Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A simple implementation of Insertion Sort in C#
bool showDebugOutput = true;
void Main()
{
var data = new string[] { "A", "R", "L", "S", "T", "N", "E" };
// Tell the user what's going on
Console.WriteLine("Unsorted Data:");
DumpData(data);
Console.WriteLine("Sorting Data...");
Console.WriteLine();
DrawSeparatorLine();
// Sort the data
var result = InsertSort(data, true);
DrawSeparatorLine();
// Dump the sorted data to the console
Console.WriteLine("Sorted Data:");
DumpData(result);
}
string[] InsertSort(string[] data, bool desc)
{
// Start at index 1 (we skip the first element because that's where
// we start the comparison)
for (int dataIndex = 1; dataIndex < data.Length; dataIndex++)
{
// Get the current item from our input data
string item = data[dataIndex];
// Note that we don't have an exit condition on this for loop
// because we break out of the loop manually once a swap is made.
for (int searchPointer = dataIndex - 1; searchPointer >= 0;)
{
if (showDebugOutput)
WriteCompareOutput(dataIndex, searchPointer);
if (showDebugOutput)
WriteDebugOutput(item, data[searchPointer]);
// Using string.CompareTo() to determine ordering
// See https://msdn.microsoft.com/en-us/library/35f0x18w(v=vs.110).aspx
// CompareTo returns:
// -1 if item belongs before the other item
// 0 if item is equal to the other item
// 1 if item belongs after the other item
if (item.CompareTo(data[searchPointer]) < 0)
{
data[searchPointer + 1] = data[searchPointer];
searchPointer--;
data[searchPointer + 1] = item;
}
else
break;
}
if (showDebugOutput)
DumpData(data);
}
return data;
}
// Methods for optional debug output
void WriteCompareOutput(int dataIndex, int searchPointer)
{
Console.Write("Comparing index {0} to index {1}: ", dataIndex, searchPointer);
}
void WriteDebugOutput(string currentItem, string other)
{
var comparisonResult = currentItem.CompareTo(other);
if (comparisonResult < 0)
Console.WriteLine("{0} is less than {1} - Swapping.", currentItem, other);
else if (comparisonResult == 0)
Console.WriteLine("{0} is equal to {1} - No Swap.", currentItem, other);
else
Console.WriteLine("{0} is greater than {1} - No Swap.", currentItem, other);
}
void DumpData(string[] input)
{
for (int i = 0; i < input.Length; i++)
{
Console.WriteLine(input[i]);
}
Console.WriteLine();
//Console.WriteLine(input);
}
void DrawSeparatorLine()
{
if (showDebugOutput)
Console.WriteLine("============================================");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.