What is the Bubble Sort Algorithm?
The bubble sort is a basic sorting algorithm named after the way elements progressively “bubble up” to the top of the list.
Code Example
func bubbleSort(_ array: [Int]) -> [Int] {
var A = array
var N = array.count
var swapping = true
while swapping {
swapping = false
for i in 1 ..< N {
if A[i - 1] > A[i] {
let tmp = A[i - 1]
A[i - 1] = A[i]
A[i] = tmp
swapping = true
}
}
N -= 1
}
return A
}
Implementation
The bubble sort uses an loop and swapping
property to control it behaviour. Inside the loop, it iterates over all elements, comparing the current and next elements. If the current element is greater than the next, it swaps them.
The example above uses optimized bubble sort, where the inner loop avoids looking at the last n − 1 items when running for the n-th time, resulting in about a 50% improvement in the worst-case scenario.
Time/Space Complexity
Bubble sort has a worst-case and average time complexity of O(n²), where n is the number of items being sorted.
The worst-case space complexity is O(n) total, O(1) auxiliary.