[vangogh]

Bubblesort is O(n^2) and shouldn't be used for huge lists. Quicksort is O(nlogn) and is easy to understand/use. From what I remember from data structures class, if you're sorting a gigantic list you should look into something like radix sort which is O(n). The basic idea behind least-significant-digit radix sort is this: First you distribute your numbers into ten bins labeled 0...9 based on their rightmost digit. Then you collect them together from left to right, bottom to top and distribute them again using their second rightmost digit. Then collect and distribute them again based on their third rightmost digit. If the largest number you're sorting is only three digits long then you are done, otherwise keep going. Note: I am not sure about the stability of radix sort.

[Gloin]

vangogh, on 17 Jan, 2009 - 04:34 PM, said:

Note: I am not sure about the stability of radix sort.

Let's just say you don't want to use radix sort if you're working with numbers from an exponential distribution.

[numerical_jerome]

Quote

Bubblesort is O(n^2) and shouldn't be used for huge lists. Quicksort is O(nlogn) and is easy to understand/use

Quicksort is O(N^2) as well, with an *average* case run time complexity of N lg(N).

though somewhat nit-picky, the distinction is important, for example in the case of a sorted list, and a pivot of the "left most" element, quick-sort will take almost as much time as a selection sort to run, and in a recursive implementation will have a recursion depth of almost the length of the list!

-Jerome

[Gloin]

You could simply say that the complexity of QuickSort depends on the choice of its pivot-element.

[numerical_jerome]

Quick sort is O(N^2) no matter where you put the pivot, or even if the pivot is moved each recursion (as mentioned in my first post). The key is not that you are reducing the *worst case* runtime complexity, but enlarging the set of cases that would achieve the *average case* runtime complexity.

I apologize that my post may seem preachy, but an algorithm that is (for a given problem size N) Nlg(N) 999,999 times in 1,000,000 , and N^2 once, is an O(N^2) algorithm.

Quicksort optimization tricks operate in this manner. They reduce the number of cases where the worst case is realized, but do not eliminate them entirely.

-Jerome

[macosxnerd101]

I did my science fair project on this. Here are my findings:

Radix sort is the most efficient with an O(n).
Quicksort is after Radix Sort (about 4x the # steps of Radix Sort) with an O(n log n)

Mergesort had 125% the # steps as Quicksort also with an O(n log n)

Insertion Sort, Selection Sort & Bubblesort had an O(n^2), with Insertion sort being the more efficient of the 3 followed by Selection Sort followed by Bubblesort. All 3 were less efficient than Mergesort.

[Gloin]

So what is your conclusion?

Is Radix sort always best?

[numerical_jerome]

Quote

Is Radix sort always best?

if you are sorting tokens that lend themselves to a radix sort, i.e.fixed precision integers.

[dorknexus]

I know this is old but still important for anyone looking around in the future concerning the generic efficiency of various comparison based sorts.

Refer to these graphs for the time complexity of those popular algorithms which fall under the classification of O(n^2)



And refer to this graph for the time complexity of those popular algorithms which fall under the classification of O(nlog(n))



For both sets of algorithms, the only difference for smaller inputs is the overhead which is generally implementation specific.
The trade offs to be considered when deciding which sorting algorithm to utilize might be:
ease of implementation
ease of maintenance
execution and memory overhead
performance based on input size

[boredom]

Obama doesn't know anything about Computers. who so ever reads computers at least knows Bubble Sort, So he replied ''Bubble sort would be the wrong way to go''. trying to say that he is right.

I think Obama should have answered quick sort.

[griffinfujioka]

That's awesome that he knew that. I just wrote a program to compare the number of operations for 10, 100, 100, etc. random numbers an insertion sort and quick sort took. Of course the quicksort took less operations and was faster, but the lab was great for showing algorithm efficiency.

This post has been edited by griffinfujioka: 30 April 2009 - 06:02 PM