# 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** ```cpp // 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** ```cpp // 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 ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1717260948894/53e6a126-72bd-4256-b3ed-4ac753611f29.gif align="center") --- ### 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. ---