Generic implementation of sorting algorithms and using Strategy pattern - Part 3

After implementation of the Insertion and Shell Sort, this article explains the implementation of the other three famous sorting algorithms (Merge sort, Heap sort and Quick sort).

Merge Sort

Merge sort works by comparing every two elements and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Merge sort uses recursion for sorting the list.

The implementation of MergeSorter class

public class MergeSorter where T : IComparable

{

List tempList;

public List Sort(IEnumerable input)

{

List inputItems = new List(input);

tempList = new List(inputItems.Count);

for (int i = 0; i <>

tempList.Add(default(T));

MergeSort(ref inputItems, 0, inputItems.Count - 1);

return inputItems;

}

private void Merge(ref List inputList, int left, int middle, int right)

{

int i;

int j;

for (i = middle + 1; i > left; i--)

{

tempList[i - 1] = inputList[i - 1];

}

for (j = middle; j <>

{

tempList[right + middle - j] = inputList[j + 1];

}

for (int k = left; k <= right; k++)

{

// Less Than

if (tempList[j].CompareTo(tempList[i]) == -1)

{

inputList[k] = tempList[j--];

}

else

{

inputList[k] = tempList[i++];

}

}

}

private void MergeSort(ref List a, int left, int right)

{

if (right <= left) return;

int middle = (right + left) / 2;

//recursive sorting

MergeSort(ref a, left, middle);

MergeSort(ref a, middle + 1, right);

Merge(ref a, left, middle, right);

}

}

Heap Sort

The heap sort works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a binary tree (heap). Once the data list has been made into a heap, the root node is guaranteed to be the largest element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root.

The implementation of HeapSorter class

public class HeapSorter where T : IComparable

{

public List Sort(IEnumerable input)

{

List inputItems = new List(input);

HeapSort(ref inputItems, 0, inputItems.Count - 1);

return inputItems;

}

private void HeapSort(ref List items, Int32 start, Int32 end)

{

int left = start + ((end - start) >> 1);

int right = end;

int offset = start;

while (left >= start)

{

SiftDown(items, offset, left, end);

left -= 1;

}

while (right > start)

{

Swap(items, right, start);

right -= 1;

SiftDown(items, offset, start, right);

}

}

private void SiftDown (List inputItems, int offset, int start, int end)

{

int root = start;

int child;

while (((root - offset) * 2 + 1) <= (end - offset))

{

child = ((root - offset) * 2 + 1) + offset;

if (child <>

{

child += 1;

}

if (inputItems[root].CompareTo(inputItems[child]) <>

{

Swap(inputItems, root, child);

root = child;

}

else

{

break;

}

}

}

private void Swap (List inputItems, int i, int k)

{

T swap = inputItems[i];

inputItems[i] = inputItems[k];

inputItems[k] = swap;

}

}

Quick Sort

Quick sort uses the algorithm that partitions an array to choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. It then uses recursion to follow the same algorithm to finally create a sorted list of elements.

The implementation of QuickSorter class

public class QuickSorter where T : IComparable

{

public List Sort(IEnumerable input)

{

List sorteditems = new List(input);

QuickSort(ref sorteditems, 0, sorteditems.Count - 1);

return sorteditems;

}

private void QuickSort(ref List sortedItems, int left, int right)

{

if (right <= left) return;

int i = Partition(ref sortedItems, left, right);

QuickSort(ref sortedItems, left, i - 1);

QuickSort(ref sortedItems, i + 1, right);

}

private int Partition(ref List a, int l, int r)

{

T tmp;

int i = l - 1;

int j = r;

T v = a[r]; for (; ; )

{

while (a[++i].CompareTo(v) == -1)

{

}

while (v.CompareTo(a[--j]) == -1)

{

if (j == l) break;

}

if (i >= j) break;

tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}

a[r] = a[i];

a[i] = v;

return i;

}

}

In the next series of this article, i will show how to use strategy pattern to select the sorting algorithms we have implemented.