Bubble Sort

Bubble Sort

Description: 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 "bubble sort" comes from the way smaller elements "bubble" to the top (beginning) of the list.

How It Works

1. Initial Pass: Start at the beginning of the array.
2. Comparison: Compare each pair of adjacent elements.
3. Swap: If the first element is greater than the second, swap them.
4. Repeat: Continue this process for each pair until the end of the array is reached.
5. Multiple Passes: Repeat the entire pass over the array until no swaps are needed (indicating that the array is sorted).

Time Complexity

• Worst Case: $O(n^2)$ — occurs when the array is sorted in reverse order.
• Average Case: $O(n^2)$
• Best Case: $O(n)$ — occurs when the array is already sorted (with an optimized version).

Space Complexity

• Space Complexity: $O(1)$ — bubble sort is an in-place sorting algorithm, requiring a constant amount of additional storage.

Stability

• Stability: Bubble sort is a stable sorting algorithm. Equal elements maintain their relative order after sorting.

Example Code

Here's a C++ implementation of bubble sort:

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    bool swapped; // Flag to check if a swap was made
    for (int i = 0; i < n - 1; i++) {
        swapped = false; // Reset swap flag for this pass
        for (int j = 0; j < n - i - 1; j++) {
            // Compare adjacent elements
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]); // Swap if they're in the wrong order
                swapped = true; // Mark that a swap has occurred
            }
        }
        // If no swaps occurred, the array is already sorted
        if (!swapped)
            break;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Explanation of the Code

1. Function Definition: The bubbleSort function takes an array and its size as parameters.
2. Outer Loop: Iterates through the array, making passes to sort it.
3. Inner Loop: Compares each pair of adjacent elements and swaps them if necessary.
4. Swap Flag: The swapped flag tracks whether any swaps were made during a pass. If no swaps occur, the array is already sorted, and the loop can exit early.
5. Output: After sorting, the program prints the sorted array.

Conclusion

Bubble sort is a straightforward algorithm that is easy to understand and implement. However, its $O(n^2)$ time complexity makes it inefficient for large datasets compared to more advanced sorting algorithms like quick sort or merge sort. Despite its simplicity, bubble sort is often used in educational contexts to introduce sorting concepts.