Sorting Algorithms

Bubble Sort: The Gentle Giant of Sorting

A simple, intuitive look at how Bubble Sort works, and why it's a great algorithm for beginners.

What is Bubble Sort?

Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until the list is sorted. The name comes from the way smaller or larger elements "bubble" up to their correct position in the array.

While not efficient for large datasets (it has an average and worst-case complexity of $O(n^2)$), its simplicity makes it an excellent algorithm for learning the fundamental concepts of sorting.

Step-by-Step Example

Let's sort the array A = [5, 1, 4, 2, 8] in ascending order.

Pass 1

• (5, 1) : Swap, because $5 > 1$. Array becomes [1, 5, 4, 2, 8]
• (5, 4) : Swap, because $5 > 4$. Array becomes [1, 4, 5, 2, 8]
• (5, 2) : Swap, because $5 > 2$. Array becomes [1, 4, 2, 5, 8]
• (5, 8) : No swap, because $5 < 8$. Array is [1, 4, 2, 5, 8]
• Result of Pass 1: The largest element (8) is now in its correct final position at the end (though it wasn't moved in this step, 5 was). The largest element, 8, is *guaranteed* to be at $A[n-1]$ by the end of Pass 1.

Pass 2

• (1, 4) : No swap. Array is [1, 4, 2, 5, 8]
• (4, 2) : Swap, because $4 > 2$. Array becomes [1, 2, 4, 5, 8]
• (4, 5) : No swap. Array is [1, 2, 4, 5, 8]
• Result of Pass 2: The second largest element (5) is now in its correct final position. The list is now sorted.

Final Sorted Array: [1, 2, 4, 5, 8]

Bubble Sort Algorithm (Pseudocode)

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    // Repeat for (n-1) passes
    for i from 0 to n-2 do
        // Last i elements are already in place, so we don't check them.
        for j from 0 to n-2-i do
            // Compare adjacent elements
            if A[j] > A[j+1] then
                // Swap A[j] and A[j+1]
                swap( A[j], A[j+1] )
            end if
        end for
    end for
end procedure

Complexity Analysis of Bubble Sort

The performance of any algorithm is typically measured by its time complexity (how runtime scales with input size) and space complexity (how much extra memory it requires).

Time Complexity:

$O(n^2)$

Worst and Average Case. This means the time grows quadratically with the number of items ($n$).

Auxiliary Space:

$O(1)$

It only requires a single temporary variable for swapping, hence minimal extra memory.

Please refer Complexity Analysis of Bubble Sort for details.

Advantages

• Bubble sort is easy to understand and implement, making it ideal for beginners.
• It does not require any additional memory space (in-place sorting).
• It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in the sorted output.

Disadvantages

• Bubble sort has a time complexity of $O(n^2)$ which makes it very slow for large data sets.
• Due to its poor performance, Bubble Sort has almost no or limited real-world applications outside of highly specific, small-scale scenarios. It is primarily used in academics to teach different ways of sorting.

C Program Implementation

#include <stdio.h>

// Function to swap two elements
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// Function to implement Bubble Sort
void bubbleSort(int arr[], int n) {
    int i, j;
    // Outer loop for the number of passes (n-1)
    for (i = 0; i < n - 1; i++) {
        // Inner loop for comparisons in each pass.
        // The largest element "bubbles up" to the end with each pass,
        // so we can reduce the inner loop limit by 'i'.
        for (j = 0; j < n - i - 1; j++) {
            // Compare adjacent elements and swap if the current element
            // is greater than the next element (for ascending order).
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver code to test the function
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    bubbleSort(arr, n);

    printf("Sorted array (using Bubble Sort): \n");
    printArray(arr, n);

    return 0;
}

This C implementation demonstrates the core logic: two nested loops and a swap mechanism. The outer loop controls the number of passes, and the inner loop performs the actual comparisons and swaps.

Final Thoughts on Bubble Sort

Bubble Sort is fantastic for educational purposes because it's so intuitive. While you won't use it for production systems with millions of data points, understanding it is a crucial first step into the world of complex algorithms like Merge Sort or Quick Sort.