Wednesday, July 16, 2008

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

In the previous article we saw the implementation of two simple and common sorting algorithms (Bubble sort and Selection sort). In this post we will see the next two sorting algorithm implementations in C#.


Insertion Sort

Insertion sort works by taking elements from the list one by one and inserting them in their correct position into a new sorted list.

The implementation of InsertionSorter class

public class InsertionSorter where T : IComparable

{

public List Sort(IEnumerable input)

{

List inputItems = new List(input);

Int32 increment;

Int32 swapPosition;

Int32 x = inputItems.Count;

T currIndex;

for (increment = 1; increment <>

{

currIndex = inputItems[increment];

swapPosition = increment;

while ((swapPosition > 0) && (inputItems[swapPosition - 1].CompareTo(currIndex) == 1))

{

inputItems[swapPosition] = inputItems[swapPosition - 1];

swapPosition = swapPosition - 1;

}

inputItems[swapPosition] = currIndex;

}

return inputItems;

}

}

Shell Sort

Shell sort improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. The shell sort is more than 5 times faster than the bubble sort and a little over twice as fast as the insertion sort, its closest competitor.

The implementation of ShellSorter class

public class ShellSorter where T : IComparable

{

public List Sort(IEnumerable input)

{

List inputItems = new List(input);

Int32 increment = inputItems.Count / 2;

while (increment > 0)

{

for (Int32 i = increment; i <>

{

Int32 j = i;

T temp = inputItems[i];

while (j >= increment && inputItems[j - increment].CompareTo(temp)== 1)

{

inputItems[j] = inputItems[j - increment];

j -= increment;

}

inputItems[j] = temp;

}

if (increment / 2 != 0)

{

increment = increment / 2;

}

else if (increment == 1)

{

increment = 0;

}

else

{

increment = 1;

}

}

return inputItems;

}

}



I will continue this series with sorting mechanisms. Till then bye.

No comments: