6/18/2015 - 12:33 PM

## Various Sorting Algorithms

Various Sorting Algorithms

``````namespace SortingAlgorithms.Tests
{
using Microsoft.VisualStudio.TestTools.UnitTesting;

[TestClass]
public class SelectionSortTests
{

[TestMethod]
public void TestSelectionSortScenario1()
{
var s = new SelectionSort();

var a = new[] { 2, 3, 4, 7, 5, 1 };
var b = new[] { 1, 2, 3, 4, 5, 7 };
s.Sort(a);

CollectionAssert.AreEqual(a, b);
}

[TestMethod]
public void TestSelectionSortOneElement()
{
var s = new SelectionSort();

var a = new[] { 2 };
var b = new[] { 2 };
s.Sort(a);

CollectionAssert.AreEqual(a, b);
}

[TestMethod]
public void TestSelectionSortTwoElements()
{
var s = new SelectionSort();

var a = new[] { 2, 3 };
var b = new[] { 2, 3 };
s.Sort(a);

CollectionAssert.AreEqual(a, b);
}

[TestMethod]
public void TestSelectionSortBigArray()
{
var s = new SelectionSort();

var a = new int[10000];
var b = new int[10000];
for (int i = 0; i < 10000; i++)
{
a[i] = 9999 - i;
b[i] = i;
}

s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

}

}

``````
``````namespace SortingAlgorithms
{
public class SelectionSort
{
// http://bit.ly/selection_sort
public void SortByUsingASecondArray(int[] a)
{
var b = new int[a.Length];

for (int i = 0; i < a.Length; i++)
{
var min = int.MaxValue;
int indexOfMin = 0;

for (int j = 0; j < a.Length; j++)
{
if (a[j] < min)
{
min = a[j];
indexOfMin = j;
}
}

a[indexOfMin] = int.MaxValue;
b[i] = min;
}
}

public void Sort(int[] a)
{
for (int i = 0; i < a.Length; i++)
{
int min = int.MaxValue;
int indexOfMin = 0;
for (int j = i; j < a.Length; j++)
{
if (a[j] < min)
{
min = a[j];
indexOfMin = j;
}
}

a[indexOfMin] = a[i];
a[i] = min;
}
}
}
}
``````
``````namespace SortingAlgorithms.Tests
{
using Microsoft.VisualStudio.TestTools.UnitTesting;

[TestClass]
public class QuickSortTests
{
[TestMethod]
public void TestQuickSortScenario1()
{
var s = new QuickSort();

var a = new[] { 2, 3, 4, 7, 5, 1 };
var b = new[] { 1, 2, 3, 4, 5, 7 };
s.Sort(a);

CollectionAssert.AreEqual(a, b);
}

[TestMethod]
public void SomeVerySimpleTestForDebugging()
{
var q = new QuickSort();

var a = new[] { 3, 2, 1 };
var b = new[] { 1, 2, 3 };

q.Sort(a);

CollectionAssert.AreEqual(a, b);
}

[TestMethod]
public void TestQuickSortOneElement()
{
var s = new QuickSort();

var a = new[] { 2 };
var b = new[] { 2 };
s.Sort(a);

CollectionAssert.AreEqual(a, b);
}

[TestMethod]
public void TestQuickSortTwoElements()
{
var s = new QuickSort();

var a = new[] { 2, 3 };
var b = new[] { 2, 3 };
s.Sort(a);

CollectionAssert.AreEqual(a, b);
}

[TestMethod]
public void TestQuickSortBigArray()
{
var s = new QuickSort();

var a = new int[10000];
var b = new int[10000];
for (int i = 0; i < 10000; i++)
{
a[i] = 9999 - i;
b[i] = i;
}

s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

}

}``````
``````namespace SortingAlgorithms
{
public class QuickSort
{
// http://bit.ly/quick_sort
public void Sort(int[] a)
{
this.Quick(a, 0, a.Length - 1);
}

private void Quick(int[] a, int startIndex, int endIndex)
{
if (startIndex < endIndex)
{
var indexPivot = this.Partition(ref a, startIndex, endIndex);

this.Quick(a, startIndex, indexPivot - 1);
this.Quick(a, indexPivot + 1, endIndex);
}
}

private int Partition(ref int[] a, int startIndex, int endIndex)
{
var pivot = a[endIndex];
var indexPivot = startIndex;

for (int i = startIndex; i < endIndex; i++)
{
if (a[i] <= pivot)
{
this.Swap(a, i, indexPivot);
indexPivot += 1;
}
}

this.Swap(a, endIndex, indexPivot);

return indexPivot;
}

private void Swap(int[] ints, int i, int j)
{
var temp = ints[i];
ints[i] = ints[j];
ints[j] = temp;
}
}
}``````
``````namespace SortingAlgorithms.Tests
{
using Microsoft.VisualStudio.TestTools.UnitTesting;

[TestClass]
public class MergeSortTests
{

[TestMethod]
public void TestMergeSortScenario1()
{
var s = new MergeSort();

var a = new[] { 2, 3, 4, 7, 5, 1 };
var b = new[] { 1, 2, 3, 4, 5, 7 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestMergeSort3Elements()
{
var s = new MergeSort();

var a = new[] { 2, 4, 3 };
var b = new[] { 2, 3, 4 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestMergeSortOneElement()
{
var s = new MergeSort();

var a = new[] { 2 };
var b = new[] { 2 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestMergeSortTwoElements()
{
var s = new MergeSort();

var a = new[] { 2, 3 };
var b = new[] { 2, 3 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestMergeSortBigArray()
{
var s = new MergeSort();

var a = new int[10000];
var b = new int[10000];
for (int i = 0; i < 10000; i++)
{
a[i] = 9999 - i;
b[i] = i;
}

s.Sort(a);

CollectionAssert.AreEqual(b, a);
}
}
}``````
``````namespace SortingAlgorithms
{
public class MergeSort
{
// http://bit.ly/merge_sort
public void Sort(int[] a)
{
if (a.Length < 2)
{
return;
}

int mid = a.Length / 2;
var left = new int[mid];
var right = new int[a.Length - mid];

for (int i = 0; i < mid; i++)
{
left[i] = a[i];
}

for (int i = mid; i < a.Length; i++)
{
right[i - mid] = a[i];
}

this.Sort(left);
this.Sort(right);
this.MergeTwoSortedArrays(left, right, a);
}

private void MergeTwoSortedArrays(int[] left, int[] right, int[] merged)
{
int i = 0;
int j = 0; // left unpicked index
int k = 0; // right unpicked index

while (i < left.Length && j < right.Length)
{
if (left[i] < right[j])
{
merged[k] = left[i];
i++;
}
else
{
merged[k] = right[j];
j++;
}
k++;
}

while (i < left.Length)
{
merged[k] = left[i];
i++;
k++;
}

while (j < right.Length)
{
merged[k] = right[j];
j++;
k++;
}
}
}
}``````
``````namespace SortingAlgorithms.Tests
{
using Microsoft.VisualStudio.TestTools.UnitTesting;

[TestClass]
public class InsertionSortTests
{
[TestMethod]
public void TestInsertionSortScenario1()
{
var s = new InsertionSort();

var a = new[] { 2, 3, 4, 7, 5, 1 };
var b = new[] { 1, 2, 3, 4, 5, 7 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestInsertionSort3Elements()
{
var s = new InsertionSort();

var a = new[] { 2, 4, 3 };
var b = new[] { 2, 3, 4 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestInsertionSortOneElement()
{
var s = new InsertionSort();

var a = new[] { 2 };
var b = new[] { 2 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestInsertionSortTwoElements()
{
var s = new InsertionSort();

var a = new[] { 2, 3 };
var b = new[] { 2, 3 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestInsertionSortBigArray()
{
var s = new InsertionSort();

var a = new int[10000];
var b = new int[10000];
for (int i = 0; i < 10000; i++)
{
a[i] = 9999 - i;
b[i] = i;
}

s.Sort(a);

CollectionAssert.AreEqual(b, a);
}
}
}
``````
``````namespace SortingAlgorithms
{
public class InsertionSort
{
// http://bit.ly/insertion_sort
public void Sort(int[] a)
{
for (int i = 1; i <= a.Length - 1; i++)
{
int myNumber = a[i];
int k = i - 1;

while ((k >= 0) && (a[k] > myNumber))
{
a[k + 1] = a[k];
k--;
}

a[k + 1] = myNumber;
}

}
}
}
``````
``````namespace SortingAlgorithms.Tests
{
using Microsoft.VisualStudio.TestTools.UnitTesting;

[TestClass]
public class BubbleSortTests
{
[TestMethod]
public void TestBubbleSortScenario1()
{
var s = new BubbleSort();

var a = new[] { 2, 3, 4, 7, 5, 1 };
var b = new[] { 1, 2, 3, 4, 5, 7 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestBubbleSortOneElement()
{
var s = new BubbleSort();

var a = new[] { 2 };
var b = new[] { 2 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestBubbleSortTwoElements()
{
var s = new BubbleSort();

var a = new[] { 2, 3 };
var b = new[] { 2, 3 };
s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

[TestMethod]
public void TestBubbleSortBigArray()
{
var s = new BubbleSort();

var a = new int[10000];
var b = new int[10000];
for (int i = 0; i < 10000; i++)
{
a[i] = 9999 - i;
b[i] = i;
}

s.Sort(a);

CollectionAssert.AreEqual(b, a);
}

}
}
``````
``````namespace SortingAlgorithms
{
public class BubbleSort
{
// http://bit.ly/bubble_sort
public void Sort(int[] a)
{
for (int k = 0; k < a.Length - 1; k++)
{
bool isSorted = true;
for (int i = 0; i <= a.Length - k - 2; i++)
{
if (a[i] > a[i + 1])
{
Util.Swap(ref a[i], ref a[i + 1]);
isSorted = false;
}
}

if (isSorted)
{
return;
}
}
}
}
}``````

Introduction to sorting algorithms, implemented in C#