# Shell Sort vs Heap Sort vs Quick Sort

• 11-22-2002
mackol
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 :)
• 11-22-2002
Hammer
Have a look at this and see if it helps you.
• 11-22-2002
master5001
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.
• 11-22-2002
Nick
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.
• 11-22-2002
quzah
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.
• 11-22-2002
master5001
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).
• 11-22-2002
mackol
thanks a lot everybody.