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, smallest element will be added to unsorted array. Let’s consider this scenario.

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

Higher Order Functions

insertion-sort-kotlin

Code explanation for Insertion Sort with kotlin :

  • First and foremost, you can use this method for list and arrays with litle modifications. Considering List in this example
  • Check number of elements in the list/array, if the number of element are lesser than 2, then no need to sor as it is already sorted. I 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 Second element ?
    We will be starting the loop from the second element because we wanted to compare the element with previous element only. (With changes in logic you can use first element as well.)
  • 
    for (count in 1..items.count() - 1){		
    

  • Before we maake 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 elemenbt then we donot have the problem. But when we are dealig with other elements we have to make sure that we are putting small element in the first position.

    The while loop helps user to see is there any other element is smaller than 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 [?.]

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)
}			

Things to remember in Insertion sort

It is a simple Sorting algorithm which sorts the array by shifting elements one by one. Following are some of the important characteristics of Insertion Sort

  • It has one of the simplest implementation
  • It is efficient for smaller data sets, but very inefficient for larger lists.
  • Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.
  • It is better than Selection Sort and Bubble Sort algorithms
  • Its space complexity is less, like Bubble Sorting, inerstion sort also requires a single additional memory space.
  • It is Stable, as it does not change the relative order of elements with equal keys

Unit type in kotlin

Pros & Cons with Insertion Sort in Kotlin

Insertion sort is a good choice when the array to be sorted is almost sorted. This is because there will be less number of swaps.

On the contrary, insertion is slow because all the elements after an element that is not in order have to be moved up, therefore not good for big arrays that are not partially sorted.

Analysis of Insertion Sort

In any case, the insertion sort runs in O(N2) time for random data. For data that is already sorted or almost sorted, the insertion sort does much better.

When data is in order, the condition in the inner for loop is never true, so it becomes a simple statement in the outer loop, which executes N-1 times. In this case the algorithm runs in O(N) time. If the data is almost sorted, insertion sort runs in almost O(N) time.

However, for data arranged in inverse sorted order, every possible comparison and shift is carried out, so the insertion sort runs no faster than the bubble sort.

Read Properties File in Kotlin

aaaaaaaaaaaaa
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

 
Join My Facebook Group
Join Group