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
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:
Outer Loop: Iterate from the start of the array to the second last element.
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.
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
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:
Outer Loop: Iterate from the start of the array to the second last element.
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.
Early Termination: If no elements were swapped in the inner loop, the array is already sorted and the algorithm can terminate early.
Time Complexity:
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:
Initial Array: [13, 46, 24, 50, 20, 9]
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]
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]
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]
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]
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]
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.
