«

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[i]>a[j])
swap(&a[i], &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 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[i]>a[j])
> swap(&a[i], &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...)

"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[i]>a[j])
> swap(&a[i], &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.

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[i]>a[j])
> swap(&a[i], &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 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[i];
for (j = i + 1; j < n; j++)
if (array[j] < smallest_value) {
smallest_value = array[j];
smallest_index = j;
}
tmp = array[i];
array[i] = 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
advantage vanishes.

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
*/

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[i]>a[j])
>> swap(&a[i], &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[i] 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 <lshaw-> 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[i]>a[j])
>>> swap(&a[i], &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.

On Fri, 6 Oct 2006, Pascal Bourguignon wrote:
> Logan Shaw <lshaw-> writes:
>>> Registered User wrote:
>>>>
>>>> for (i=0; i<n-1; i++)
>>>> for (j=i+1; j<n; j++)
>>>> if (a[i]>a[j])
>>>> swap(&a[i], &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
with some newsreaders' displays.)

> 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

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[i]>a[j])
> >> swap(&a[i], &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 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[i]>a[j])
>>>> swap(&a[i], &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/)