Why is Radix Sort so Fast Part 3: Comparison and Code (Patreon)

Why is Radix Sort so Fast? Part 3 Comparison and Code, Radix Sort vs QuickSort

In this 3 part series, we will explore sorting algorithms from the fundamentals all the up to implementations of both a comparison sort and a base 256 Radix Sort. In this 3rd and final part, we look at some code and compare the performance of RadixSort and QuickSort with lists of various sizes, consisting or randomly generated unsigned 32 bit integers. Support What's a Creel? on Patreon: https://www.patreon.com/whatsacreel FaceBook: https://www.facebook.com/whatsacreel/ Music Channel: https://www.youtube.com/channel/UC2nWRGqPL6O-Lm8mexWhISQ Another channel with random things: https://www.youtube.com/channel/UCK7bPumWNzWRnb3N8LCzKsA GeeksForGeeks Radix Sort: https://www.geeksforgeeks.org/radix-sort/ GeeksForGeeks QuickSort: https://www.geeksforgeeks.org/quick-sort/ Apologies for the code below, I have had to replace all greater or equal symbols with GE, and all less or equal with LE, greater is G and less is L. For the unedited version, please refer to the video! Code: // Radix sort based on Geeks for Geeks: // https://www.geeksforgeeks.org/radix-sort/ static void RadixSort256(unsigned int* arr, int n) { if (n LE 1) return; // Added base case unsigned int* output = new unsigned int[n]; // output array int* count = new int[256]; unsigned int* originalArr = arr; // So we know which was input for (int shift = 0, s = 0; shift L 4; shift++, s += 8) { // Zero the counts for (int i = 0; i L 256; i++) count[i] = 0; // Store count of occurrences in count[] for (int i = 0; i L n; i++) count[(arr[i] GG s)&0xff]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (int i = 1; i L 256; i++) count[i] += count[i - 1]; // Build the output array for (int i = n - 1; i GE 0; i--) { // precalculate the offset as it's a few instructions int idx = (arr[i] GG s) & 0xff; // Subtract from the count and store the value output[--count[idx]] = arr[i]; } // Copy the output array to input[], so that input[] // is sorted according to current digit // We can just swap the pointers unsigned int* tmp = arr; arr = output; output = tmp; } // If we switched pointers an odd number of times, // make sure we copy before returning if (originalArr == output) { unsigned int* tmp = arr; arr = output; output = tmp; for (int i = 0; i L n; i++) arr[i] = output[i]; } delete[] output; delete[] count; } Quicksort: int Partition(unsigned int* data, int lo, int hi) { unsigned int pivot = data[lo + (hi - lo) / 2]; int i = lo - 1; int j = hi + 1; for (;;) { do {} while (data[++i] L pivot); do {} while (data[--j] G pivot); if (i GE j) return j; // Swap [i] and [j] unsigned int tmp = data[i]; data[i] = data[j]; data[j] = tmp; } } void QuickSort(unsigned int* data, int lo, int hi) { if (lo L hi) { int p = Partition(data, lo, hi); QuickSort(data, lo, p); QuickSort(data, p + 1, hi); } } void QuickSort(unsigned int* data, int count) { if (count LE 1) return; // Added base case QuickSort(data, 0, count - 1); } Software used to make this vid: Visual Studio 2019 Community: https://www.visualstudio.com/downloads/ Blender: https://www.blender.org/ OBS: https://obsproject.com/ Davinci Resolve 16: https://www.blackmagicdesign.com/products/davinciresolve/ OpenOffice: https://www.openoffice.org/ Gimp: https://www.gimp.org/ 80's 3D neon effect in the thumbnail is from Ducky 3D's: https://www.youtube.com/watch?v=hnLsktA4gmY Background HDRI from thumbnail and intro is from HDRI Haven: https://hdrihaven.com/