Bubble Sort Algorithm

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. The process is repeated until the list is sorted. This algorithm gets its name because larger elements "bubble" to the top (end) of the list.

Implementation of Bubble Sort

Standard Bubble Sort

// Time Complexity: O(n*n) (where n = size of the array)
// for the worst, average and best cases.
// Space Complexity: O(1)
void bubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

Logic:

1. Outer Loop: Iterate from the start of the array to the second last element.

2. Inner Loop: For each pass, compare adjacent elements.

• If the current element is greater (or smaller, depending on sorting order) than the next element, swap them.

3. Progressive Shortening: With each pass, the largest (or smallest, depending on sorting order) unsorted element is bubbled to its correct position, so the range of the inner loop is reduced.

Time Complexity: O(n²)

• Explanation: Two nested loops each iterating up to n times result in O(n²) time complexity for all (best, worst and average) cases.

Space Complexity: O(1)

• Explanation: The algorithm sorts in place and uses a constant amount of extra space.

---

Optimized Bubble Sort

// Time Complexity: O(n*n) (where n = size of the array)
// for the worst and average cases &
// O(n) for the best case.
// Space Complexity: O(1)
void bubbleSortOptimized(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        bool didSwap = false;

        for (int j = 0; j < n - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                didSwap = true;
            }
        }

        if (!didSwap)
        {
            break;
        }
    }
}

Logic:

1. Outer Loop: Iterate from the start of the array to the second last element.

2. Inner Loop: For each pass, compare adjacent elements.

• If the current element is greater (or smaller, depending on sorting order) than the next element, swap them and set didSwap to true.

3. Early Termination: If no elements were swapped in the inner loop, the array is already sorted and the algorithm can terminate early.

Time Complexity:

• Worst and Average Cases: O(n²)

• Best Case: O(n) when the array is already sorted.

Space Complexity: O(1)

• Explanation: The algorithm sorts in place and uses a constant amount of extra space.

Example

Input: arr = [13, 46, 24, 50, 20, 9], n = 6

Output: arr = [9, 13, 20, 24, 46, 50]

Explanation: The algorithm repeatedly compares and swaps adjacent elements if they are in the wrong order. This process continues until the array is sorted.

---

Step-by-Step Explanation

Let's break down the steps for the example input arr = [13, 46, 24, 50, 20, 9] using the standard Bubble Sort:

1. Initial Array: [13, 46, 24, 50, 20, 9]

2. Pass 1:

• Array at the start of Pass 1: [13, 46, 24, 50, 20, 9]

• Compare 13 and 46: No swap [13, 46, 24, 50, 20, 9]

• Compare 46 and 24: Swap [13, 24, 46, 50, 20, 9]

• Compare 46 and 50: No swap [13, 24, 46, 50, 20, 9]

• Compare 50 and 20: Swap [13, 24, 46, 20, 50, 9]

• Compare 50 and 9: Swap [13, 24, 46, 20, 9, 50]

• Array after pass 1: [13, 24, 46, 20, 9, 50]

3. Pass 2:

• Array at the start of Pass 2: [13, 24, 46, 20, 9, 50]

• Compare 13 and 24: No swap [13, 24, 46, 20, 9, 50]

• Compare 24 and 46: No swap [13, 24, 46, 20, 9, 50]

• Compare 46 and 20: Swap [13, 24, 20, 46, 9, 50]

• Compare 46 and 9: Swap [13, 24, 20, 9, 46, 50]

• Array after pass 2: [13, 24, 20, 9, 46, 50]

4. Pass 3:

• Array at the start of Pass 3: [13, 24, 20, 9, 46, 50]

• Compare 13 and 24: No swap [13, 24, 20, 9, 46, 50]

• Compare 24 and 20: Swap [13, 20, 24, 9, 46, 50]

• Compare 24 and 9: Swap [13, 20, 9, 24, 46, 50]

• Array after pass 3: [13, 20, 9, 24, 46, 50]

5. Pass 4:

• Array at the start of Pass 4: [13, 20, 9, 24, 46, 50]

• Compare 13 and 20: No swap [13, 20, 9, 24, 46, 50]

• Compare 20 and 9: Swap [13, 9, 20, 24, 46, 50]

• Array after pass 4: [13, 9, 20, 24, 46, 50]

6. Pass 5:

• Array at the start of Pass 5: [13, 9, 20, 24, 46, 50]

• Compare 13 and 9: Swap [9, 13, 20, 24, 46, 50]

• Array after pass 5: [9, 13, 20, 24, 46, 50]

7. Final Sorted Array: [9, 13, 20, 24, 46, 50]

Visualization

---

Edge Cases

• Already Sorted Array: The optimized version will terminate early, resulting in O(n) time complexity.

• Array with Identical Elements: The algorithm will handle duplicates correctly.

• Single Element Array: No swaps needed, the array remains unchanged.

Additional Notes

• Inefficiency: Due to its O(n²) time complexity, Bubble Sort is inefficient for large datasets compared to more advanced algorithms like Quick Sort or Merge Sort.

• Stability: Bubble Sort is stable, meaning it maintains the relative order of elements with equal keys.

• Use Case: Useful for small datasets or when the simplicity of implementation is more important than performance.

Conclusion

Bubble Sort is a fundamental sorting algorithm that provides a clear introduction to the concept of sorting. Although not suitable for large datasets due to its quadratic time complexity, it is easy to understand and implement. The optimized version improves efficiency by terminating early if the array is already sorted. Its simplicity and in-place sorting capability are its main advantages.

---