[Mono-dev] Possible QuickSort optimizations for Array.Sort()
Marek Safar
marek.safar at gmail.com
Wed Apr 6 03:18:54 EDT 2011
Hello,
>>>
public class Sort<T> {
public delegate int Comparison (T v0, T v1);
You don't need yet another delegate, just use standard Func
>>
static readonly int INSERTIONSORT_THRESHOLD = 7;
Why not to used const int ?
More importantly what is performance of sorting array of 10-20 elements
called 1000000 times ?
Thanks
Marek
> 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
>
>
> Jeff
>
>
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20110406/d40e48ae/attachment.html
More information about the Mono-devel-list
mailing list