Common Sorting Algorithms

Question

Here I've prepared my solutions for the following algorithms, and was curious if there were a way to optimize any of them. Any input is welcome and appreciated!

using System; using System.Collections.Generic; using System.Linq; namespace algotest { class Program { static void InsertionSort(int[] arr) { for (int i = 1; i < arr.Length; ++i) { int temp = arr[i]; bool sorted = false; for (int j = i - 1; j >= 0 && !sorted;) { if (temp < arr[j]) { arr[j + 1] = arr[j]; --j; arr[j + 1] = temp; } else { sorted = true; } } } } static void BubbleSort(int[] arr) { int temp = 0; for (int i = 0; i < arr.Length; ++i) { for (int j = 0; j < arr.Length - 1; ++j) { if (arr[j] > arr[j + 1]) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } } static void SelectionSort(int[] arr) { int temp, min; for (int i = 0; i < arr.Length - 1; ++i) { min = i; for (int j = i + 1; j < arr.Length; ++j) { if (arr[j] < arr[min]) { min = j; } } temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } static void Merge(int[] arr, int left, int pivot, int right) { int[] temp = new int[25]; int index = left; int leftBound = pivot - 1; int length = right - left + 1; while (left <= leftBound && pivot <= right) { if (arr[left] <= arr[pivot]) { temp[index++] = arr[left++]; } else { temp[index++] = arr[pivot++]; } } while (left <= leftBound) { temp[index++] = arr[left++]; } while (pivot <= right) { temp[index++] = arr[pivot++]; } for (int i = 0; i < length; i++) { arr[right] = temp[right]; right--; } } static void MergeSort(int[] arr, int left, int right) { if (right > left) { int pivot = (right + left) / 2; MergeSort(arr, left, pivot); MergeSort(arr, pivot + 1, right); Merge(arr, left, pivot + 1, right); } } static void QuickSort(int[] arr, int left, int right) { int i = left, j = right; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr[i].CompareTo(pivot) < 0) { ++i; } while (arr[j].CompareTo(pivot) > 0) { --j; } if (i <= j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; ++i; --j; } } if (left < j) { QuickSort(arr, left, j); } if (i < right) { QuickSort(arr, i, right); } } static void Heapify(int[] arr, int i, int n) { try { int temp = arr[i]; int j = 2 * i; while (j <= n) { if (j < n && arr[j] < arr[j + 1]) { j++; } if (temp >= arr[j]) { break; } arr[j / 2] = arr[j]; j *= 2; } arr[j / 2] = temp; } catch (IndexOutOfRangeException err) { Console.WriteLine("Array Out of Bounds ", err); } } static void HeapSort(int[] arr) { for (int i = arr.Length / 2; i >= 0; --i) { Heapify(arr, i, arr.Length - 1); } for (int i = arr.Length - 2; i >= 0; --i) { int temp = arr[i + 1]; arr[i + 1] = arr[0]; arr[0] = temp; Heapify(arr, 0, i); } } static void CountingSort(int[] arr) { int[] count = new int[arr.Max() + 1]; for (int i = 0; i < arr.Length; ++i) { ++count[arr[i]]; } int j = 0; for (int i = 0; i < count.Length; ++i) { for (int k = 0; k < count[i]; ++k) { arr[j++] = i; } } } static void RadixSort(int[] arr) { int i, j; int[] temp = new int[arr.Length]; for (int shift = 31; shift > -1; --shift) { j = 0; for (i = 0; i < arr.Length; ++i) { bool move = (arr[i] << shift) >= 0; if (shift == 0 ? !move : move) { arr[i - j] = arr[i]; } else { temp[j++] = arr[i]; } } Array.Copy(temp, 0, arr, arr.Length - j, j); } } static void BucketSort(int[] arr) { // bucket size key: // array 1-99 ; 10 buckets // arrat 100-199 ; 20 buckets // etc. // TODO: Implement logic to determine bucket size? int numOfBuckets = 10; List<int> result = new List<int>(); List<int>[] buckets = new List<int>[numOfBuckets]; for (int i = 0; i < numOfBuckets; ++i) { buckets[i] = new List<int>(); } for (int i = 0; i < arr.Length; ++i) { int index = arr[i] / numOfBuckets; buckets[index].Add(arr[i]); } for (int i = 0; i < numOfBuckets; ++i) { int[] temp = buckets[i].ToArray(); InsertionSort(arr); result.AddRange(temp); } arr = result.ToArray(); } static void Main(string[] args) { Console.WriteLine("Please select an algorithm: "); Console.WriteLine("I : InsertionSort O(n^2)"); Console.WriteLine("B : BubbleSort O(n^2)"); Console.WriteLine("S : SelectionSort O(n^2)"); Console.WriteLine("M : MergeSort O(nlgn)"); Console.WriteLine("Q : QuickSort O(nlgn)"); Console.WriteLine("H : HeapSort O(nlgn)"); Console.WriteLine("C : CountingSort O(n)"); Console.WriteLine("R : RadixSort O(n)"); Console.WriteLine("U : BucketSort O(n)"); string algorithm = Console.ReadLine().ToUpper(); Console.WriteLine("How many elements?"); int numOfElements = int.Parse(Console.ReadLine()); int[] arr = new int[numOfElements]; Random rand = new Random(); Console.WriteLine("Generating random data..."); for (int i = 0; i < numOfElements; ++i) { arr[i] = rand.Next(100); } switch (algorithm) { case "I": InsertionSort(arr); break; case "B": BubbleSort(arr); break; case "S": SelectionSort(arr); break; case "M": MergeSort(arr, 0, arr.Length - 1); break; case "Q": QuickSort(arr, 0, arr.Length - 1); break; case "H": HeapSort(arr); break; case "C": CountingSort(arr); break; case "R": RadixSort(arr); break; case "U": BucketSort(arr); break; } for (int i = 0; i < arr.Length; ++i) { Console.WriteLine(arr[i]); } Console.WriteLine("Press any key to exit."); Console.ReadKey(); } } } 

Answer 1

Insertion sort

You don't need the flag variable sorted. Instead of sorted = true, you can simply break out of the loop.

Many times flag variables can be avoided, and result in simpler, more readable solutions. Always look suspiciously at flag variables.

Merge sort

The number 25 in int[] temp = new int[25] looks arbitrary. Why is it 25?

Note that this may lead to integer overflow, a common pitfall in merge sort implementations:

int pivot = (right + left) / 2; 

The fix is simple enough:

int pivot = left + (right - left) / 2; 

Counting sort

The implementation allocates an array of size arr.Max() + 1 as storage. It would be good to also take into account arr.Min(), to avoid allocating much more space than necessary.

Furthermore, the current implementation will crash if the input contains negative numbers. That's another reason to consider arr.Min() too.

Answer 2

Insertion sort

You appear to be writing the moving element repeatedly, which isn't needed, and as mentioned there is a sorted flag you don't need, so you can break out of the loop to place the moving element.

 static void InsertionSort(int[] arr) { for (int i = 1; i < arr.Length; ++i) { int temp = arr[i]; int j = i - 1; while (j >= 0) { if (temp >= arr[j]) break; // found insertion point arr[j + 1] = arr[j]; --j; } arr[j + 1] = temp; } } 

Bubble sort

Normally bubble sort refers to swapping adjacent elements. It can be optimized by tracking the last swap.

 static void BubbleSort(int[] arr) { int endPt = arr.Length - 1; while (endPt > 0) { int lastSwap = 0; for (int j = 0; j < endPt; ++j) { if (arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; lastSwap = j; } } endPt = lastSwap; } } 

Selection sort

No issues, although you have variables declared a little further from their point of use than in the previous routines.

... I might look at some more later.