Table of content

Insertion Sort in Kotlin

Insertion sort is similar to arranging the documents of a bunch of students in order of their ascending roll number.

Starting from the second element, we compare it with the first element and swap it if it is not in order. Similarly, we take the third element in the next iteration and place it at the right place in the subarray of the first and second elements (as the subarray containing the first and second elements is already sorted).

We repeat this step with the fourth element of the array in the next iteration and place it at the right position in the subarray containing the first, second and the third elements. We repeat this process until our array gets sorted. So, the steps to be followed are:

Kotlin Insertion Sort Logic is very simple

Every iteration, the smallest element will be added to the unsorted array. Let’s consider this scenario.

  • Consider, You have 10 elements in an array.
  • 1st iteration(from the second element in the array) puts the smallest element into position 1. We will call it as a sorted array. Remaining 9 elements will call as an unsorted array.
  • Now in 2nd iteration, the smallest element from the unsorted array will be put into 1st position. Now, there will be 2 elements in sorted array and 8 elements into the unsorted array.
  • The same iteration will continue until we reached to 0 elements in the unsorted array.

Higher Order Functions in kotlin

insertion-sort-kotlin

Code explanation for Insertion Sort with kotlin :

    • First and foremost, you can use this method for list and arrays with little modifications. Considering List in this example
    • Check the number of elements in the list/array, if the number of elements are lesser than 2, then no need to sort because it is already sorted. It would be funny if we try to sort an array/list with 1 element
if (items.isEmpty() || items.size<2){
	return items
}
    • Start the comparing current element with previous element, if the current element is smaller then we switch/swap it with previous element.

      Why should we start with the second element ?
      We will be starting the loop from the second element because we wanted to compare the element with the previous element only. (With changes in logic you can use the first element as well.)
for (count in 1..items.count() - 1){
    • Before we make the swap, we have to store the current element in a temp variable called "item"
val item = items[count]
var i = count
    • When we handle the second element then we do not have the problem. But when we are dealing with other elements we have to make sure that we are putting the small element in the first position.

      The while loop helps the user to see is there any other element is smaller than the current element by decrementing the position from "current-1" position. If any small element is present then we swap it.

while (i>0 && item < items[i - 1]){
	items[i] = items[i - 1]
	i = i - 1
}

Safe Call Operator [?.] in kotlin

Complete program for Insertion sort in Kotlin

fun insertionsort(items:MutableList<Int>):List<Int>{
    if (items.isEmpty() || items.size<2){
        return items
    }
    for (count in 1..items.count() - 1){
        // println(items)
        val item = items[count]
        var i = count
        while (i>0 && item < items[i - 1]){
            items[i] = items[i - 1]
            i -= 1
        }
        items[i] = item
    }
    return items
}
fun main(args: Array<String>) {
    val names = mutableListOf(8, 3, 2, 7, 4)
    println(names)
    var ordered = insertionsort(names)
    println(ordered)
}
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions