In Bubble sort, if a number has to bubble up from position p to its correct position q, then q-p number of swaps are required.

Example

 Example 1 :
list = [3, 2, 1]
To bubble up 3 from index p=0 to q=2,
swap index 0 & 1 : [2, 3, 1]
swap index 1 & 2 : [2, 1, 3]
number of swaps = q-p = 2-0 = 2

Example 2 :
list = [9, 10, 5]
To bubble up 10 from index p=1 to q=2,
swap index 1 & 2 : [9, 5, 10]
number of swaps  = q-p = 2-1 = 1
 

We can reduce the number of swaps from q-p to just 1 if we know the position p. Then only the swap of positions p & q are sufficient.

Similar to Bubble sort, Selection sort also requires n-1 iterations for i in range lastIndex downTo 1. On each iteration instead of multiple swaps, we first find the index of the correct element to place at ith index and then perform just 1 swap.

Example

 list = [9, 10, 5]
iterations required = 2 (from 2 to 1)

i=2 :
max no in index range 0..2 = 10
index of 10 = 1
swap position (i=2) & (index=1) : [9, 5, 10]

i=1 :
max no in index range 0..1 = 9
index of 9 = 0
swap position (i=1) & (index=0) : [5, 9, 10]
 

Lets see how to find this index to swap ith index with.

To find the index of element to swap with, we create one variable index to store the position of largest element found so far. It is initialized with 0. For each iteration of i, we find this index by comparing numbers at index j in range 1..i. We update the index whenever a number larger than list[index] is found.

Example

 list = [9, 10, 5]
iterations required = 2 (from 2 to 1)

i=2 :
index = 0
j in 1..2
j=1 : list[j=1] > list[index=0] : 10 > 9 : true, update index = 1
j=2 : list[j=2] > list[index=1] : 5 > 10 : false
swap list[index=1] & list[i=2] : [9, 5, 10]

i=1 :
index = 0
j in 1..1
j=1 : list[j=1] > list[index=0] : 5 > 9 : false
swap list[index=0] & list[i=1] : [5, 9, 10]
 

To summarize, in Selection Sort we first select (find) the number number to swap with the number on its correct position. Hence, due to this select operation it is named Selection sort.

For a list of size n, we perform this select & swap operation n-1 times for i in range lastIndex downTo 1.

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

    for (i in lastIndex downTo 1) {

        // Index of number to swap with. Assume array[0] to be max
        var index = 0

        for (j in 1..i) {
            
            // Update index if larger number is found
            if (array[j] > array[index]) index = j
        }

        // Swap position i & index
        array[i] = array[index].also {
            array[index] = array[i]
        }
    }

    return array.toList()
}
 

To support descending sort, we just have to change the “update index” condition checking from array[j] > array[index] to array[j] < array[index] i.e. we update index when a number smaller than array[index] is found.

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

    for (i in lastIndex downTo 1) {

        // Index of number to swap with. Assume array[0] to be max/min
        var index = 0

        for (j in 1..i) {

            val update = if (descending) {
                array[j] < array[index]
            } else {
                array[j] > array[index]
            }

            // Update index if larger/smaller number is found
            if (update) index = j
        }

        // Swap position i & index
        array[i] = array[index].also {
            array[index] = array[i]
        }
    }

    return array.toList()
}