Name of sorting method

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

  1. 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
    #1
    1. Advertising

  2. Registered User

    Snis Pilbor Guest

    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
    #2
    1. Advertising

  3. "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
    #3
  4. Registered User

    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
    #4
  5. Registered User

    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
    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
    */
    , Oct 6, 2006
    #5
  6. Registered User

    Logan Shaw Guest

    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
    #6
  7. 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
    #7
  8. 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
    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
    Arthur J. O'Dwyer, Oct 6, 2006
    #8
  9. Registered User

    Snis Pilbor Guest

    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
    #9
  10. 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
    #10
  11. Registered User

    Richard Bos Guest

    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
    #11
  12. "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
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?iso-8859-1?B?bW9vcJk=?=
    Replies:
    7
    Views:
    796
    Roedy Green
    Jan 2, 2006
  2. ding feng
    Replies:
    2
    Views:
    2,774
    ding feng
    Jun 25, 2003
  3. Bobby Chamness
    Replies:
    2
    Views:
    2,371
    Joe Smith
    Apr 22, 2007
  4. Jack-2
    Replies:
    3
    Views:
    249
    Jack-2
    Dec 24, 2003
  5. Java  script  Dude

    IE name="name" & form.name property bug

    Java script Dude, Jun 29, 2004, in forum: Javascript
    Replies:
    5
    Views:
    217
    Java script Dude
    Jun 30, 2004
Loading...

Share This Page