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@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@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@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@lists.ximian.com
http://lists.ximian.com/mailman/listinfo/mono-devel-list
_______________________________________________
Mono-devel-list mailing list
Mono-devel-list@lists.ximian.com
http://lists.ximian.com/mailman/listinfo/mono-devel-list
