Consider two improvement for Quicksort.
1. Chose a better pivot so that it never has just 1 key in a partition.
2. Only call the recursion when the array having length >16 (or greater).
The question is: do these improvement change the worst case and average-case complexities of the algorithm (n*n and n*logn) and why ?
Any idea ? ( I suppose those don't change the complexity (in average), but why ?)
The first improvement (better pivot) definitely changes the worst case O(n^2), which occurs if a sorted list is to be sorted and the pivot is simply chosen to be the first (0th) element.
The worst case is O(n^2) because the left partitions are always going to be of size 0, and everything will always be on the right (greater than) the pivot, which is the smallest element.
If a better pivot is chosen, the left partitions at each step in the quicksort will have some size greater than 0, coming closer to "chopping the problem in half" [O(n*log n)].
Hope this helps,
- D.t.O
Well, your homework assignment asks you to consider.
What have you considered so far? You could implement the algorithm, with and without the purposed cut off at 16, and test the performance. You could do it without implementing too, just by visualizing (use pen and paper!) stop by step how the sorting progresses. Andyou could search the web. Try words like cutoff quicksort "big o" qsort in your search criteria.
Good luck with the assignment!
I came up with the following solution (not sure that correct)
If when reaching the length of 16, instead of calling recursion, you applied the insertion Sort. In this case, with the array almost sorted, the Insertion sort takes linear time.
Then with the worst case, the complexity should be n*(n-15) or n*n - 15*n.
How do you think ?
As always, one of the best places to look for code is in the Sun J2SE source code. The Arrays.sort() methods (except the one that takes an Object[] parameter) are all a tuned quicksort, which, according to the documentation, "offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance."
Here's the code that you are probably interested in:
// Insertion sort on smallest arrays
if (len < 7) {
for (int i=off; i<len+off; i++)
for (int j=i; j>off && x[j-1]>x[j]; j--)
swap(x, j, j-1);
return;
}
(The swap() method just swaps the two specified indices of the array.)
Apparently insertion sort, when used on arrays of length 0-6, has at least about n*log(n) performance.
Hope this helps,
- D.t.O
> Apparently insertion sort, when used on arrays of length 0-6, has at least about n*log(n) performance.
If you look at the definition of big-O notation, you'll find that if you restrict the range of n to be finite, any algorithm which is guaranteed to terminate will be O(n^0) (or O(1) - I just like to make the variable explicit).
> If you look at the definition of big-O notation,
> you'll find that if you restrict the range of n to be
> finite, any algorithm which is guaranteed to terminate
> will be O(n^0) (or O(1) - I just like to make the
> variable explicit).
That's right, but although 2 operations and 2 million operations both reduce to O(1), they are different.