Insertion sort in C#
Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.
- File
InsertionSort.cs, 24 lines- Level
- Toolchain
- .NET 10, C# 14, xUnit
- Test framework
- xUnit
- Run the tests
dotnet test
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
namespace Algorithm;
/// <summary>Insertion sort.</summary>
public static class InsertionSort
{
/// <summary>Sorts a in place, in non-decreasing order. The sort is stable.</summary>
public static void Sort<T>(Span<T> a) where T : IComparable<T>
{
for (int i = 1; i < a.Length; i++) // @line L1
{
T key = a[i]; // @line L2
int j = i - 1; // @line L3
while (j >= 0 && a[j].CompareTo(key) > 0) // @line L4
{
a[j + 1] = a[j]; // @line L5
j--; // @line L6
}
a[j + 1] = key; // @line L7
}
}
}
InsertionSortTests.cs 42 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
using Algorithm;
using Xunit;
public class InsertionSortTests
{
[Fact]
public void Example()
{
long[] a = [5, 2, 4, 6, 1, 3];
InsertionSort.Sort<long>(a);
Assert.Equal(new long[] { 1, 2, 3, 4, 5, 6 }, a);
}
[Fact]
public void Edges()
{
long[] e = [];
InsertionSort.Sort<long>(e);
Assert.Empty(e);
string[] w = ["pear", "fig", "apple"];
InsertionSort.Sort<string>(w);
Assert.Equal(new[] { "apple", "fig", "pear" }, w);
}
[Fact]
public void RandomAgainstArraySort()
{
var rng = new Random(2150);
for (int t = 0; t < 500; t++)
{
var a = new long[rng.Next(41)];
for (int i = 0; i < a.Length; i++) a[i] = rng.Next(101) - 50;
var want = (long[])a.Clone();
Array.Sort(want);
InsertionSort.Sort<long>(a);
Assert.Equal(want, a);
}
}
}
What the next level needs
- the native tests did not run in this build
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work