On 04/06/2011 03:18 AM, Marek Safar wrote:
Hello,
>>>
public class Sort<T> {
public delegate int Comparison (T v0, T v1);
You don't need yet another delegate, just use standard Func
It was just a quick hack to get things going, if we decide it's worth
having corlib move to my QuickSort implementation, it would use the same
standard func corlib is using now.
>>
static readonly int INSERTIONSORT_THRESHOLD = 7;
Why not to used const int ?
I never learned when to use const vs static/readonly in C# :-(
I assume you suggest const because it is more appropriate, so I will :-)
More importantly what is performance of sorting array of 10-20
elements called 1000000 times ?
I've attached a sample program to test this in case you'd like to play
with it some more, but here are the results on my system for 20 elements
@ 1 million iterations:
[fejj@serenity sorting]$ mono ./qsort-small.exe -random 1000000
Timings for sorting 20 random items 1000000 times.
Basic QuickSort finished in: 00:00:03.0227324s
QuickSort+Insertion finished in: 00:00:02.5357660s
[fejj@serenity sorting]$ mono ./qsort-small.exe -sorted 1000000
Timings for sorting 20 sorted items 1000000 times.
Basic QuickSort finished in: 00:00:02.3003898s
QuickSort+Insertion finished in: 00:00:01.9493073s
[fejj@serenity sorting]$ mono ./qsort-small.exe -reversed 1000000
Timings for sorting 20 reversed items 1000000 times.
Basic QuickSort finished in: 00:00:02.4001482s
QuickSort+Insertion finished in: 00:00:02.3277809s
And here are the results for 10 elements @ 1 million iterations:
[fejj@serenity sorting]$ mono ./qsort-small.exe -random 1000000
Timings for sorting 10 random items 1000000 times.
Basic QuickSort finished in: 00:00:01.8165901s
QuickSort+Insertion finished in: 00:00:01.7363410s
[fejj@serenity sorting]$ mono ./qsort-small.exe -sorted 1000000
Timings for sorting 10 sorted items 1000000 times.
Basic QuickSort finished in: 00:00:01.7398261s
QuickSort+Insertion finished in: 00:00:01.5270049s
[fejj@serenity sorting]$ mono ./qsort-small.exe -reversed 1000000
Timings for sorting 10 reversed items 1000000 times.
Basic QuickSort finished in: 00:00:01.7166351s
QuickSort+Insertion finished in: 00:00:01.6798535s
Hope that helps,
Jeff
using System;
using System.Diagnostics;
namespace SortingTest {
public class Sort<T> {
public delegate int Comparison (T v0, T v1);
static void swap (T [] array, int i, int j)
{
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
static void QuickSortBasicR (T [] array, int low0, int high0, Comparison comparison)
{
int low = low0;
int high = high0;
// Be careful with overflows
int mid = low + ((high - low) / 2);
T keyPivot = array [mid];
while (true) {
if (keyPivot == null) {
while (low < high0 && array [low] == null)
++low;
while (high > low0 && array [high] != null)
--high;
} else {
// Move the walls in
while (low < high0 && comparison (array [low], keyPivot) < 0)
++low;
while (high > low0 && comparison (keyPivot, array [high]) < 0)
--high;
}
if (low <= high) {
swap (array, low, high);
++low;
--high;
} else
break;
}
if (low0 < high)
QuickSortBasicR (array, low0, high, comparison);
if (low < high0)
QuickSortBasicR (array, low, high0, comparison);
}
public static void QuickSortBasic (T [] array, int index, int length, Comparison comparison)
{
QuickSortBasicR (array, index, index + length - 1, comparison);
}
static int Median (T [] array, int a, int b, int c, Comparison comparison)
{
T keyA = array[a];
T keyB = array[b];
T keyC = array[c];
if (comparison (keyA, keyB) < 0) {
/* a < b < c */
if (comparison (keyB, keyC) < 0)
return b;
/* a < c < b */
if (comparison (keyA, keyC) < 0)
return c;
/* c < a < b */
return a;
} else {
/* b < a < c */
if (comparison (keyA, keyC) < 0)
return a;
/* b < c < a */
if (comparison (keyB, keyC) < 0)
return c;
/* c < b < a */
return b;
}
}
static void QuickSortMedianR (T [] array, int low, int high, Comparison comparison)
{
int pivot, mid, i, k;
T pval;
// determine which element contains the median value
mid = low + ((high - low) / 2);
pivot = Median (array, low, mid, high, comparison);
if (pivot != low) {
// swap pivot value into first element (so the location stays constant)
swap (array, low, pivot);
pivot = low;
}
pval = array[pivot];
i = low + 1;
k = high;
do {
if (pval == null) {
while (i < k && array[i] == null)
i++;
while (k >= i && array[k] != null)
k--;
} else {
// find the first element with a value > pivot value
while (i < k && comparison (array[i], pval) <= 0)
i++;
// find the last element with a value <= pivot value
while (k >= i && comparison (pval, array[k]) < 0)
k--;
}
if (i < k) {
swap (array, i, k);
i++;
k--;
} else
break;
} while (true);
if (k != pivot) {
// swap the pivot with the last element in the first partition
swap (array, pivot, k);
}
if (k - 1 > low)
QuickSortMedianR (array, low, k - 1, comparison);
if (k + 1 < high)
QuickSortMedianR (array, k + 1, high, comparison);
}
public static void QuickSortMedian (T [] array, int index, int length, Comparison comparison)
{
QuickSortMedianR (array, index, index + length - 1, comparison);
}
const int INSERTIONSORT_THRESHOLD = 7;
static void QuickSortInsertionR (T [] array, int low, int high, Comparison comparison)
{
int pivot, mid, n1, n2, i, k;
T pval;
if ((low + INSERTIONSORT_THRESHOLD) > high) {
// switch to insertion sort
for (i = low + 1; i <= high; i++)
for (k = i; k > low && comparison (array[k], array[k-1]) < 0; k--)
swap (array, k - 1, k);
return;
}
// determine which element contains the median value
mid = low + ((high - low) / 2);
pivot = Median (array, low, mid, high, comparison);
if (pivot != low) {
// swap pivot value into first element (so the location stays constant)
swap (array, low, pivot);
pivot = low;
}
pval = array[pivot];
i = low + 1;
k = high;
do {
if (pval == null) {
while (i < k && array[i] == null)
i++;
while (k >= i && array[k] != null)
k--;
} else {
// find the first element with a value > pivot value
while (i < k && comparison (array[i], pval) <= 0)
i++;
// find the last element with a value <= pivot value
while (k >= i && comparison (pval, array[k]) < 0)
k--;
}
if (i < k) {
swap (array, i, k);
i++;
k--;
} else
break;
} while (true);
if (k != pivot) {
// swap the pivot with the last element in the first partition
swap (array, pivot, k);
}
// calculate partition sizes
n2 = (high - k);
n1 = (k - low);
if (n1 <= 1 || n2 <= 1) {
// pathological case detected, switch to insertion sort
for (i = low + 1; i <= high; i++)
for (k = i; k > low && comparison (array[k], array[k-1]) < 0; k--)
swap (array, k - 1, k);
} else {
QuickSortInsertionR (array, k + 1, high, comparison);
QuickSortInsertionR (array, low, k - 1, comparison);
}
}
public static void QuickSortInsertion (T [] array, int index, int length, Comparison comparison)
{
QuickSortInsertionR (array, index, index + length - 1, comparison);
}
}
public class TestProgram {
enum InputMode {
Random,
Sorted,
Reversed
}
static int Int32Compare (int v0, int v1) { return v0 - v1; }
public static void Main (string [] args)
{
InputMode mode = InputMode.Random;
Random random = new Random ();
Stopwatch [] timer;
int loops = 10000;
int [] master;
int [] array;
int n = 20;
for (int i = 0; i < args.Length; i++) {
if (args[i] == "-sorted")
mode = InputMode.Sorted;
else if (args[i] == "-reversed")
mode = InputMode.Reversed;
else if (args[i] == "-random")
mode = InputMode.Random;
else if (!Int32.TryParse (args[i], out loops))
return;
}
master = new int [n];
array = new int [n];
switch (mode) {
case InputMode.Random:
for (int i = 0; i < n; i++)
master[i] = random.Next (0, Int32.MaxValue);
break;
case InputMode.Reversed:
for (int i = 0; i < n; i++)
master[i] = n - i;
break;
case InputMode.Sorted:
for (int i = 0; i < n; i++)
master[i] = i;
break;
}
timer = new Stopwatch [2];
timer[0] = new Stopwatch ();
timer[1] = new Stopwatch ();
for (int i = 0; i < loops; i++) {
Array.Copy (master, array, n);
timer[0].Start ();
Sort<int>.QuickSortBasic (array, 0, n, Int32Compare);
timer[0].Stop ();
}
for (int i = 0; i < loops; i++) {
Array.Copy (master, array, n);
timer[1].Start ();
Sort<int>.QuickSortInsertion (array, 0, n, Int32Compare);
timer[1].Stop ();
}
Console.WriteLine ("Timings for sorting {0} {1} items {2} times.", n, mode.ToString ().ToLower (), loops);
Console.WriteLine ("Basic QuickSort finished in: {0}s", timer[0].Elapsed);
Console.WriteLine ("QuickSort+Insertion finished in: {0}s", timer[1].Elapsed);
}
}
}
_______________________________________________
Mono-devel-list mailing list
Mono-devel-list@lists.ximian.com
http://lists.ximian.com/mailman/listinfo/mono-devel-list
