Implement Bubble Sort Fast AF

Bubble sort is a simple sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. It is called bubble sort because the larger elements “bubble” to the top of the list like a bubble rising to the surface of a liquid.

While bubble sort is not the most efficient sorting algorithm, it can be a good choice for small lists or for educational purposes. In this tutorial, we will learn how to implement bubble sort in Swift and discuss the pros and cons of using it.

To start, let’s create a function called bubbleSort that takes in an array of integers and returns a sorted array. We will use a variable called sorted to store the sorted array and a variable called swapped to track whether any swaps have been made in the current iteration.

func bubbleSort(array: [Int]) -> [Int] {
    var sorted = array
    var swapped = true
    
    while swapped {
        swapped = false
        for i in 0..<sorted.count-1 {
            if sorted[i] > sorted[i+1] {
                let temp = sorted[i]
                sorted[i] = sorted[i+1]
                sorted[i+1] = temp
                swapped = true
            }
        }
    }
    
    return sorted
}

The inner for loop iterates through the entire array, comparing each element to its neighbor. If the element is larger than its neighbor, it is swapped. The swapped variable is set to true to indicate that a swap has been made. If no swaps are made in a given iteration, the while loop will terminate because swapped is set to false.

Now let’s test our bubbleSort function using the following array:

let array = [5, 2, 4, 1, 3]
let sortedArray = bubbleSort(array: array)
print(sortedArray)  // Output: [1, 2, 3, 4, 5]

As expected, the output is a sorted version of the original array.

One advantage of bubble sort is that it is easy to understand and implement. It also requires minimal additional space, as it only uses a single temporary variable to store the value being swapped. However, the main disadvantage of bubble sort is its time complexity. On average, it takes O(n²) time to sort an array using bubble sort, making it inefficient for larger lists.

In conclusion, bubble sort is a simple sorting algorithm that can be useful for small lists or for educational purposes. However, for larger lists, it is recommended to use a more efficient algorithm such as quicksort or merge sort.