Count sort is very good to sort sequence of integer which has small range of values (in comparison with sequence length). Due to two assumptions - our sequence contains only integers and its values range is much less than amount of items in sequence, it's linear in time to the amount of items in input. It's much better than classic algorythms based on comparison, cause it doesn't use comparison in its work, so it overcomes traditional for comparing algorythms O(nlogn).
Here is an implementation:
Show/Hide
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CountSort
{
public class SortManager
{
public int[] Sort(int[] data)
{
int max = 0;
int min = 0;
// get min and max elements of input array to get borders of counting array
GetMaxMin(data, out min, out max);
// declare sorting array
int[] metaCount = new int[max + 1 - min];
// count amount of each item in iput
foreach (int d in data)
{
metaCount[d - min]++;
}
// rebuild sorting array to get end position of each item in sorted output
for (int i = 1; i < metaCount.Length; i++)
{
metaCount[i] += metaCount[i - 1];
}
int[] returnValue = new int[data.Length];
// just fill output array
int currentInsertPosition = 0;
for (int i = 0; i < metaCount.Length; i++)
{
for (; currentInsertPosition < metaCount[i]; currentInsertPosition++)
{
returnValue[currentInsertPosition] = i + min;
}
}
return returnValue;
}
void GetMaxMin(int[] data, out int min, out int max)
{
if (data.Length == 1)
{
min = data[0];
max = data[0];
return;
}
decimal mediana = data.Length / 2;
int[] left = new int[(int)Math.Floor(mediana)];
int[] right = new int[data.Length - left.Length];
for (int i = 0; i < left.Length; i++)
{
left[i] = data[i];
}
for (int i = 0; i < right.Length; i++)
{
right[i] = data[i + left.Length];
}
int leftMin = 0;
int leftMax = 0;
int rightMin = 0;
int rightMax = 0;
GetMaxMin(left, out leftMin, out leftMax);
GetMaxMin(right, out rightMin, out rightMax);
min = leftMin < rightMin ? leftMin : rightMin;
max = leftMax > rightMax ? leftMax : rightMax;
}
}
}
and of course some test for you:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using NUnit;
using NUnit.Framework;
namespace CountSort.Fixture
{
public class SortManagerTest
{
[Test]
public void TestFromZero()
{
SortManager manager = new SortManager();
int[] data = new[] { 1, 3, 0, 2, 1, 4, 3, 0, 2, 4, 2, 4, 3, 2, 1, 0 };
int[] sorted = manager.Sort(data);
checkSort(data, sorted);
}
[Test]
public void TestFromLessZero()
{
SortManager manager = new SortManager();
int[] data = new[] { 1, 3, 0, -1, 2, 1, 4, 3, 0, -1, -2 ,2, 4, 2, 4, -2, 3, -1, 2, 1, 0 };
int[] sorted = manager.Sort(data);
checkSort(data, sorted);
}
[Test]
public void TestFromGreatZero()
{
SortManager manager = new SortManager();
int[] data = new[] { 1, 3, 5, 1, 2, 1, 4, 3, 5, 11, 2, 2, 4, 2, 4, 2, 3, 1, 2, 1, 6 };
int[] sorted = manager.Sort(data);
checkSort(data, sorted);
}
[Test]
public void TestWithSpaces()
{
SortManager manager = new SortManager();
int[] data = new[] { 3, 3, 1, 1, 3, 5, 3, 1, 5, 6, 3, 1 };
int[] sorted = manager.Sort(data);
checkSort(data, sorted);
}
void checkSort(int[] input, int[] output)
{
// check both arrays have equal amount of items
Assert.AreEqual(output.Length, input.Length);
// check for sort
for (int i = 1; i < output.Length; i++)
{
Assert.IsTrue(output[i - 1] <= output[i]);
}
// check no new items in output
for (int i = 0; i < output.Length; i++)
{
bool isInInput = false;
foreach (int inp in input)
{
if (output[i] == inp)
{
isInInput = true;
break;
}
}
Assert.IsTrue(isInInput);
}
// check no items lost
for (int i = 0; i < input.Length; i++)
{
bool isInOutput = false;
foreach (int outp in output)
{
if (input[i] == outp)
{
isInOutput = true;
break;
}
}
Assert.IsTrue(isInOutput);
}
// check sum
int sumInput = 0;
for (int i = 0; i < input.Length; i++)
{
sumInput += input[i];
}
int sumOutput = 0;
for (int i = 0; i < output.Length; i++)
{
sumOutput += output[i];
}
Assert.AreEqual(sumInput, sumOutput);
}
}
}
