# Name of sorting method

Discussion in 'C Programming' started by Registered User, Oct 6, 2006.

1. ### Registered UserGuest

What is the name of the following sorting method?

for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (a>a[j])
swap(&a, &a[j]);

It seems to be the opposite of bubble sort, with lighter elements going
in their proper positions first. However, this one does not compare
a[j] with a[j+1], as the normal bubble sort does.

Looks very simple, and I wonder why I couldn't find it anywhere on the
net!

Registered User, Oct 6, 2006

2. ### Snis PilborGuest

Registered User wrote:
> What is the name of the following sorting method?
>
> for (i=0; i<n-1; i++)
> for (j=i+1; j<n; j++)
> if (a>a[j])
> swap(&a, &a[j]);
>
> It seems to be the opposite of bubble sort, with lighter elements going
> in their proper positions first. However, this one does not compare
> a[j] with a[j+1], as the normal bubble sort does.
>
> Looks very simple, and I wonder why I couldn't find it anywhere on the
> net!

I doubt this has a name, but most people would call it something like
"the naive O(n^2) sorting algorithm". In otherwords, it's a lousy
sorting algorithm. It IS simple, because it just does it by brute
force. It's extremely slow. If you used this to sort a million
elements, it would take order of a trillion steps, whereas the fancier
sorting algorithms would take order of 10 million steps.

Also this is off topic at comp.lang.c since the algorithm has nothing
to do with C (in fact it even uses a weird "swap" thing that is
defined somewhere in your file, not in the C language. In my analysis
I *assumed* this was a straightforward swap function, but really it
could be anything at all for all we know...)

Snis Pilbor, Oct 6, 2006

3. ### Pascal BourguignonGuest

"Registered User" <> writes:

> What is the name of the following sorting method?
>
> for (i=0; i<n-1; i++)
> for (j=i+1; j<n; j++)
> if (a>a[j])
> swap(&a, &a[j]);
>
> It seems to be the opposite of bubble sort, with lighter elements going
> in their proper positions first. However, this one does not compare
> a[j] with a[j+1], as the normal bubble sort does.
>
> Looks very simple, and I wonder why I couldn't find it anywhere on the
> net!

It's a bad variant of the selection sort.
http://en.wikipedia.org/wiki/Selection_sort

It's very complex: Î˜(ÎÂ²) comparaisons, and O(NÂ²) swaps.

--
__Pascal Bourguignon__ http://www.informatimago.com/

HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.

Pascal Bourguignon, Oct 6, 2006
4. ### Guest

This program is very very very bad, no technology, very simple mind,
very simple algorithm, and no locality!!!! Please forgive me, and
forget this code, after several years, it will be your nightmare!

Registered User wrote:
> What is the name of the following sorting method?
>
> for (i=0; i<n-1; i++)
> for (j=i+1; j<n; j++)
> if (a>a[j])
> swap(&a, &a[j]);
>
> It seems to be the opposite of bubble sort, with lighter elements going
> in their proper positions first. However, this one does not compare
> a[j] with a[j+1], as the normal bubble sort does.
>
> Looks very simple, and I wonder why I couldn't find it anywhere on the
> net!

, Oct 6, 2006
5. ### Guest

I think it is closer to a standard bubble sort than to a selection
sort. Here is a selection sort:

#include <stdlib.h> /* for size_t */

/* flavor to taste */
typedef double e_type;

void selection_sort(e_type * array, size_t n)
{
size_t i,
j;
e_type tmp;
if (n < 2)
return;
for (i = 0; i < n - 1; i++) {
int smallest_index = i;
e_type smallest_value = array;
for (j = i + 1; j < n; j++)
if (array[j] < smallest_value) {
smallest_value = array[j];
smallest_index = j;
}
tmp = array;
array = array[smallest_index];
array[smallest_index] = tmp;
}
}

/*
P.S.
Selection sort is unbelievably lame. It is better than some others
when you have huge objects because it reduces exchanges to a small
value. However, if you make it a pointer based sort, then that small

In short, it's lame. Not as lame as the OP's sort, but lame
nonetheless.
P.P.S.
Lame, lame, lame, lame, lame. And did I mention lame?
P.P.P.S.
IMO-YMMV
*/

, Oct 6, 2006
6. ### Logan ShawGuest

Snis Pilbor wrote:
> Registered User wrote:
>> What is the name of the following sorting method?
>>
>> for (i=0; i<n-1; i++)
>> for (j=i+1; j<n; j++)
>> if (a>a[j])
>> swap(&a, &a[j]);
>>
>> It seems to be the opposite of bubble sort, with lighter elements going
>> in their proper positions first. However, this one does not compare
>> a[j] with a[j+1], as the normal bubble sort does.
>>
>> Looks very simple, and I wonder why I couldn't find it anywhere on the
>> net!

>
> I doubt this has a name, but most people would call it something like
> "the naive O(n^2) sorting algorithm". In otherwords, it's a lousy
> sorting algorithm. It IS simple, because it just does it by brute
> force. It's extremely slow.

It's not all that much worse than any other O(n^2) algorithm.
In particular, although it looks much worse than a select sort, it is
actually only slightly worse. For any given run of the inner loop,
the probability of the condition being true on each individual
iteration decreases as you go through that loop, because a gets
smaller and smaller every time you swap.

So actually, this algorithm, except in perhaps a few degenerate cases,
is not much worse than select sort at all. Granted, select sort is
not that great in the first place.

By the way, I am sure I am not the only one to have come up with it,
but I was quite proud of myself when I came up with this exact sort
in high school. I liked it because (I believe) it's more efficient
than bubble sort in practice and it's extremely easy to remember and
key in quickly. So if you are on a system with no built-in sort
function (admittedly less common a situation these days than when I
was in high school 20 years ago...), and if you're only sorting 10
elements, it could be useful.

- Logan

Logan Shaw, Oct 6, 2006
7. ### Pascal BourguignonGuest

Logan Shaw <> writes:

> Snis Pilbor wrote:
>> Registered User wrote:
>>> What is the name of the following sorting method?
>>>
>>> for (i=0; i<n-1; i++)
>>> for (j=i+1; j<n; j++)
>>> if (a>a[j])
>>> swap(&a, &a[j]);
>>>
>>> It seems to be the opposite of bubble sort, with lighter elements going
>>> in their proper positions first. However, this one does not compare
>>> a[j] with a[j+1], as the normal bubble sort does.
>>>
>>> Looks very simple, and I wonder why I couldn't find it anywhere on the
>>> net!

>> I doubt this has a name, but most people would call it something
>> like
>> "the naive O(n^2) sorting algorithm". In otherwords, it's a lousy
>> sorting algorithm. It IS simple, because it just does it by brute
>> force. It's extremely slow.

>
> It's not all that much worse than any other O(n^2) algorithm.

Yes it is.
Because most of the other O(nÂ²) algorithms are Î©(n).
Only the selection sort is both O(nÂ²) and Î©(nÂ²) and that's why I'm
saying this is some kind of selection sort.

> By the way, I am sure I am not the only one to have come up with it,
> but I was quite proud of myself when I came up with this exact sort
> in high school. I liked it because (I believe) it's more efficient
> than bubble sort in practice and it's extremely easy to remember and
> key in quickly. So if you are on a system with no built-in sort
> function (admittedly less common a situation these days than when I
> was in high school 20 years ago...), and if you're only sorting 10
> elements, it could be useful.

Bubble sort is Î©(n). We cannot do much better...
When you need to sort data that is already mostly sorted, bubble sort
is a good choice.

--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.

Pascal Bourguignon, Oct 6, 2006
8. ### Arthur J. O'DwyerGuest

On Fri, 6 Oct 2006, Pascal Bourguignon wrote:
> Logan Shaw <> writes:
>>> Registered User wrote:
>>>>
>>>> for (i=0; i<n-1; i++)
>>>> for (j=i+1; j<n; j++)
>>>> if (a>a[j])
>>>> swap(&a, &a[j]);

>>
>> It's not all that much worse than any other O(n^2) algorithm.

>
> Yes it is.
> Because most of the other O(nÂ²) algorithms are Î©(n).

/All/ comparison-based sorting algorithms are Omega(n), for obvious
reasons. (BTW, don't use crazy character sets on Usenet. They interfere

> Only the selection sort is both O(nÂ²) and Î©(nÂ²)

Don't be silly. Plenty of algorithms are both O(n^2) and Omega(n^2)
(i.e., an asymptotically tight bound, or Theta(n^2)).

> and that's why I'm saying this is some kind of selection sort.

I agree with Logan that it doesn't need a name.

-Arthur

Arthur J. O'Dwyer, Oct 6, 2006
9. ### Snis PilborGuest

Logan Shaw wrote:
> Snis Pilbor wrote:
> > Registered User wrote:
> >> What is the name of the following sorting method?
> >>
> >> for (i=0; i<n-1; i++)
> >> for (j=i+1; j<n; j++)
> >> if (a>a[j])
> >> swap(&a, &a[j]);
> >>

> (snip)
>
> By the way, I am sure I am not the only one to have come up with it,
> but I was quite proud of myself when I came up with this exact sort
> in high school. I liked it because (I believe) it's more efficient
> than bubble sort in practice and it's extremely easy to remember and
> key in quickly. So if you are on a system with no built-in sort
> function (admittedly less common a situation these days than when I
> was in high school 20 years ago...), and if you're only sorting 10
> elements, it could be useful.

Not to belittle you or anything, but what is to be proud of? This is
about as straightforward as it gets- I have trouble thinking of a MORE
straightforward, brainless way of doing the sort, short of maybe
specifically finding the lowest entry and putting it at the bottom of a
new array, then the 2nd lowest, etc., then copying the new array onto
the original. I mean, in terms of ingenuity involved, the OP's sort
algorithm is about one or two steps above "Hello, world!"

Snis Pilbor, Oct 6, 2006
10. ### Simon Richard ClarkstoneGuest

Snis Pilbor wrote:
> Logan Shaw wrote:
>
>>Snis Pilbor wrote:
>>
>>>Registered User wrote:
>>>
>>>>What is the name of the following sorting method?
>>>>
>>>>for (i=0; i<n-1; i++)
>>>> for (j=i+1; j<n; j++)
>>>> if (a>a[j])
>>>> swap(&a, &a[j]);
>>>>

>>
>>(snip)
>>
>>By the way, I am sure I am not the only one to have come up with it,
>>but I was quite proud of myself when I came up with this exact sort
>>in high school. I liked it because (I believe) it's more efficient
>>than bubble sort in practice and it's extremely easy to remember and
>>key in quickly. So if you are on a system with no built-in sort
>>function (admittedly less common a situation these days than when I
>>was in high school 20 years ago...), and if you're only sorting 10
>>elements, it could be useful.

>
>
> Not to belittle you or anything, but what is to be proud of? This is
> about as straightforward as it gets- I have trouble thinking of a MORE
> straightforward, brainless way of doing the sort, short of maybe
> specifically finding the lowest entry and putting it at the bottom of a
> new array, then the 2nd lowest, etc., then copying the new array onto
> the original. I mean, in terms of ingenuity involved, the OP's sort
> algorithm is about one or two steps above "Hello, world!"

_QBasic Programming for Dummies_ (my first programming book) actually
claims this one is not too bad. What could they be comparing it
against? (IIRC, Knuth gives an O(n^3) algorithm as the one with the
shortest MIX program.)

--
Simon Richard Clarkstone: s.r.cl?rkst?n?@durham.ac.uk/s?m?n.cl?rkst?n?@
hotmail.com ### "I have a spelling chequer / it came with my PC /
it plainly marks for my revue / Mistake's I cannot sea" ...
by: John Brophy (at: http://www.cfwf.ca/farmj/fjjun96/)

Simon Richard Clarkstone, Oct 10, 2006
11. ### Richard BosGuest

Simon Richard Clarkstone <> wrote:

> >>>Registered User wrote:
> >>>
> >>>>What is the name of the following sorting method?
> >>>>
> >>>>for (i=0; i<n-1; i++)
> >>>> for (j=i+1; j<n; j++)
> >>>> if (a>a[j])
> >>>> swap(&a, &a[j]);
> >>>>

> _QBasic Programming for Dummies_ (my first programming book) actually
> claims this one is not too bad. What could they be comparing it
> against?

Belgian Sort?

Richard

Richard Bos, Oct 12, 2006
12. ### Paul ConnollyGuest

"Richard Bos" <> wrote in message
news:4all.nl...
> Simon Richard Clarkstone <> wrote:
>
>> >>>Registered User wrote:
>> >>>
>> >>>>What is the name of the following sorting method?
>> >>>>
>> >>>>for (i=0; i<n-1; i++)
>> >>>> for (j=i+1; j<n; j++)
>> >>>> if (a>a[j])
>> >>>> swap(&a, &a[j]);
>> >>>>

>
>> _QBasic Programming for Dummies_ (my first programming book) actually
>> claims this one is not too bad. What could they be comparing it
>> against?

>
> Belgian Sort?
>
> Richard

If it looks greek to a london cabbie then in cockney rhyming slang that
would be bubble* sort
*bubble and squeak = greek
hopefully that clears up the nationality of this sort

Paul Connolly, Oct 12, 2006