Kotlin Training Program

DOWNLOAD APP

FEEDBACK

Insertion Sort

Insertion Sort algorithm is similar to the way we sort playing cards. Following is how we sort n playing cards :

Example

 Cards = 4, 7, 2, A, K, J (Sort in Ascending order)

i=0 : [4] Single card already sorted
i=1 : Insert 7 correctly in [4] : [4, 7]
i=2 : Insert 2 correctly in [4, 7] : [2, 4, 7]
i=3 : Insert A correctly in [2, 4, 7] : [2, 4, 7, A]
i=4 : Insert K correctly in [2, 4, 7, A] : [2, 4, 7, K, A]
i=5 : Insert J correctly in [2, 4, 7, K, A] : [2, 4, 7, J, K, A]

Similarly, to sort list of numbers we insert numbers one by one into the sorted sub-list. Hence, this algorithm is named Insertion sort.

Algorithm

For Insertion sort on a list of n number, n-1 iterations are required for i in range 1..n-1 (or 1..lastIndex). On each i^th^ iteration, a sub-list of size i+1 is sorted by inserting list[i] in the sub-list list[0..i-1]. On the last iteration i=n-1, all i+1=n numbers are sorted.

Example

 list = [5, 3, 1, 2, 4]
iterations = i in 1..4

[5 <<sorted | unsorted>> 3, 1, 2, 4]

i=1
Insert list[i=1]=3 in the sub-list list[0..i-1 = 0..0]
[3, 5 <<sorted | unsorted>> 1, 2, 4]

i=2
Insert list[i=2]=1 in the sub-list list[0..i-1 = 0..1]
[1, 3, 5 <<sorted | unsorted>> 2, 4]

i=3
Insert list[i=3]=2 in the sub-list list[0..i-1 = 0..2]
[1, 2, 3, 5 <<sorted | unsorted>> 4]

i=4
Insert list[i=4]=4 in the sub-list list[0..i-1 = 0..3]
[1, 2, 3, 4, 5 <<sorted]

An extra array is not required to store the sorted sub-list. Instead, swaps are used to perform in-place sorting. Swaps are required for inserting list[i] in the sub-list list[0..i-1]. In Bubble sort, consecutive left to right swaps are performed while in Insertion sort, consecutive right to left swaps are performed.

On each i^th^ iteration indices j for j in range (i-1) downTo 0, we compare list[j] & list[j+1]. If larger number is found before smaller number, swap is performed.

Example

 list = [5, 3, 1, 2, 4]
iterations = i in 1..4

[5 <<sorted | unsorted>> 3, 1, 2, 4]

i=1
j in i-1..0 = 0..0
j=0 : list[j=0] > list[j+1=1] : 5 > 3 : true, swap 0 & 1
list = [3, 5 <<sorted | unsorted>> 1, 2, 4]

i=2
j in i-1..0 = 1..0
j=1 : list[j=1] > list[j+1=2] : 5 > 1 : true, swap 1 & 2
list = [3, 1, 5, 2, 4]
j=0 : list[j=0] > list[j+1=1] : 3 > 1 : true, swap 0 & 1
list = [1, 3, 5 <<sorted | unsorted>> 2, 4]

i=3
j in i-1..0 = 2..0
j=2 : list[j=2] > list[j+1=3] : 5 > 2 : true, swap 2 & 3
list = [1, 3, 2, 5, 4]
j=1 : list[j=1] > list[j+1=2] : 3 > 2 : true, swap 1 & 2
list = [1, 2, 3, 5, 4]
j=0 : list[j=0] > list[j+1=1] : 1 > 2 : false
list = [1, 2, 3, 5 <<sorted | unsorted>> 4]

i=4
j in i-1..0 = 3..0
j=3 : list[j=3] > list[j+1=4] : 5 > 4 : true, swap 3 & 4
list = [1, 2, 3, 4, 5]
j=2 : list[j=2] > list[j+1=3] : 3 > 4 : false
list = [1, 2, 3, 4, 5]
j=1 : list[j=1] > list[j+1=2] : 2 > 3 : false
list = [1, 2, 3, 4, 5]
j=0 : list[j=0] > list[j+1=1] : 2 > 1 : false
list = [1, 2, 3, 4, 5 <<sorted]

Implementation

 
 fun List<Int>.sortedUsingInsertionSort1(): List<Int> {
    val array = toIntArray()

    for (i in 1..lastIndex) {
        
        // Correctly insert array[i] in array[0..i-1]
        for (j in i-1 downTo 0) {

            // Swap if larger number is found before smaller
            if (array[j] > array[j+1]) {
                array[j] = array[j+1].also {
                    array[j+1] = array[j]
                }
            }
        }
    }

    return array.toList()
}

Descending sort

To support descending sort, we just have to change the swap condition checking from array[j] > array[j+1] to array[j] < array[j+1] i.e. we swap when smaller number is found before larger number.

 fun List<Int>.sortedUsingInsertionSort(descending: Boolean = false): List<Int> {
    val array = toIntArray()

    for (i in 1..lastIndex) {

        // Correctly insert array[i] in array[0..i-1]
        for (j in i-1 downTo 0) {

            // Determine whether to swap
            val swap = if (descending) {
                array[j] < array[j+1]
            } else {
                array[j] > array[j+1]
            }

            if (swap) {
                array[j] = array[j+1].also {
                    array[j+1] = array[j]
                }
            }
        }
    }

    return array.toList()
}