QuickSort conclusions (Off-Topic)

by marmot 1333 , Wednesday, October 23, 2013, 08:58 (4055 days ago)

There was some interest in my Java-based Quicksort project but that thread got locked.

To update: I was using an algorithm out of my book that used the right-most value as pivot. This led to the partitions being extremely unbalanced (8191 vs 1 in case of 2^13) and led to stack overflows starting at 2^13.

So I just updated my algorithm to utilize randomized quicksort; it chooses a pseudo-random element in the array and uses that as pivot. This solved my stack overflows as I was able to sort up to 2^20 for sorted, reverse sorted, and shuffled arrays with no problem.

So I guess I was lucky, Sekhmet, because my quicksort was performing faster than heapsort on the largest set (2^20). Here's some sample output.

Starting a HeapSort with n sorted numbers, where n = 1048576
Time to sort 1048576 sorted entries with Heapsort was 1015 milliseconds.
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Starting a HeapSort with n reversed numbers, where n = 1048576
Time to sort 1048576 reversed entries with Heapsort was 886 milliseconds.
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Starting a HeapSort with n shuffled numbers, where n = 1048576
Time to sort 1048576 shuffled entries with Heapsort was 1483 milliseconds.
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Before sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
Starting a QuickSort with n sorted numbers, where n = 1048576
Time to sort 1048576 sorted entries with QuickSort was 396 milliseconds.
After sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Before sorting the array is:
[(1): 1048576]
[(524288): 524289]
[(1048576): 1]
Starting a QuickSort with n reversed numbers, where n = 1048576
Time to sort 1048576 reversed entries with QuickSort was 400 milliseconds.
After sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Before sorting the array is:
[(1): 857704]
[(524288): 190051]
[(1048576): 792221]
Starting a QuickSort with n shuffled numbers, where n = 1048576
Time to sort 1048576 shuffled entries with QuickSort was 481 milliseconds.
After sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]