Thread: Shell Sort vs Heap Sort vs Quick Sort

  1. #1
    Registered User
    Join Date
    May 2002
    Posts
    71

    Thumbs up Shell Sort vs Heap Sort vs Quick Sort

    i am having a debate as to which of the sort is more efficient in 2 cases:

    when a 2d array of size 50, 100, or 1000 of randomly generated integers


    and the same 2d array with all numbers sorted but only 2 indexes where their values have been exchanged.


    for these 2 cases which of the 3 sorts seems more efficient.. i am pretty sure the quick sort is the best for the randomly generated array..

    but what about the other case... the problem that is bugging me is that when the size is small the difference in the number of comparisons made with quick sort is very similar to the shell sort ...
    any suggestions welcomed

  2. #2
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Have a look at this and see if it helps you.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  3. #3
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Quick sort is the best general purpose sorting algorithm. Sorting is a funny thing though. Some sorting algorithms are better for one thing but not so good for another. Quick sort is best for sorting unsorted data (not necessarily random data). Bubble sorting, for example, can out perform quick sort when the data is sorted or nearly sorted. The reason that so many sorting algorithms exist is because they each have their place. I know this didn't truly answer your question but this question is difficult to answer with any degree of certainty. Especially since "random" should give a non-sequencial string of values but can do otherwise.

  4. #4
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Equally implemented, I would say that insertion sort
    or shell sort would win on almost sorted data.
    100 isn't too large so you might want to experiment with
    a million elements.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    To summarize:

    Lots of items to sort, the most efficient wins.
    Few items to sort, it doesn't make much difference what you use.

    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Quzah is right. If you are sorting 5 items it is difficult to go wrong. Even 1000 items isn't that big of an issue so long as comparison is not a big issue. Actually that brings me to another point. The way one item is compared to another item is another large factor in speed. Obviously statements such as x == y will work quicker than statements like (x == y && x < z && z != y && z > m).

  7. #7
    Registered User
    Join Date
    May 2002
    Posts
    71
    thanks a lot everybody.
    that feedback was really helpful

    from the program i created and tested it seemed like the quick sort did the best for large arrays and pretty much for small arrays too and even for random and nearly sorted arrays...

    btw, awesome site mate

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 05:21 PM
  2. Shell, Heap and Quick Sort
    By GaPe in forum C Programming
    Replies: 1
    Last Post: 08-19-2003, 01:04 PM
  3. Quick Sort Help
    By NavyBlue in forum C Programming
    Replies: 1
    Last Post: 03-02-2003, 10:34 PM
  4. question about Quick Sort
    By Liberty4all in forum C++ Programming
    Replies: 8
    Last Post: 11-23-2002, 10:38 AM
  5. Quick sort
    By Saiyanman in forum C Programming
    Replies: 4
    Last Post: 07-30-2002, 10:16 PM