Bubble Sort Algorithm (C++)

[qingquan-li]

1. What is Bubble Sort Algorithm

Bubble sort is a simple comparison-based sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm gets its name because smaller elements "bubble" to the beginning of the list, while larger elements "sink" to the end. Bubble sort is easy to understand and implement but is generally inefficient for large datasets.

The main steps of the bubble sort algorithm are:

1. Iterate through the array from the first element to the second-to-last element. (Because it will be compared with the last element in the array during this process. There is no need to compare the last element with a non-existent "next" element.)
2. Compare the current element with the next element. If they are in the wrong order, swap them.
3. Repeat steps 1 and 2 for the entire array, excluding the last sorted element after each iteration (as it is already in its correct position).
4. Continue iterating through the array until no more swaps are needed, which indicates that the array is sorted.

The time complexity of the bubble sort algorithm is O(n^2) in the worst and average cases, but it has a best-case complexity of O(n) when the input array is already sorted. Despite its simplicity, bubble sort is not recommended for large datasets due to its poor performance compared to more efficient sorting algorithms like quicksort and merge sort. Compared to insertion sort and selection sort, if the input array is already partially sorted or has only a few elements out of place, bubble sort can perform better due to its adaptive nature.

2. How it Works

Example: Sort the array "5,2,6,3,1,4" in ascending order using bubble sort.

Index0	Index1	Index2	Index3	Index4	Index5
5	2	6	3	1	4
2	5	6	3	1	4
2	5	3	6	1	4
2	5	3	1	6	4
2	5	3	1	4	6
2	3	5	1	4	6
2	3	1	5	4	6
2	3	1	4	5	6
2	1	3	4	5	6
1	2	3	4	5	6

3. C++ Code for the Bubble Sort Algorithm

#include <iostream>

// Function prototype
void bubbleSort(int[], int);

int main() {
    const int SIZE = 6;
    // Array of unsorted values
    int values[SIZE] = { 5, 2, 6, 3, 1, 4 };
    // Sort the array.
    bubbleSort(values, SIZE);
    // Display the sorted array.
    for (int element : values)
        std::cout << element << " ";
    return 0;
}

/**
 * Bubble sort function
 * @param array The array to sort
 * @param size  The size of the array
 */
void bubbleSort(int array[], int size) {
    // The maxElement variable will hold the subscript (index) of the
    // last element that is to be compared to its immediate neighbor.
    // In each pass, maxElement represents the index of the
    // last unsorted element in the array.
    int maxElement;
    int index;
    for (maxElement = size - 1; maxElement > 0; maxElement--) {
        for (index = 0; index < maxElement; index++) {
            if (array[index] > array[index + 1]) {
                std::swap(array[index], array[index + 1]);
            }
        }
    }
}

Another bubble sort function:

void bubbleSort(int array[], int size) {
    // The `pass` variable represents the current pass (iteration). In each pass, the largest
    // unsorted element "bubbles up" to its correct position in the array, reducing the size
    // of the unsorted portion of the array.
    // The outer loop iterates `size - 1` times in the worst case to ensure the array is
    // sorted completely. The pass variable helps control the number of passes over the array
    // and determines the range of the inner loop (which compares and swaps adjacent elements).
    for (int pass = 0; pass < size - 1; ++pass) {
        // The `index` variable represents the index of the current element in the array that
        // is being compared to its immediate neighbor (array[index + 1]) during each pass in
        // the inner loop. The inner loop iterates from the beginning of the array (index 0)
        // up to size - 1 - pass, which is the last unsorted element that needs to be compared
        // to its neighbor during each pass.
        for (int index = 0; index < size - 1 - pass; ++index) {
            if (array[index] > array[index + 1]) {
                std::swap(array[index], array[index + 1]);
            }
        }
    }
}

4. Time Complexity

Example: Given array: [5, 4, 3, 2, 1]

**Pass 1 (index = 0 to 3). Comparisons: 4:

Comparisons and Swaps	Index0	Index1	Index2	Index3	Index4
Compare 5 and 4, swap them -> [4, 5, 3, 2, 1]	5	4	3	2	1
Compare 5 and 3, swap them -> [4, 3, 5, 2, 1]	4	5	3	2	1
Compare 5 and 2, swap them -> [4, 3, 2, 5, 1]	4	3	5	2	1
Compare 5 and 1, swap them -> [4, 3, 2, 1, 5]	4	3	2	5	1
After the first pass, the largest element (5) has "bubbled up" to its correct position at the end of the array.	4	3	2	1	5

Pass 2 (index = 0 to 2). Comparisons: 3:

Comparisons and Swaps	Index0	Index1	Index2	Index3	Index4
Compare 4 and 3, swap them -> [3, 4, 2, 1, 5]	4	3	2	1	5
Compare 4 and 2, swap them -> [3, 2, 4, 1, 5]	3	4	2	1	5
Compare 4 and 1, swap them -> [3, 2, 1, 4, 5]	3	2	4	1	5
After the second pass, the second-largest element (4) has "bubbled up" to its correct position (index 3), just before the largest element (5).	3	2	1	4	5

Pass 3 (index = 0 to 1). Comparisons: 2:

Comparisons and Swaps	Index0	Index1	Index2	Index3	Index4
Compare 3 and 2, swap them -> [2, 3, 1, 4, 5]	3	2	1	4	5
Compare 3 and 1, swap them -> [2, 1, 3, 4, 5]	2	3	1	4	5
After the third pass, the third-largest element (3) has "bubbled up" to its correct position (index 2).	2	1	3	4	5

Pass 4 (index = 0 to 0). Comparisons: 1:

Comparisons and Swaps	Index0	Index1	Index2	Index3	Index4
Compare 2 and 1, swap them -> [1, 2, 3, 4, 5]	2	1	3	4	5
After the fourth pass, the second-smallest element (2) has "bubbled up" to its correct position (index 1). Since there is only one element left in the unsorted portion of the array (the smallest element), there is no need for further passes.	1	2	3	4	5

After the 4th pass, the array is sorted, and the algorithm terminates. The sorted array is [1, 2, 3, 4, 5].

Comparisions are made in this (worst) case is 4 + 3 + 2 + 1 =10.

Comparisions are made in the worst case is: (n - 1) + (n - 2) + (n - 3) + ... + 1. (n is the number of array elements.)

As we know, 1 + 2 + 3 + ... + n = n * (n+1) / 2. So, the formula of the comparisons in the worst case is: (n - 1) * ( n - 1 + 1) / 2 = (n - 1) * n / 2

Using Big-O notation, the worst-case time complexity of bubble sort is:

lim n -> ∞ (n - 1) * n / 2 = lim n -> ∞ (n² -n) / 2 = n²

O(n²)