1. Overview
In this tutorial, we’ll implement the insertion sort algorithm in Kotlin. Insertion sort is a simple and efficient sorting algorithm that performs its tasks by repeatedly moving elements from an unsorted part of a list to the sorted part of the list. It builds the sorted list one element at a time, iterating through the input array and inserting each element into its correct position in the sorted portion of the array.
Essentially, insertion sort is similar to the process of arranging integers, such as scores or counts, in ascending order from the smallest to the largest.
2. How Insertion Sort Works
In insertion sort, we begin with an initial array, such as [5, 2, 9, 3]. We start by comparing the second integer, 2, to the first one, which is 5. Since 2 is smaller, we insert it before 5, resulting in [2, 5, 9, 3]. Next, we move to the third integer, 9, and insert it in its correct position among the already-sorted integers. Since 9 is larger than 5, no change is needed at this point, leaving us with [2, 5, 9, 3] as our partially sorted array.
Now, when moving on to the fourth integer, 3, we compare it to 9 first. Instead of shifting 9 one position to the left, we should shift 9 one position to the right because 9 is larger than 3. After that, we compare 3 to 5 and shift 5 to the right side, as 3 is smaller than 5. Finally, we compare 3 to 2, and since 3 is larger than 2, no change is needed. Thus, we insert 3 in the correct position, giving us the final sorted array: [2, 3, 5, 9].
3. Insertion Sort in Kotlin
Let’s take a look at how we can implement the insertion sort using Kotlin:
fun insertionSort(arr: IntArray) {
val n = arr.size
for (i in 1 until n) {
val key = arr[i]
var j = i - 1
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
}
class SortIntArrayTest {
@Test
fun testInsertionSort() {
val myArray = intArrayOf(5, 2, 9, 3, 6)
insertionSort(myArray)
val expectedSortedArray = intArrayOf(2, 3, 5, 6, 9)
assertArrayEquals(expectedSortedArray, myArray)
}
}
Our insertionSort() function takes an IntArray as input and sorts it in place using the insertion sort algorithm. It iterates through the array, comparing each element with the elements before it and inserting it into the correct position within the sorted part of the array.
Our testInsertionSort() function demonstrates how we use the insertionSort() function to sort an array of integers and then assert the sorted array.
4. Insertion Sort Algorithm Using Comparable
Since we’ve just seen a simple example with IntArrays, let’s take a look at how we would implement insertion sort while using arrays of Comparable objects:
data class Person(val name: String, val age: Int): Comparable<Person> {
override fun compareTo(other: Person): Int {
return age.compareTo(other.age)
}
}
fun insertionSortByAge(people: Array<Person>) {
val n = people.size
for (i in 1 until n) {
val key = people[i]
var j = i - 1
while (j >= 0 && people[j] > key) {
people[j + 1] = people[j]
j--
}
people[j + 1] = key
}
}
class SortingTests {
@Test
fun testInsertionSortByAge() {
val people = arrayOf(
Person("Alice", 30),
Person("Bob", 25),
Person("Charlie", 35),
Person("David", 20)
)
insertionSortByAge(people)
val expected = arrayOf(
Person("David", 20),
Person("Bob", 25),
Person("Alice", 30),
Person("Charlie", 35)
)
for (i in people.indices) {
assertEquals(expected[i], people[i])
}
}
}
In this code, we first define a data class Person with two properties: name and age. Our function insertionSortByAge() takes an Array of Person objects as input and performs the insertion sort algorithm to sort them in ascending order by age.
Because our Person class is Comparable, we can directly compare our Person objects via operator functions and our Comparable implementation. It works in a very similar way to the first example.
5. Insertion Sort Complexity Analysis
Let’s review the time complexity features of the insertion sort algorithm:
- Best-case: The best-case scenario occurs when the input data is already sorted. In this case, the insertion sort algorithm performs n-1 comparisons and no swaps, where n is the number of elements. The time complexity is O(n).
- Average case: In the average case, insertion sort performs approximately n^2/4 comparisons and n^2/4 swaps. The time complexity is O(n^2).
- Worst-case: The worst-case scenario occurs when the input data is sorted in reverse order. In this case, the insertion sort algorithm performs n(n-1)/2 comparisons and n(n-1)/2 swaps. The time complexity is still O(n^2).
Regarding space complexity, *insertion sort is an in-place sorting algorithm, which means it doesn’t require additional memory for temporary storage. Therefore, its space complexity is O(1), which makes it memory-efficient.*
Generally, insertion sort can be regarded as a stable sorting algorithm. This means that if two of our elements have equal keys or values, their relative order in the sorted output will be the same as their relative order in the input.
The best use case for the insertion sort algorithm is when we need to sort small datasets or when efficiency is not a critical concern we need to address.
6. Conclusion
In this article, we reviewed the insertion sort algorithm, which builds a final sorted list/array one element at a time. We saw how the insertion sort algorithm works and implemented solutions in Kotlin using both Arrays and IntArrays. Finally, we looked at the algorithm’s complexity properties and concluded that it’s best applicable when we need to sort small datasets.
The full implementation of these examples is available over on GitHub.