Common Sorting Algorithms

Posted on

Problem

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();
}
}
}
``````

Solution

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.

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.