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.