Bubble Sort Python Implementations

by

Bubble Sort is a fundamental comparison-based sorting algorithm that iteratively compares and swaps adjacent elements to arrange a list in ascending order. Though not the most efficient for large datasets, its simplicity makes it an excellent tool for learning sorting concepts. This article explores three Python implementations of Bubble Sort, from a basic version to optimized variants, with detailed code, outputs, explanations, and complexity analyses.

1. Basic Bubble Sort

def bubbleSortBasic(arr):
    n = len(arr)
    for i in range(n):                         # outer passes
        for j in range(0, n - i - 1):          # compare neighbors
            if arr[j] > arr[j + 1]:            # swap if out of order
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

array = [50, 20, 40, 10, 30]
bubbleSortBasic(array)
print(f"Result: {array}")

Output

Result: [10, 20, 30, 40, 50]

Explanation

The basic Bubble Sort implementation uses two nested loops. The outer loop iterates n times, where n is the length of the array. The inner loop compares each pair of adjacent elements up to the unsorted portion (n - i - 1) and swaps them if they are in the wrong order. This process ensures the largest unsorted element bubbles up to its correct position in each pass. However, this version always completes all passes, even if the array is sorted early, making it inefficient for nearly sorted inputs.

Time and Space Complexity

  • Worst-case: \( \Theta(n^2) \) – occurs when the array is sorted in reverse order, requiring the maximum number of comparisons and swaps.
  • Average-case: \( \Theta(n^2) \) – typical for random input, as most elements need multiple passes to reach their final positions.
  • Best-case: \( \Theta(n^2) \) – even for a sorted array, the algorithm performs all comparisons without early termination.
  • Space: \( \Theta(1) \) – in-place sorting with only a constant amount of extra memory for variables.

2. Bubble Sort with Early-Exit Flag

def bubbleSortEarlyExit(arr):
    n = len(arr)
    for i in range(n):
        swapped = False                        # track if a swap happened
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:                        # already sorted → stop early
            break

array = [50, 20, 40, 10, 30]
bubbleSortEarlyExit(array)
print(f"Result: {array}")

Output

Result: [10, 20, 30, 40, 50]

Explanation

This optimized version introduces a swapped flag to track whether any swaps occurred during a pass. If no swaps are needed, the array is already sorted, and the algorithm terminates early. This improvement significantly enhances performance for nearly sorted or fully sorted arrays, as it avoids unnecessary iterations.

Time and Space Complexity

  • Worst-case: \( \Theta(n^2) \) – same as the basic version for reverse-sorted arrays, requiring full passes.
  • Average-case: \( \Theta(n^2) \) – similar to the basic version for random inputs, though slightly fewer comparisons may occur.
  • Best-case: \( \Theta(n) \) – if the array is already sorted, the algorithm terminates after a single pass with no swaps.
  • Space: \( \Theta(1) \) – adds only a boolean variable, maintaining in-place sorting.

3. Bubble Sort with Last-Swap Boundary

def bubbleSortLastSwap(arr):
    n = len(arr)
    while n > 1:                               # keep shrinking unsorted part
        lastSwap = 0
        for j in range(1, n):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
                lastSwap = j                   # remember furthest swap index
        n = lastSwap                           # next pass only up to last swap

array = [50, 20, 40, 10, 30]
bubbleSortLastSwap(array)
print(f"Result: {array}")

Output

Result: [10, 20, 30, 40, 50]

Explanation

This version further optimizes Bubble Sort by tracking the index of the last swap in each pass. After each pass, the unsorted portion of the array is reduced to the position of the last swap, as all elements beyond that point are already in their correct positions. This dynamic shrinking of the unsorted region reduces the number of comparisons, especially for partially sorted arrays, making it the most efficient of the three implementations in practice.

Time and Space Complexity

  • Worst-case: \( \Theta(n^2) \) – similar to the other versions for reverse-sorted arrays.
  • Average-case: \( \Theta(n^2) \) – fewer comparisons than the other versions for partially sorted data due to the shrinking unsorted region.
  • Best-case: \( \Theta(n) \) – like the Early-Exit version, it terminates after one pass if the array is sorted.
  • Space: \( \Theta(1) \) – uses only a single integer variable for tracking the last swap.

Conclusion

The three Bubble Sort implementations demonstrate a progression in optimization. The Basic Bubble Sort is simple but performs unnecessary comparisons. The Early-Exit Flag version reduces iterations for sorted or nearly sorted arrays by stopping early. The Last-Swap Boundary version further optimizes by dynamically shrinking the unsorted region, minimizing comparisons. Despite their quadratic time complexity, these optimizations make Bubble Sort more practical for small datasets or educational purposes. For large datasets, more efficient algorithms like Quick Sort or Merge Sort are recommended, but Bubble Sort remains a valuable tool for understanding sorting fundamentals.

Leave a comment