// Sorting with Generic C#, and comparisons with dynamically typed sorting // Revised to use three-way comparisons (IComparable and IGComparable) // Sorting integers or strings // This program requires .NET version 2.0. // Peter Sestoft (sestoft@itu.dk) * 2001-11-01, 2001-11-22, 2003-08-11 using System; // Generic sorting routines public class Polysort { // Cannot use this in // void qsort(IGComparable[] arr, int a, int b) // because ref arguments that are array elements of reference // type must have the exact element type of the formal parameter private static void swap(ref U s, ref U t) { U tmp = s; s = t; t = tmp; } private static void swap(U[] arr, int s, int t) { U tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp; } private static void swap(object[] arr, int s, int t) { object tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp; } // Polymorphic OO-style quicksort: general, not typesafe private static void qsort(IGComparable[] arr, int a, int b) { // sort arr[a..b] if (a < b) { int i = a, j = b; IGComparable x = arr[(i+j) / 2]; do { while (arr[i].CompareTo(x) < 0) i++; while (x.CompareTo(arr[j]) < 0) j--; if (i <= j) { swap< IGComparable >(arr, i, j); i++; j--; } } while (i <= j); qsort(arr, a, j); qsort(arr, i, b); } } public static void Quicksort(IGComparable[] arr) { qsort(arr, 0, arr.Length-1); } public static void CheckSorted(IGComparable[] arr) { for (int i=1; i(T[] arr, IGComparer cmp, int a, int b) { // sort arr[a..b] if (a < b) { int i = a, j = b; T x = arr[(i+j) / 2]; do { while (cmp.Compare(arr[i], x) < 0) i++; while (cmp.Compare(x, arr[j]) < 0) j--; if (i <= j) { swap(ref arr[i], ref arr[j]); // swap(arr, i, j); i++; j--; } } while (i <= j); qsort(arr, cmp, a, j); qsort(arr, cmp, i, b); } } public static void Quicksort(T[] arr, IGComparer cmp) { qsort(arr, cmp, 0, arr.Length-1); } public static void CheckSorted(T[] arr, IGComparer cmp) { for (int i=1; i(T v1, T v2); private static void qsort(T[] arr, DGComparer cmp, int a, int b) { // sort arr[a..b] if (a < b) { int i = a, j = b; T x = arr[(i+j) / 2]; do { while (cmp(arr[i], x) < 0) i++; while (cmp(x, arr[j]) < 0) j--; if (i <= j) { swap(ref arr[i], ref arr[j]); // swap(arr, i, j); i++; j--; } } while (i <= j); qsort(arr, cmp, a, j); qsort(arr, cmp, i, b); } } public static void Quicksort(T[] arr, DGComparer cmp) { qsort(arr, cmp, 0, arr.Length-1); } } public class Polyselfsort { private static void swap(T[] arr, int s, int t) { T tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp; } // Polymorphic OO-style quicksort: general, typesafe // Note the type parameter bound in the generic method public static void qsort(T[] arr, int a, int b) where T : IGSelfComparable { // sort arr[a..b] if (a < b) { int i = a, j = b; T x = arr[(i+j) / 2]; do { while (arr[i].CompareTo(x) < 0) i++; while (x.CompareTo(arr[j]) < 0) j--; if (i <= j) { swap(arr, i, j); i++; j--; } } while (i <= j); qsort(arr, a, j); qsort(arr, i, b); } } public static void Quicksort(T[] arr) where T : IGSelfComparable { qsort(arr, 0, arr.Length-1); } } public class Objsort { private static void swap(object[] arr, int s, int t) { object tmp = arr[s]; arr[s] = arr[t]; arr[t] = tmp; } // OO-style IComparable quicksort: general, not typesafe private static void qsort(IComparable[] arr, int a, int b) { // sort arr[a..b] if (a < b) { int i = a, j = b; IComparable x = arr[(i+j) / 2]; do { while (arr[i].CompareTo(x) < 0) i++; while (x.CompareTo(arr[j]) < 0) j--; if (i <= j) { swap(arr, i, j); i++; j--; } } while (i <= j); qsort(arr, a, j); qsort(arr, i, b); } } public static void Quicksort(IComparable[] arr) { qsort(arr, 0, arr.Length-1); } public static void CheckSorted(IComparable[] arr) { for (int i=1; i { int CompareTo(IGComparable that); } public interface IGSelfComparable { // Actually we could assert a bound on the parameter: // public interface IGSelfComparable< T : IGSelfComparable > // but there seems to be no need for that. // Note that the argument type is T itself, not a superclass: int CompareTo(T that); } // An int wrapper that implements all Comparable interfaces public class OrderedInt : IComparable, IGComparable, IGSelfComparable { int i; public OrderedInt(int i) { this.i = i; } public int Value { get { return i; } } // Implements IComparable.CompareTo(object) public int CompareTo(object that) { int thati = ((OrderedInt)that).i; return i < thati ? -1 : i > thati ? +1 : 0; } // Implements IGComparable.CompareTo(IGComparable) public int CompareTo(IGComparable that) { int thati = ((OrderedInt)that).i; return i < thati ? -1 : i > thati ? +1 : 0; } // Implements IGSelfComparable.CompareTo(T) // because with T = OrderedInt we have T : IGSelfComparable public int CompareTo(OrderedInt that) { // Simple subtraction i-that.i won't do because of possible overflow. return i < that.i ? -1 : i > that.i ? +1 : 0; // This following is eight times slower, although the compiler // and runtime knows that i and that.i are ints: // return i.CompareTo(that.i); } } // A string wrapper that implements all Comparable interfaces public class OrderedString : IComparable, IGComparable, IGSelfComparable { string s; public OrderedString(string s) { this.s = s; } public string Value { get { return s; } } // Implements IComparable.CompareTo(object) public int CompareTo(object that) { return string.Compare(this.s, ((OrderedString)that).s); } // Implements IGComparable.CompareTo(IGComparable) public int CompareTo(IGComparable that) { return string.Compare(this.s, ((OrderedString)that).s); } // Implements IGSelfComparable.CompareTo(T) // because with T = OrderedString we have T : IGSelfComparable public int CompareTo(OrderedString that) { return string.Compare(this.s, that.s); } } // A generic version of IComparer public interface IGComparer { int Compare(T v1, T v2); } public interface IIntComparer { int Compare(int v1, int v2); } public class IntComparer : IGComparer, IIntComparer { public int Compare(int v1, int v2) { return v1 < v2 ? -1 : v1 > v2 ? +1 : 0; } } public interface IStringComparer { int Compare(string v1, string v2); } public class StringComparer : IGComparer, IStringComparer { public int Compare(string v1, string v2) { return string.Compare(v1, v2); } } // Try it on integers public class Gsort { static readonly Random rnd = new Random(); static void Main(string[] args) { if (args.Length < 1) Console.Out.WriteLine("Usage: Gsort [string]\n"); else { int N = int.Parse(args[0]); const string fmt = "{0,9:0.00}"; if (args.Length < 2 || args[1] != "string") { Console.Out.WriteLine(" Sorting {0} ints", N); headers(fmt); for (int i=0; i<20; i++) { int[] arr = mkRandomInts(N); Console.Out.Write(fmt, ObjComparable(arr)); Console.Out.Write(fmt, ObjOrderedInt(arr)); Console.Out.Write(fmt, MonoIntPrimitive(arr)); Console.Out.Write(fmt, MonoIntComparer(arr)); Console.Out.Write(fmt, PolyIGComparable(arr)); Console.Out.Write(fmt, PolyIGSelfComparable(arr)); Console.Out.Write(fmt, PolyIGComparer(arr)); Console.Out.Write(fmt, PolyDGComparer(arr)); Console.Out.WriteLine(); } } else { Console.Out.WriteLine(" Sorting {0} strings", N); headers(fmt); for (int i=0; i<20; i++) { string[] arr = mkRandomStrings(N); Console.Out.Write(fmt, ObjComparable(arr)); Console.Out.Write(fmt, ObjOrderedString(arr)); Console.Out.Write(fmt, MonoStringPrimitive(arr)); Console.Out.Write(fmt, MonoStringComparer(arr)); Console.Out.Write(fmt, PolyIGComparable(arr)); Console.Out.Write(fmt, PolyIGSelfComparable(arr)); Console.Out.Write(fmt, PolyIGComparer(arr)); Console.Out.Write(fmt, PolyDGComparer(arr)); Console.Out.WriteLine(); } } } } static void headers(string fmt) { Console.Out.Write(fmt, "general"); Console.Out.Write(fmt, "general"); Console.Out.Write(fmt, "not genl"); Console.Out.Write(fmt, "not genl"); Console.Out.Write(fmt, "general"); Console.Out.Write(fmt, "general"); Console.Out.Write(fmt, "general"); Console.Out.Write(fmt, "general"); Console.Out.WriteLine(); Console.Out.Write(fmt, "not safe"); Console.Out.Write(fmt, "not safe"); Console.Out.Write(fmt, "typesafe"); Console.Out.Write(fmt, "typesafe"); Console.Out.Write(fmt, "not safe"); Console.Out.Write(fmt, "typesafe"); Console.Out.Write(fmt, "typesafe"); Console.Out.Write(fmt, "typesafe"); Console.Out.WriteLine(); Console.Out.Write(fmt, "Comparab"); Console.Out.Write(fmt, "OrderedI"); Console.Out.Write(fmt, "Primitiv"); Console.Out.Write(fmt, "Comparer"); Console.Out.Write(fmt, "GCompara"); Console.Out.Write(fmt, "GSelfCom"); Console.Out.Write(fmt, "IGCompar"); Console.Out.Write(fmt, "DGCompar"); Console.Out.WriteLine(); } // The standard OO thing to do, given that int : IComparable static double ObjComparable(int[] arr) { int n = arr.Length; // Objsort.Quicksort(arr) would be illegal since int[] cannot be // converted to IComparable[], even though int : IComparable. IComparable[] oarr = new IComparable[n]; for (int i=0; i(oarr); // print(oarr); return t.Check(); } static double PolyIGSelfComparable(int[] arr) { int n = arr.Length; OrderedInt[] oarr = new OrderedInt[n]; for (int i=0; i(oarr); // print(oarr); return t.Check(); } static double PolyIGComparer(int[] arr) { int n = arr.Length; int[] narr = new int[n]; for (int i=0; i(narr, new IntComparer()); // print(narr); return t.Check(); } static int intCompare(int v1, int v2) { return v1 < v2 ? -1 : v1 > v2 ? +1 : 0; } static double PolyDGComparer(int[] arr) { int n = arr.Length; int[] narr = new int[n]; for (int i=0; i(narr, new Polysort.DGComparer(intCompare)); // print(narr); return t.Check(); } // Eight ways to sort strings // The standard OO thing to do, given that string : IComparable static double ObjComparable(string[] arr) { int n = arr.Length; // Objsort.Quicksort(arr) would be illegal since string[] cannot be // converted to IComparable[], even though string : IComparable. IComparable[] oarr = new IComparable[n]; for (int i=0; i(oarr); // print(oarr); return t.Check(); } static double PolyIGSelfComparable(string[] arr) { int n = arr.Length; OrderedString[] oarr = new OrderedString[n]; for (int i=0; i(oarr); // print(oarr); return t.Check(); } static double PolyIGComparer(string[] arr) { int n = arr.Length; string[] narr = new string[n]; for (int i=0; i(narr, new StringComparer()); // print(narr); return t.Check(); } static double PolyDGComparer(string[] arr) { int n = arr.Length; string[] narr = new string[n]; for (int i=0; i(narr, new Polysort.DGComparer(string.Compare)); // print(narr); return t.Check(); } // Create arrays of random ints static int[] mkRandomInts(int n) { int[] arr = new int[n]; for (int i=0; igsort 1000000 general general not genl not genl general general general general not safe not safe typesafe typesafe not safe typesafe typesafe typesafe Comparab OrderedI IntPrimi IntCompa GCompara GSelfCom IGCompar DGCompar 4.93 3.06 0.47 1.07 3.09 2.33 1.04 1.84 4.94 3.02 0.46 1.05 3.08 2.32 1.05 1.83 4.96 3.03 0.47 1.03 3.07 2.34 1.03 1.83 4.96 3.03 0.46 1.05 3.07 2.33 1.04 1.83 4.94 3.04 0.46 1.05 3.08 2.33 1.05 1.83 4.95 3.03 0.47 1.04 3.08 2.33 1.05 1.83 4.96 3.03 0.46 1.03 3.07 2.34 1.04 1.83 4.95 3.03 0.46 1.05 3.07 2.33 1.04 1.84 4.95 3.02 0.46 1.04 3.08 2.33 1.04 1.84 4.95 3.03 0.47 1.03 3.09 2.33 1.05 1.83 4.96 3.04 0.46 1.04 3.07 2.33 1.04 1.84 4.95 3.04 0.46 1.05 3.08 2.32 1.05 1.82 4.94 3.03 0.46 1.04 3.07 2.32 1.04 1.83 4.96 3.02 0.47 1.03 3.07 2.34 1.04 1.84 4.96 3.03 0.46 1.04 3.07 2.33 1.04 1.84 4.95 3.04 0.46 1.05 3.08 2.32 1.05 1.84 4.93 3.03 0.46 1.04 3.07 2.33 1.05 1.84 4.96 3.03 0.46 1.04 3.06 2.34 1.04 1.83 4.96 3.03 0.46 1.05 3.06 2.32 1.03 1.83 4.94 3.03 0.46 1.05 3.10 2.33 1.05 1.83 Sixth run, with random strings, 2001-11-01: Sorting 200000 strings general general not genl not genl general general general general not safe not safe typesafe typesafe not safe typesafe typesafe typesafe Comparab OrderedI Primitiv Comparer GCompara GSelfCom IGCompar DGCompar 3.25 2.64 2.14 2.22 2.61 2.58 2.22 2.89 3.12 2.50 2.04 2.13 2.50 2.45 2.12 2.74 3.15 2.54 2.08 2.17 2.55 2.51 2.17 2.81 3.24 2.65 2.15 2.25 2.64 2.61 2.24 2.91 3.16 2.56 2.08 2.17 2.56 2.53 2.17 2.81 3.19 2.58 2.10 2.19 2.58 2.55 2.19 2.84 3.22 2.60 2.11 2.20 2.60 2.54 2.20 2.86 3.09 2.47 2.03 2.11 2.47 2.45 2.10 2.73 3.31 2.74 2.19 2.29 2.70 2.68 2.28 2.96 3.17 2.55 2.09 2.17 2.56 2.51 2.17 2.81 3.14 2.52 2.05 2.14 2.52 2.50 2.15 2.78 3.18 2.60 2.11 2.19 2.58 2.56 2.19 2.83 3.07 2.47 2.01 2.10 2.46 2.42 2.11 2.74 3.29 2.67 2.18 2.27 2.66 2.63 2.26 2.94 3.18 2.58 2.10 2.22 2.56 2.54 2.19 2.84 3.17 2.57 2.09 2.19 2.57 2.53 2.18 2.83 3.09 2.49 2.03 2.12 2.49 2.45 2.11 2.75 3.15 2.53 2.07 2.16 2.54 2.50 2.18 2.83 3.17 2.56 2.08 2.18 2.56 2.52 2.16 2.82 3.33 2.70 2.21 2.39 2.71 2.68 2.32 2.98 Don Syme: · Also I think it’s worth adding an issue regarding IGComparable – the results are slower for this than they could be, because we box one of the integers (the first). Also the terminology “typesafe” could be clarified to “prone to typecheck failures at runtime”, which will mean more to the runtime team. · If it were possible to repeat the sorting examples on (a) strings (b) some value type, e.g. DateTime and (c) some kind of boxed record where you sort on one of the fields then that would be great. Seventh run, with random ints, fixed bbt runtime (RAID 109) 2001-11-06, all sharing enabled, lazy dictionary lookup: Sorting 1000000 ints general general not genl not genl general general general general not safe not safe typesafe typesafe not safe typesafe typesafe typesafe Comparab OrderedI Primitiv Comparer GCompara GSelfCom IGCompar DGCompar 4.93 2.98 0.46 1.03 3.27 2.41 1.11 1.88 5.02 3.11 0.46 1.06 3.15 2.44 1.16 1.91 4.96 3.03 0.45 1.04 3.11 2.42 1.14 1.95 4.98 3.02 0.46 1.03 3.08 2.40 1.13 1.86 5.04 3.13 0.47 1.06 3.18 2.48 1.15 1.94 4.91 3.02 0.45 1.04 3.14 2.41 1.12 1.87 4.92 3.03 0.46 1.04 3.10 2.41 1.14 1.88 5.12 3.22 0.49 1.09 3.24 2.55 1.18 2.00 4.89 3.01 0.46 1.04 3.05 2.39 1.12 1.86 4.92 3.01 0.45 1.03 3.05 2.39 1.12 1.84 5.02 3.12 0.46 1.06 3.19 2.47 1.14 1.90 5.02 3.11 0.48 1.05 3.17 2.46 1.14 1.91 4.97 3.09 0.45 1.05 3.11 2.44 1.13 1.90 4.99 3.09 0.47 1.06 3.14 2.45 1.15 1.89 5.14 3.26 0.51 1.10 3.33 2.58 1.17 2.00 5.06 3.16 0.48 1.08 3.21 2.49 1.16 1.95 4.93 3.02 0.46 1.05 3.09 2.41 1.13 1.88 4.91 3.00 0.45 1.03 3.06 2.39 1.12 1.85 4.97 3.08 0.47 1.06 3.19 2.46 1.14 1.94 5.06 3.18 0.49 1.10 3.23 2.54 1.19 2.00 Eighth run, with random ints, fixed bbt runtime (RAID 109) 2001-11-06, all sharing disabled, no lazy dictionary lookup: Sorting 1000000 ints general general not genl not genl general general general general not safe not safe typesafe typesafe not safe typesafe typesafe typesafe Comparab OrderedI Primitiv Comparer GCompara GSelfCom IGCompar DGCompar 5.01 3.10 0.47 1.05 3.13 2.37 1.07 1.85 4.90 3.00 0.45 1.05 2.99 2.29 1.05 1.81 4.96 3.06 0.46 1.05 3.03 2.32 1.06 1.83 4.96 3.08 0.45 1.05 3.05 2.34 1.05 1.82 4.93 3.03 0.45 1.04 3.01 2.30 1.05 1.81 4.94 3.04 0.47 1.05 3.01 2.31 1.03 1.82 4.99 3.10 0.47 1.06 3.07 2.35 1.07 1.86 4.84 2.94 0.45 1.03 2.90 2.25 1.02 1.80 4.96 3.07 0.47 1.06 3.03 2.31 1.04 1.84 4.96 3.09 0.46 1.05 3.04 2.33 1.04 1.85 4.97 3.10 0.47 1.06 3.06 2.34 1.04 1.83 5.05 3.14 0.47 1.06 3.11 2.38 1.07 1.88 5.06 3.14 0.50 1.07 3.13 2.39 1.08 1.91 5.19 3.29 0.49 1.12 3.23 2.47 1.10 1.96 4.96 3.08 0.45 1.05 3.05 2.32 1.06 1.83 4.95 3.06 0.46 1.06 3.04 2.32 1.05 1.84 4.95 3.05 0.45 1.05 3.03 2.30 1.05 1.82 4.94 3.03 0.45 1.04 3.01 2.30 1.05 1.80 4.97 3.10 0.45 1.05 3.06 2.34 1.05 1.84 4.96 3.08 0.45 1.06 3.06 2.35 1.05 1.86 */