[Mono-dev] Possible QuickSort optimizations for Array.Sort()
fejj at novell.com
Tue Apr 5 18:48:59 EDT 2011
Attached you'll find qsort.cs which includes 3 QuickSort implementations:
1. QuickSortBasic[R]: This is a basic QuickSort implementation and the
one currently in use as the sorting function in Array.Sort(). This
implementation always uses the middle element as the pivot.
2. QuickSortMedian[R]: This implementation is also a basic QuickSort
implementation which attempts choose a better pivot based on the first,
last, and middle elements. For sorted inputs and random inputs, this
seems to help performance somewhat as the array gets larger and larger.
However, for reverse-sorted inputs, it seems to kill performance.
Perhaps if I choose 3 random points to feed into Median() it will do better.
3. QuickSortInsertion[R]: This implementation includes the above perf
trick and also includes an Insertion Sort fallback when partitions are
broken down smaller than some threshold # of elements (7 in the attached
code). It also falls back to Insertion Sort when it encounters a
worst-case scenario. As always, the performance improvement with this is
greater as the number of elements increases and/or as the comparison
function becomes more complex.
You'll notice that the attached test program will print out the number
of comparisons that each sort routine uses in order to complete its job.
It's important to keep in mind that the more complex the comparison
function is, the more important it is that the number of comparisons is
kept to a minimum.
Here are some example runs:
[fejj at warpig sorting]$ mono ./qsort.exe -random 100000000
Basic QuickSort comparisons needed: 3807986012
QuickSort+Median comparisons needed: 3077915654
QuickSort+Insertion comparisons needed: 3021355043
Basic QuickSort finished in: 00:00:43.8178721s
QuickSort+Median finished in: 00:00:37.3047443s
QuickSort+Insertion finished in: 00:00:36.6122681s
[fejj at warpig sorting]$ mono ./qsort.exe -sorted 100000000
Basic QuickSort comparisons needed: 2632227866
QuickSort+Median comparisons needed: 2632227867
QuickSort+Insertion comparisons needed: 2483222808
Basic QuickSort finished in: 00:00:21.8213618s
QuickSort+Median finished in: 00:00:21.2622527s
QuickSort+Insertion finished in: 00:00:19.0837352s
(Note: I reduced the array size here due to wanting to head home for dinner)
[fejj at warpig sorting]$ mono ./qsort.exe -reversed 10000
Basic QuickSort comparisons needed: 129546
QuickSort+Median comparisons needed: 12522499
QuickSort+Insertion comparisons needed: 39993
Basic QuickSort finished in: 00:00:00.0016905s
QuickSort+Median finished in: 00:00:00.0911385s
QuickSort+Insertion finished in: 00:00:00.0008721s
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 7895 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20110405/bee0a775/attachment.bin
More information about the Mono-devel-list