In bubble sort, we place last n-1 numbers at their correct place one by one, starting from index n-1 till index 1. So, n-1 iterations are required i.e. for i in range n-1..1.

Example

 list = [5, 4, 3, 2, 1]
size = 5
iterations required = 4 (from 4 to 1)

i=4 : 4th index is correctly set : [4, 3, 2, 1, 5]
i=3 : 3rd index is correctly set : [3, 2, 1, 4, 5]
i=2 : 2nd index is correctly set : [2, 1, 3, 4, 5]
i=1 : 1st index is correctly set : [1, 2, 3, 4, 5]
 

If we imagine start of list as bottom and end of list as top of a water container, then bubble sort algorithm makes larger numbers bubble up to their correct positions. In the above example,

• On iteration i=4, largest number 5 bubbles up to its correct position index 4
• On iteration i=3, second largest number 4 bubbles up to its correct position index 3
• On iteration i=2, third largest number 3 bubbles up to its correct position index 2
• On iteration i=1, fourth largest number 2 bubbles up to its correct position index 1

Bubbling up n-1 numbers to their correct positions works but how do we perform this algorithmically? We can do so using consecutive swaps. To make a number bubble up to its to its correct position i, we have to perform i comparisons. Firstly positions 0 & 1 are compared, then positions 1 & 2, till the positions i-1 & i i.e. we compare positions j & j+1 for j in range 0..i-1. On each comparison if larger number is found before a smaller number i.e. list[j] > list[j+1], we swap the positions.

Example

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

iteration i=4 :
j in 0..i-1 = 0..3
j=0 : list[0] > list[1] : 5 > 4 : true, swap : [4, 5, 3, 2, 1]
j=1 : list[1] > list[2] : 5 > 3 : true, swap : [4, 3, 5, 2, 1]
j=2 : list[2] > list[3] : 5 > 2 : true, swap : [4, 3, 2, 5, 1]
j=3 : list[3] > list[4] : 5 > 1 : true, swap : [4, 3, 2, 1, 5]
5 bubbles up to its correct position i=4

iteration i=3 :
j in 0..i-1 = 0..2
j=0 : list[0] > list[1] : 4 > 3 : true, swap : [3, 4, 2, 1, 5]
j=1 : list[1] > list[2] : 4 > 2 : true, swap : [3, 2, 4, 1, 5]
j=2 : list[2] > list[3] : 4 > 1 : true, swap : [3, 2, 1, 4, 5]
4 bubbles up to its correct position i=3

Similarly, 
after i=2, 3 bubbles up to its correct position i=2 :
[2, 1, 3, 4, 5]

after i=1, 2 bubbles up to its correct position i=1 :
[1, 2, 3, 4, 5]

Array is sorted!
 

To summarize, we need two nested loops (one inside another) :

• Outer loop will be of i in range n-1..1 (or lastIndex downTo 1)
• Inner loop will be of j in range 0..i-1 (or 0 until i)

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

    for (i in lastIndex downTo 1) {

        for (j in 0 until i) {

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

Because List is immutable, we first convert list to an array, modify it and then convert it back to list.

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>.sortedUsingBubbleSort(descending: Boolean = false): List<Int> {
    val array = toIntArray()

    for (i in lastIndex downTo 1) {

        for (j in 0 until i) {

            // Determine Swap condition
            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()
}
 

Lets analyze the number of operations to be performed when a list of size n is sorted using Bubble sort.

Recall that two nested loops are required :

• Outer loop of i in range lastIndex downTo 1
• Inner loop of j in range 0 until i

i	j	no. of operations
lastIndex = n-1	0…(n-1)	n-1
n-2	0…(n-2)	n-2
n-3	0…(n-3)	n-3
1	0…1	1

So, total number of operations performed

= 1 + 2 + 3 + … + (n-3) + (n-2) + (n-1)

= [ (n-1) * (n) ] / 2

≈ n^2^

Hence time complexity of Bubble sort is quadratic i.e. n^2^.

The above implementation of Bubble sort performs similarly in all 3 cases -

• Best case : list is already partially / completely sorted
• Average case : list is not sorted either way
• Worst case : list is sorted in reverse order

We can improve the algorithm to perform better in Best case. During any iteration of outer loop if no swap is performed, then it implies that sorting is complete. Swap is performed when larger number is found before smaller number. No swap means all numbers in the list are preceded by a number smaller or equal to itself i.e. list is already sorted. Example :

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

iteration i=4 :
j in 0..i-1 = 0..3
j=0 : list[0] > list[1] : 5 > 1 : true, swap : [1, 5, 2, 3, 4]
j=1 : list[1] > list[2] : 5 > 2 : true, swap : [1, 2, 5, 3, 4]
j=2 : list[2] > list[3] : 5 > 3 : true, swap : [1, 2, 3, 5, 4]
j=3 : list[3] > list[4] : 5 > 4 : true, swap : [1, 2, 3, 4, 5]
5 bubbles up to its correct position i=4

iteration i=3 :
j in 0..i-1 = 0..2
j=0 : list[0] > list[1] : 1 > 2 : false
j=1 : list[1] > list[2] : 2 > 3 : false
j=2 : list[2] > list[3] : 3 > 4 : false
No swap performed, we can stop here because list is sorted
 

To implement this improvement, lets introduce a new Boolean flag to track whether we have performed at least one swap. We break out of the outer loop if no swap is performed.

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

    for (i in lastIndex downTo 1) {

        // Flag to track whether at least 1 swap is performed
        var swapped = false

        for (j in 0 until i) {

            // Determine Swap condition
            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]
                }
                swapped = true
            }
        }

        // If no swap performed, then list is sorted
        if (!swapped) break
    }

    return array.toList()
}
 

By this improvement, time complexity of best case is reduced. If the list is already sorted, then no swap will be performed in the first iteration of outer loop. Hence we break out of the loop performing only n-1 comparisons. So when list is already sorted, time complexity of Bubble sort is just n instead of n^2^.