Bubble Sort

5.1 Bubble Sort Definition

Bubble Sort is a simple sorting algorithm that repeatedly goes through the list, compares adjacent elements and swaps them if they're in the wrong order. This process continues until the list is completely sorted.

How it works:

1. The algorithm goes through the list and compares each pair of adjacent elements.
2. If the elements are in the wrong order (the first is greater than the second for ascending order), they are swapped.
3. This process is repeated for all pairs of elements in the list.
4. After each full pass, the largest element "bubbles" to its correct position (like a bubble to the water's surface), and doesn't get included in the next passes.
5. This process repeats until the list is sorted.

Time and Space Complexity of Bubble Sort

Time Complexity:

• In the worst case: O(n^2)— occurs when elements are initially ordered in reverse.
• On average: O(n^2)— happens for random element arrangement.
• In the best case: O(n)— occurs when elements are already sorted (the algorithm can be optimized for this case by adding a check if a swap occurred during a pass).

Space Complexity:

O(1)— since the algorithm uses a constant amount of extra memory (just a few variables to store temporary values).

5.2 Algorithm Implementation

The "bubble sort" algorithm is the simplest and most primitive sorting algorithm for a list/array of elements. It simply compares pairwise elements and swaps them if needed.

Version 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)

for i in range(n):
    for j in range(n - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Swap elements

print("Sorted array:", array)
# Output: Sorted array: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

The inner loop (highlighted in green) compares the element with its right neighbor. And if needed, swaps the elements.

Version 2:

Our algorithm can be optimized right away: after the first pass of the algorithm, the largest element ends up on the far right, so it can be ignored in the next cycle.

After the second iteration, there will already be 2 maximum elements on the right, so the inner loop can run up to n - 1 minus i, where i is the number of completed iterations of the outer loop.

The new version would look like this:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)

for i in range(n):
    for j in range(n - 1 - i): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Swap elements

print("Sorted array:", array)
# Output: Sorted array: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Version 3:

Also, the array might already be nearly sorted. So we can add an optimization: if the inner loop goes through all elements but makes no swaps, the sorting is complete.

In this version, a variable swapped is used to track whether there was a swap during the last pass. If after a pass through the array no swaps were made, it means the array is already sorted, and further iterations are unnecessary—they won't improve the sorting. Thus, the swapped variable can significantly speed up the algorithm on nearly sorted arrays by ending its execution early.

Bubble sort implementation in Python:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False # Optimization: check if a swap has occurred
        for j in range(0, n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Swap elements
                swapped = True
        if not swapped:
            break  # If no swaps occurred, the array is already sorted
    return array

# Example usage:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Sorted array:", sorted_array)
# Output: Sorted array: [11, 12, 22, 25, 34, 64, 90]