Bubble Sort

At each iteration, the largest element bubbles into correct order.

The bubbling operation takes \(O(n)\) time and this operation is performed \(n\) times. Therefore, Bubble Sort runs in \(O(n^2)\) time.

The swaps are performed in place. If the given array is mutable, the algorithm can be performed in constant space.

func bubbleSort(_ array: inout [Int]) -> [Int] {
    for _ in 0.. array[i+1] {
                array.swapAt(i, i+1)
            }
        }
    }
    return array
}

Here’s a couple of real world optimizations.

Add a counter to avoid checking the part of the list that has already been sorted.

func bubbleSort(_ array: inout [Int]) -> [Int] {
    var counter = 0
    for _ in 0.. array[i+1] {
                array.swapAt(i, i+1)
            }
        }
        counter += 1
    }
    return array
}

Add a bool to return the list if it is already sorted.

func bubbleSort(_ array: inout [Int]) -> [Int] {
    var counter = 0
    var inOrder = false
    while !inOrder {
        inOrder = true
        for i in 0.. array[i+1] {
                array.swapAt(i, i+1)
                inOrder = false
            }
        }
        counter += 1
    }
    return array
}