Name of sorting method

This is a discussion on Name of sorting method within the Tech Board forums, part of the Community Boards category; What is the name of the following sorting method? Code: for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (a[i]>a[j]) ...

  1. #1
    Registered User
    Join Date
    Jun 2006
    Posts
    75

    Question Name of sorting method

    What is the name of the following sorting method?

    Code:
    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!

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,638
    > lighter elements going in their proper positions first
    or larger elements being pushed down - this is the definition of a bubble sort because the items percolate to their proper places. That and the code looks like a bubble sort to me.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered Luser risby's Avatar
    Join Date
    Jun 2006
    Posts
    72
    Quote Originally Posted by noodles
    What is the name of the following sorting method?

    Code:
    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!
    As you say, bubble sort swaps adjacent elements. It also sets a flag to show that a swap has taken place and repeats until the flag remains unset on a pass through the array.

    This is a Shell sort that gets the first element from wherever it is in the rest of the array and then gets the second element, etc. no need for a flag and usually more efficient.
    ===
    Don't grumble about what you can't have;
    be grateful you don't get what you deserve.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >As you say, bubble sort swaps adjacent elements.
    Not necessarily.

    >It also sets a flag to show that a swap has taken place and repeats until the flag remains unset
    Again, not necessarily.

    >This is a Shell sort
    It's most certainly not a Shell sort. If Shell sort were so trivial, life would be grand indeed.
    My best code is written with the delete key.

  6. #6
    Registered Luser risby's Avatar
    Join Date
    Jun 2006
    Posts
    72
    Quote Originally Posted by Prelude
    >This is a Shell sort
    It's most certainly not a Shell sort.
    Oh yeah ... it's that other one init ... I'm always getting those two confused ... um ... ?
    ===
    Don't grumble about what you can't have;
    be grateful you don't get what you deserve.

  7. #7
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,638
    Quote Originally Posted by risby
    Oh yeah ... it's that other one init ... I'm always getting those two confused ... um ... ?
    [guesses] It's not an insert sort either. [/guesses]
    It's a bubble sort, just like I said.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. best sorting method to sort half end of array
    By nitinmhetre in forum C Programming
    Replies: 2
    Last Post: 01-11-2007, 11:18 AM
  2. Sorting Method
    By silicon in forum C++ Programming
    Replies: 2
    Last Post: 04-18-2005, 10:06 PM
  3. change sorting method using polymorphism
    By Forever82 in forum C++ Programming
    Replies: 2
    Last Post: 07-31-2003, 01:21 PM
  4. Best sorting method to use
    By pelp in forum C++ Programming
    Replies: 3
    Last Post: 03-11-2003, 11:30 PM
  5. Sorting words with a fast, effincient sorting method
    By Unregistered in forum C++ Programming
    Replies: 19
    Last Post: 07-12-2002, 04:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21