Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

In general, given a collection of n unsorted elements, it takes (n-1) iterations through the list in order to sort it using the bubble sort algorithm.

How Bubble Sort Works

1. Start at the Beginning: Begin by comparing the first two elements of the list.

2. Comparison and Swap: Compare the two adjacent elements. If they are in the wrong order, swap them.

3. Move to the Next Pair: Move one position to the right and compare the next pair of elements.

4. Repeat Until Sorted: Continue comparing and swapping adjacent elements as you move through the list. Keep repeating these steps until you make a pass through the list without any swaps.

5. Completion: The list is considered sorted when a pass through the entire list results in no swaps.

Example:
Input: N = 5, array[] = {9,7,4,1,2}
Output: 9,7,4,1,2
Explanation: After sorting we get 1,2,4,7,9

We start off comparing the first two elements — 9 and 7—and, since they’re out of order, we swap them.

Next, we compare the second and third elements: 9 and 4. The number 9 is definitely bigger than 4, so it should come after. This means we have to swap these two elements as well.

The next two elements are 9 and 1. Again, the 9 should come after the 1, and not before, which means we need to swap again. Finally, we’re on the last two elements in this iteration: 9 and 2. The number 2 should definitely come before 9, so we’ll swap these two elements so that they’re in the correct order.

Phew! That was just one single iteration of bubble sort. And our list isn’t even sorted yet. We’d need to keep repeating this set of actions again and again until the entire collection of elements was sorted. If this was just a single iteration, there’s one big question on my mind now: how many times would we have to iterate in order to sort the entire collection? Imagine if we had a list of 10 or 20, or 50 unsorted elements — I really don’t want to iterate through each set in order to know how much work it’s going to be!

Pseudocode

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; 
    }
}

Advantages

Simple Implementation: Easy to understand and implement.

In-Place Sorting: It does not require additional memory.

Disadvantages

Inefficient for Large Arrays: Performs poorly with larger datasets.

Quadratic Time Complexity: Has a time complexity of O(n^2), which makes it unsuitable for larger lists.