Exploring radix sort. Radix sort has the reputation of being the fastest algorithm to sort through millions of integers in the computing literature. It has a complexity of 
where 
is the number of elements, and 
is the element’s length.
I modified the version on the Wikipedia to use binary representation to sort the unsigned integers. Here is my version in C#:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
public static class RadixSort { /// <summary> /// Binary Radix Sort /// </summary> /// <param name="unorderedArray">Array that contains unordered elements.</param> /// <param name="nbOfBits">Number of bits for the elements. uint represents global::System.UInt32, therefore default to 32.</param> /// <returns></returns> public static uint[] BinarySort(uint[] unorderedArray, uint nbOfBits = 32) { //make a copy of the unorderedArray uint[] orderedArray = new uint[unorderedArray.Length]; unorderedArray.CopyTo(orderedArray, 0); const int BASE = 2;//binary int[] bucket = new int[BASE]; for (int bit = 0; bit < nbOfBits; bit++) { //init bucket bucket[0] = bucket[1] = 0; //Count the number of keys that will go into each bucket for (int i = 0; i < unorderedArray.Length; i++) bucket[GetBitValueAtPosition(bit, unorderedArray[i])]++; //Add the count of the previous buckets to acquire the indexes after the end of each bucket location in the array bucket[1] += bucket[0]; //Starting at the end of the list, get the index corresponding to the unorderedArray[i]'s key, decrement it, and use it to place unorderedArray[i] into array orderedArray. for (int i = unorderedArray.Length - 1; i >= 0; i--) orderedArray[--bucket[GetBitValueAtPosition(bit, unorderedArray[i])]] = unorderedArray[i]; //Copy array orderedArray to array unorderedArray orderedArray.CopyTo(unorderedArray, 0); } return orderedArray; } /// <summary> /// Get the bit value of the input at bitPosition-th bit. /// E.G.: /// input = 10001001b = 137 /// ^^^^^^^^ /// bitPosition => 76543210 /// - If bitPosition = 3, the returned value is 1. /// - If bitPosition = 4, the returned value is 0. /// - Etc. /// The returned value is either 0 or 1. /// </summary> /// <param name="bitPosition">Zero-based position.</param> /// <param name="input">Data value.</param> /// <returns></returns> private static long GetBitValueAtPosition(int bitPosition, uint input) { return ((1 << bitPosition) & input) >> bitPosition; } } |