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
{
public List
{
List
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
{
public List
{
List
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;
}
}
No comments:
Post a Comment