Bubble Sort — Swift

Bubble sort is an In place sorting algorithm and follows the following four steps to sort an array

1. Compare pair of adjacent items (a, b)
2. Swap that pair if the items are out of order (in this case, when a > b),
3. Repeat Step 1 and 2 until we reach the end of array
   (the last pair is the (N-2)-th and (N-1)-th items as we use 0-based indexing),
4. By now, the largest item will be at the last position.
   We then reduce N by 1 and repeat Step 1 until we have N = 1.

Code

func bubbleSort<T: Comparable>(_ nums: inout [T]) {
    if nums.isEmpty {
        return
    }
    var numsCount = nums.count
    while numsCount != 0 {
        for index in 0..<numsCount {
            if numsCount + 1 <= nums.count && nums[index] > nums[index + 1] {
                nums.swapAt(index, index + 1)
            }
        }
        numsCount -= 1
     }
}
var array = [29, 10, 14, 37, 14]
bubbleSort(&array)

Complexity Analysis

Time Complexity — O(N²) Space Complexity — O(1)

Comparison and swap happens in constant time, let’s call it c. There are two nested loops in Bubble Sort. The outer loop runs for exactly N iterations but the inner loop get shorter and shorter.

1. When index=0, (N−1) iterations (of comparisons and possibly swaps),
2. When index=1, (N−2) iterations,
   …,
3. When index=(N−2), 1 iteration,
4. When index=(N−1), 0 iteration.

Thus, the total number of iterations = (N−1)+(N−2)+…+1+0 = N*(N−1)/2 (derivation).

Total time = c*N*(N−1)/2 = O(N²).

Improved Bubble Sort

If we go through the inner loop with no swapping at all, it means that the array is already sorted and we can stop Bubble Sort at that point where it terminates in O(N) time.

func bubbleSort<T: Comparable>(_ nums: inout [T]) {
    if nums.isEmpty {
        return
    }
var numsCount = nums.count
    while numsCount != 0 {
        var swapped = false
        for index in 0..<numsCount {
            if numsCount + 1 <= nums.count && nums[index] > nums[index + 1] {
                nums.swapAt(index, index + 1)
            }
        }
        if !swapped {
            break
        }
        numsCount -= 1
     }
}
var array = [3, 6, 11, 25, 39]
bubbleSort(&array)