Insertion sort in Kotlin
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.kt, 15 lines- Level
- Toolchain
- Kotlin 2.3 on JDK 25
- Test framework
- JUnit 5
- Run the tests
kotlinc and the JUnit console launcher
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
/** Sorts a in place, in non-decreasing order. The sort is stable. */
fun <T : Comparable<T>> insertionSort(a: MutableList<T>) {
for (i in 1 until a.size) { // @line L1
val key = a[i] // @line L2
var j = i - 1 // @line L3
while (j >= 0 && a[j] > key) { // @line L4
a[j + 1] = a[j] // @line L5
j-- // @line L6
}
a[j + 1] = key // @line L7
}
}
InsertionSortTest.kt 36 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
import kotlin.random.Random
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test
class InsertionSortTest {
@Test
fun example() {
val a = mutableListOf(5, 2, 4, 6, 1, 3)
insertionSort(a)
assertEquals(listOf(1, 2, 3, 4, 5, 6), a)
}
@Test
fun edges() {
val e = mutableListOf<Int>()
insertionSort(e)
assertEquals(emptyList<Int>(), e)
val w = mutableListOf("pear", "fig", "apple")
insertionSort(w)
assertEquals(listOf("apple", "fig", "pear"), w)
}
@Test
fun randomAgainstSorted() {
val rng = Random(2150)
repeat(500) {
val a = MutableList(rng.nextInt(41)) { rng.nextInt(101) - 50 }
val want = a.sorted()
insertionSort(a)
assertEquals(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