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. The pass through the list is repeated until no swaps are needed, which means the list is sorted. It is called bubble sort because smaller elements “bubble” at the top of the list during each pass.

 Working

1. Start: The algorithm starts at the beginning of the list (array) that you want to sort.
2. Comparison: It compares adjacent elements in the list. Initially, it compares the first two elements.
3. Swap if Necessary: If the element of the left is greater that the element on the right (i.e., they are in the wrong order), the algorithm swaps these two elements. This steps effectively "bubbles up" the larger element towards the end of the list in case of sorting in ascending order.
4. Move to the Next Pair: The algorithm moves on the next pair of adjacent elements and repeats the comparison and swapping process. This continues until it reaches the end of the list.
5. Repeat the Process: Steps 2-4 are repeated for each element in the list essentially performing a “pass” through the list.
6. Largest Element Bubbles to the End: After the first pass through the list, the largest element will have “bubbled up” to the end of the list because it was repeatedly swapped with smaller elements. This means that the larges element is now in its correct position.
7. Repeat Until No Swaps: The algorithm continues with subsequent passes through the list, but on each pass, it can ignore the last element since it is already in its correct position. The process continues until no more swaps are needed during a pass.
8. Termination: If no swaps were made during a pass, it means the list is fully sorted, and the algorithm terminates because the list is sorted.

Example:

Here's a simple example to illustrate how bubble sort works:

Original List: [5, 1, 4, 2, 8]

1st Pass:

• Compare 5 and 1, swap→[1,5,4,2,8]
• Compare 5 and 4, swap→[1,4,5,2,8]
• Compare 5 and 2, swap→[1,4,2,5,8]
• Compare 5 and 8, no swap
• The largest element (8) has bubbled to the end

2nd Pass:

• Compare 1 and 4, no swap
• Compare 4 and 2, swap→[1,2,4,5,8]
• Compare 4 and 5, no swap
• The second-largest element (5) has bubbled to the end.

3rd Pass:

• Compare 1 and 2, no swap
• Compare 2 and 4, no swap
• The third element (4) has bubbled to the end.

4th Pass:

• Compare 1 and 2, no swap
• The fourth-largest element (2) has bubbled to the end.

No more swaps are needed, so the list is sorted. The final sorted list is [1,2,4,5,8].

Code in C++

 #include <iostream>

void bubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j + 1]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // If no two elements were swapped in inner loop, the array is sorted.
        if (!swapped)
            break;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);
    
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

Complexity

Time Complexity:

• Best-case time complexity: O(n) - This occurs when the input array is already sorted, and no swaps are needed.
• Worst-case time complexity: O(n^2) - This occurs when the input is sorted in reverse order, and the maximum number of swaps is needed.
• Average-case time complexity: O(n^2) - In most cases, bubble sort will take this amount of time.

Space Complexity:

The space complexity of bubble sort is O(1) because it used a constant amount of extra space for temporary variables and loops.

Conclusion

Bubble sort is not considered an efficient sorting algorithm, especially for large datasets, due to its quadratic time complexity. There are more efficient sorting algorithm out there.