Average time complexity of quicksort vs insertion

问题:

I'm lead to believe that quick sort should be faster than insertion sort on a medium size unorderd int array. I've implemented both algorithms in java and I notice quicksort is significantly slower then insertion sorrt.

I have a theory: quiksort is being slower because it's recursive and the call it's making to it's own method signature is quite slow in the JVM which is why my timer is giving much higher readings than I expected, whereas insertion isn't recursive and all thwe work is done within one method so they JVM isn't having to do any extra grunt work? amirite?

回答1:

You may be interested in these Sorting Algorithm Animations.

回答2:

Probably not, unless your recursive methods are making any big allocations. Its more likely there's a quirk in your code or your data set is small.

The JVM shouldn't have any trouble with recursive calls.

回答3:

Unless you've hit one of Quicksort's pathological cases (often, a list that is already sorted), Quicksort should be O(n log n) — substantially faster than insertion sort's O(n^2) as n increases.

You may want to use merge sort or heap sort instead; they don't have pathological cases. They are both O(n log n).

(When I did these long ago in C++, quicksort was faster than insertion sort with fairly small ns. Radix is notable faster with mid-size ns as well.)

回答4:

theoretically Quick Sort should work faster than insertion sort for random data of medium to large size.

I guess the differences should be in the way QS is implemented:

pivot selection for the given data ?(3-median is a better approach)

using the same Swap mechanism for QS and insertion sort ?

is the input random enuf, i.e ., if you have clusters of ordered data performance will
suffer.

I did this exercise in C and results are in accordance with theory.

回答5:

Actually for small value of n insertion sort is better than quick sort. As for small value of n instead of n^2 or nlogn the time depends more on constant.

回答6:

The fastest implementations of quicksort use looping instead of recursion. Recursion typically isn't very fast.

回答7:

You have to be careful how you make the recursive calls, and because it's Java, you can't rely on tail calls being optimized, so you should probably manage your own stack for the recursion.

Everything that is available to be known about quicksort vs insertion sort can be found in Bob Sedgewick's doctoral dissertation. The boiled-down version can be found in his algorithms textbooks.

回答8:

I remember that in school, when we did sorting in Java, we would actually do a hybrid of the two. So for resursive algorithms like quicksort and mergesort, we would actually do insertion sort for segments that were very smal, say 10 records or so.

Recursion is slow, so use it with care. And as was noted before, if you can figure a way to implement the same algorithm in an iterative fashion, then do that.

回答9:

There are three things to consider here. First, insertion sort is much faster (O(n) vs O(n log n)) than quicksort IF the data set is already sorted, or nearly so; second, if the data set is very small, the 'start up time" to set up the quicksort, find a pivot point and so on, dominates the rest; and third, Quicksort is a little subtle, you may want to re-read the code after a night's sleep.

回答10:

How are you choosing your pivot in Quicksort? This simple fact is the key to your question, and probably why Quicksort is running slower. In cases like this it's a good idea to post at least the important sections of your code if you're looking for some real help.

回答11:

Actually for little worth of n insertion type is healthier than fast type. As for little worth of n rather than n^2 or nlogn the time depends a lot of on constant. Web Development Indianapolis