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

Most of the day to day applications we deal with contain a Sorting implementation of collections. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly. In this article series I will explain implementation of various sorting algorithms in C# using generics and finally a strategy pattern implementation to switch to a particular algorithm based on the requirement.

Bubble Sort

Bubble sort is a comparison sort that works by repeatedly stepping through the list of items to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Implementation

I have my BubbleSorter class implementation as

public class BubbleSorter where T : IComparable

{

public List Sort(IEnumerable input)

{

List sortItems = new List(input);

Int32 right = sortItems.Count - 1;

do

{

Int32 lastSwap = 0;

for (Int32 i = 0; i <>

{

if (sortItems[i].CompareTo(sortItems[i + 1]) > 0)

{

T temp = sortItems[i];

sortItems[i] = sortItems[i + 1];

sortItems[i + 1] = temp;

lastSwap = i;

}

}

right = lastSwap;

}

while (right > 0);

return sortItems;

}

}

Selection Sort

Selection sort is a simple sorting algorithm that improves on the performance of bubble sort. It works by first finding the smallest element by scanning the entire list and moving it into the first position, then finding the second smallest element by scanning the remaining elements, and so on.

The implementation of SelectionSorter class

public class SelectionSorter where T : IComparable

{

public List Sort(IEnumerable input)

{

List inputItems = new List(input);

for (Int32 sortedSize = 0; sortedSize <>

{

Int32 minElementIndex = sortedSize;

T minElementValue = inputItems[sortedSize];

for (Int32 i = sortedSize + 1; i <>

{

if (inputItems[i].CompareTo(minElementValue) <>

{

minElementIndex = i;

minElementValue = inputItems[i];

}

}

inputItems[minElementIndex] = inputItems[sortedSize];

inputItems[sortedSize] = minElementValue;

}

return inputItems;

}

}

In the next part of the series we will see how to implement insertion and shell sort.