Exploring Time Complexity and Space Complexity of Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order until the list is sorted.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # Swap if elements are in the wrong order
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            # Stop early if no elements were swapped in the inner loop
            break
    return arr

template<typename T>
void bubble_sort(vector<T>& arr) {
    
    // Flag to detect if any swapping happened in the current pass
    bool swapped = false; 
    
    for(int i = 0; i < arr.size() - 1; ++i) {
        // Reset swapped to false at the start of each pass
        swapped = false; 
 
        // Stop at arr.size()-1-i to avoid checking sorted elements
        for(int j = 0; j < arr.size() - 1 - i; ++j) {
            // Swap adjacent elements if they are in the wrong order
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]); 
                // Set swapped to true indicating a swap occurred
                swapped = true; 
            }
        }
        
        // If no elements were swapped, 
        // the arr is sorted and we can break early
        if(!swapped)
            break;
    }
}

Best Case Time Complexity: O(n)

The best-case time complexity occurs when the data is already sorted. Consider this data:

4, 16, 17, 18

In the case of sorted data, the inner loop will only run once and terminate as no swaps are made. This results in the best-case time complexity of O(n).

Worst Case Time Complexity: <katex>O(n^{2})</katex>

The worst-case time complexity occurs when the input data is in reverse order. Consider another set of data:

18, 17, 16, 4

When the data is in reverse order, each element is farthest from its correct position. So, two nested loops perform pairwise comparisons and swaps for each element.

Therefore, the time complexity becomes <katex>O(n^{2})</katex>.

Average Case Time Complexity: <katex>O(n^{2})</katex>

In the average case, the elements are in random order. For example,

17, 18, 4, 16

In this case, the algorithm needs to swap almost half of the elements while it performs a pairwise comparison for each element.

This results in the average case time complexity of <katex>O(n^{2})</katex>.

Space Complexity of Bubble Sort: O(1)

Bubble sort is an in-place algorithm—it sorts data directly within the array without additional memory, apart from a few variables used for swapping (swapped) and counting (i).

The memory usage does not grow with the size of the input. Regardless of whether you are sorting 10 elements or 10,000, the same fixed amount of memory is used for the variables.

Hence, the space complexity of bubble sort is O(1).

When to Use Bubble Sort?

Bubble sort is a memory-efficient algorithm with a space complexity of O(1), making it suitable for limited memory environments.

However, its quadratic time complexity (<katex>O(n^{2})</katex>) makes it inefficient for large datasets.

When to Use:

• Small datasets (for example, 10 elements): Bubble sort can be fast and efficient as the number of comparisons and swaps is not very high, even in the worst case.
• Nearly sorted data: Optimized bubble sort can achieve O(n) in the best case. So, if the data is predictable and very close to the best-case scenario, bubble sort can be used.

The table below shows the approximate number of comparisons and swaps in cases of small datasets and nearly sorted datasets:

This shows that the number of swaps and comparisons is quite small despite the quadratic time complexity.

When to Avoid:

• Large and unpredictable datasets: The inefficiency of <katex>O(n^{2})</katex> dominates in the case of large unsorted datasets, making other algorithms like Quick Sort or Merge Sort more suitable.