Skip to content

Commit 257dad1

Browse files
joshimoojoshimoo
committed
Implemented Counting Sort in C#, tried to optimize the default implementation to also work on negative entries.
Also testing out Code Contracts.
1 parent 4dd27e9 commit 257dad1

2 files changed

Lines changed: 197 additions & 0 deletions

File tree

‎Counting_Sort/C#/joshimoo/CountingSort.cs‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Diagnostics.Contracts;
4+
using System.Linq;
5+
using System.Text;
6+
using System.Threading.Tasks;
7+
8+
namespace JamLib.Algorithms.Sorting.OtherSorts
9+
{
10+
public static class CountingSort
11+
{
12+
public static int[] Sort(IList<int> data)
13+
{
14+
int min = int.MaxValue;
15+
int max = int.MinValue;
16+
17+
for (int i = 0; i < data.Count; i++)
18+
{
19+
int element = data[i];
20+
if (element < min) { min = element; }
21+
if (element > max) { max = element; }
22+
}
23+
24+
return Sort(data, min, max);
25+
}
26+
27+
28+
/// <summary>
29+
/// The default implementation which creates a work array from 0 to max
30+
/// Only works with positive numbers
31+
/// </summary>
32+
public static int[] Sort(IList<int> data, int max)
33+
{
34+
Contract.Requires(data != null && Contract.ForAll(data, i => i >= 0));
35+
Contract.Requires(max >= 0 && max == data.Max());
36+
37+
int[] count = new int[max + 1];
38+
int[] sorted = new int[data.Count];
39+
40+
// Add the elements in order small --> big
41+
foreach (int key in data)
42+
{
43+
count[key] += 1;
44+
}
45+
46+
// Transfer the temp array to the sorted array from small --> big
47+
int sortedIndex = 0;
48+
for (int number = 0; number < count.Length; number++)
49+
{
50+
// How often did we have this number in the input?
51+
for (int j = 0; j < count[number]; j++)
52+
{
53+
sorted[sortedIndex++] = number;
54+
}
55+
}
56+
57+
return sorted;
58+
}
59+
60+
61+
/// <summary>
62+
/// I feel like this way is a little bit more optimized since it saves space
63+
/// there is still the possibility of empty space beetwen min,max
64+
/// but atleast it gets rid of the space from 0 to min
65+
///
66+
/// This will also work with negative numbers.
67+
/// </summary>
68+
public static int[] Sort(IList<int> data, int min, int max)
69+
{
70+
Contract.Ensures(data != null, "data cannot be a null pointer");
71+
Contract.Ensures(min == data.Min(), "wrong min submitted");
72+
Contract.Ensures(max == data.Max(), "wrong max submitted");
73+
74+
int[] count = new int[(max - min) + 1];
75+
int[] sorted = new int[data.Count];
76+
77+
// Add the elements in reverse order big --> small
78+
// NOTE: Could do key - min instead for order small --> big
79+
foreach (int key in data)
80+
{
81+
count[max - key] += 1;
82+
}
83+
84+
// Transfer the temp array to the sorted array from small --> big
85+
int sortedIndex = data.Count - 1;
86+
for (int i = 0; i < count.Length; i++)
87+
{
88+
// How often did we have this number in the input?
89+
int number = max - i;
90+
for (int j = 0; j < count[i]; j++)
91+
{
92+
sorted[sortedIndex--] = number;
93+
}
94+
}
95+
96+
return sorted;
97+
}
98+
99+
}
100+
}

‎Counting_Sort/C#/joshimoo/CountingSortTests.cs‎

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
using System.Linq;
2+
using JamLib.Algorithms.Sorting.OtherSorts;
3+
using Microsoft.VisualStudio.TestTools.UnitTesting;
4+
5+
namespace JamLib.Algorithms.Sorting.OtherSorts.Tests
6+
{
7+
[TestClass()]
8+
public class CountingSortTests
9+
{
10+
[TestMethod()]
11+
public void SortEmptyTest()
12+
{
13+
int[] data = new int[] { };
14+
int[] expected = new int[] { };
15+
var result = CountingSort.Sort(data);
16+
17+
CollectionAssert.AreEqual(expected, result, "CountingSort did not sort correctly");
18+
}
19+
20+
[TestMethod()]
21+
public void SortEmptyWrongMinMaxTest()
22+
{
23+
int[] data = new int[] { };
24+
int[] expected = new int[] { };
25+
26+
// Trying the test with a wrong min/max count
27+
var result = CountingSort.Sort(data, 8, 10);
28+
29+
CollectionAssert.AreEqual(expected, result, "CountingSort did not sort correctly");
30+
}
31+
32+
[TestMethod()]
33+
public void SortEmptyWrongMaxTest()
34+
{
35+
int[] data = new int[] { };
36+
int[] expected = new int[] { };
37+
38+
// Trying the test with a wrong max count
39+
var result = CountingSort.Sort(data, 20);
40+
41+
CollectionAssert.AreEqual(expected, result, "CountingSort did not sort correctly");
42+
}
43+
44+
[TestMethod()]
45+
public void SortNegativeMaxTest()
46+
{
47+
int[] data = new int[] { -11, -10, 0, 2, 2 };
48+
int[] expected = new int[] { -11, -10, 0, 2, 2 };
49+
50+
// Trying the test with a Negative max count
51+
var result = CountingSort.Sort(data, 2);
52+
53+
CollectionAssert.AreEqual(expected, result, "CountingSort did not sort correctly");
54+
}
55+
56+
[TestMethod()]
57+
public void SortNegativeTest()
58+
{
59+
int[] data = new int[] { 0, 8, 8, -2, 5, 5, 5, 1, 2, 3, -1, -1, 4, 4, 4, 10 };
60+
int[] expected = new int[] { -2, -1, -1, 0, 1, 2, 3, 4, 4, 4, 5, 5, 5, 8, 8, 10 };
61+
var result = CountingSort.Sort(data);
62+
63+
CollectionAssert.AreEqual(expected, result, "CountingSort did not sort correctly");
64+
}
65+
66+
[TestMethod()]
67+
public void SortTest()
68+
{
69+
int[] data = new int[] { 8, 8, 5, 5, 5, 1, 2, 3, 4, 4, 4, 10 };
70+
int[] expected = new int[] { 1, 2, 3, 4, 4, 4, 5, 5, 5, 8, 8, 10 };
71+
var result = CountingSort.Sort(data);
72+
73+
CollectionAssert.AreEqual(expected, result, "CountingSort did not sort correctly");
74+
}
75+
76+
[TestMethod()]
77+
public void SortMinMaxTest()
78+
{
79+
int[] data = new int[] { 8, 8, 5, 5, 5, 1, 2, 3, 4, 4, 4, 10 };
80+
int[] expected = new int[] { 1, 2, 3, 4, 4, 4, 5, 5, 5, 8, 8, 10 };
81+
var result = CountingSort.Sort(data, data.Min(), data.Max());
82+
83+
CollectionAssert.AreEqual(expected, result, "CountingSort did not sort correctly");
84+
}
85+
86+
[TestMethod()]
87+
public void SortMaxTest()
88+
{
89+
int[] data = new int[] { 8, 8, 5, 5, 5, 1, 2, 3, 4, 4, 4, 10 };
90+
int[] expected = new int[] { 1, 2, 3, 4, 4, 4, 5, 5, 5, 8, 8, 10 };
91+
var result = CountingSort.Sort(data, data.Max());
92+
93+
CollectionAssert.AreEqual(expected, result, "CountingSort did not sort correctly");
94+
}
95+
96+
}
97+
}

0 commit comments

Comments
 (0)