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
}

Leave a Reply

Come See Me

San Francisco, CA
hello@ingax.com

See My Work