{"title":"Bubble Sort","description":"","content":"Bubble Sort is one of the simplest sorting algorithms and is usually the first one taught in an algorithms course. It is not efficient for large inputs, but it is a useful starting point for building sorting intuition. It shows how sorting works step by step, how swaps affect order, and how repeated passes gradually lead to a sorted array.\n\n\n\n\n\nThis chapter covers how Bubble Sort works, how to implement it, and how a small optimization changes its behavior on nearly sorted data. It also serves as a stepping stone for understanding why more advanced sorting algorithms are needed.\n\n---\n\n# What Is Bubble Sort?\n\nBubble sort is a comparison-based sorting algorithm that works by repeatedly stepping through the array, comparing adjacent elements, and swapping them if they are in the wrong order. Each pass through the array moves the largest unsorted element to its correct position at the end.\n\nHere is the core intuition: after the first pass, the largest element is guaranteed to be at the last position. After the second pass, the second-largest element is in its correct spot. After `n-1` passes, the entire array is sorted.\n\n### Example\n\n\n```mermaid\nflowchart TB\n subgraph Before[\"Before Pass\"]\n\t\tdirection TB\n A1[\"5\"]:::red\n A2[\"3\"]:::primary\n A3[\"8\"]:::primary\n A4[\"4\"]:::primary\n A5[\"2\"]:::primary\n end\n\n subgraph During[\"Bubbling\"]\n\t\tdirection TB\n B1[\"3\"]:::primary\n B2[\"5\"]:::primary\n B3[\"4\"]:::primary\n B4[\"2\"]:::primary\n B5[\"8\"]:::red\n end\n\n subgraph After[\"After Pass 1\"]\n\t\tdirection TB\n C1[\"3\"]:::primary\n C2[\"5\"]:::primary\n C3[\"4\"]:::primary\n C4[\"2\"]:::primary\n C5[\"8\"]:::green\n end\n\n Before --> During --> After\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe element `8`, being the largest, bubbles to the far right after the first pass. In the next pass, `5` will bubble to its correct position (second from the right), and so on. Each pass guarantees that one more element is sorted.\n\n### Why \"Bubble\"?\n\nIn a carbonated drink, larger bubbles rise to the surface faster. In bubble sort, larger values rise (move toward the end of the array) faster because they keep getting swapped forward with every comparison.\n\n---\n\n# How It Works\n\nThe algorithm has seven steps:\n\n1. Start at the beginning of the array.\n2. Compare the current element with the next element.\n3. If the current element is greater than the next element, swap them.\n4. Move to the next pair and repeat steps 2-3.\n5. After completing one full pass, the largest unsorted element is now at the end.\n6. Repeat the process for the remaining unsorted portion of the array.\n7. Stop when no swaps are made during a pass (this means the array is sorted).\n\nStep 7 is the optimization that makes bubble sort practical on nearly sorted data. Without it, the algorithm runs `n-1` passes even if the array becomes sorted after the second pass. With early termination, a pass that completes with zero swaps signals that the array is already in order, so the algorithm can stop immediately.\n\nHere is the algorithm as a flowchart:\n\n\n```mermaid\nflowchart TD\n START[\"Start\"]:::primary\n INIT[\"Set n = array length\"]:::primary\n OUTER[\"For i = 0 to n-2\"]:::secondary\n FLAG[\"Set swapped = false\"]:::teal\n INNER[\"For j = 0 to n-i-2\"]:::secondary\n COMPARE{\"arr[j] > arr[j+1]?\"}:::yellow\n SWAP[\"Swap arr[j] and arr[j+1]
Set swapped = true\"]:::orange\n NEXT[\"Move to next pair\"]:::primary\n CHECK{\"swapped == false?\"}:::yellow\n DONE[\"Array is sorted\"]:::green\n\n START --> INIT --> OUTER --> FLAG --> INNER --> COMPARE\n COMPARE -- Yes --> SWAP --> NEXT\n COMPARE -- No --> NEXT\n NEXT --> |\"More pairs?\"| INNER\n NEXT --> |\"Pass complete\"| CHECK\n CHECK -- Yes --> DONE\n CHECK -- No --> OUTER\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef yellow fill:#ffd43b,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe flowchart highlights two details. The inner loop range shrinks by one after each pass (`n-i-2` instead of `n-2`) because the last `i` elements are already sorted. The `swapped` flag resets at the start of every pass, so it tracks whether any work was done in the current pass only.\n\n---\n\n# Code Implementation\n\n\n```java\npublic class BubbleSort {\n public static void bubbleSort(int[] arr) {\n int n = arr.length;\n\n for (int i = 0; i < n - 1; i++) {\n boolean swapped = false;\n\n // Last i elements are already in place\n for (int j = 0; j < n - i - 1; j++) {\n if (arr[j] > arr[j + 1]) {\n // Swap arr[j] and arr[j+1]\n int temp = arr[j];\n arr[j] = arr[j + 1];\n arr[j + 1] = temp;\n swapped = true;\n }\n }\n\n // If no swaps happened, array is already sorted\n if (!swapped) {\n break;\n }\n }\n }\n}\n```\n\n```python\ndef bubble_sort(arr):\n n = len(arr)\n\n for i in range(n - 1):\n swapped = False\n\n # Last i elements are already in place\n for j in range(n - i - 1):\n if arr[j] > arr[j + 1]:\n # Swap arr[j] and arr[j+1]\n arr[j], arr[j + 1] = arr[j + 1], arr[j]\n swapped = True\n\n # If no swaps happened, array is already sorted\n if not swapped:\n break\n```\n\n```cpp\n#include \n\nvoid bubbleSort(std::vector& arr) {\n int n = arr.size();\n\n for (int i = 0; i < n - 1; i++) {\n bool swapped = false;\n\n // Last i elements are already in place\n for (int j = 0; j < n - i - 1; j++) {\n if (arr[j] > arr[j + 1]) {\n // Swap arr[j] and arr[j+1]\n std::swap(arr[j], arr[j + 1]);\n swapped = true;\n }\n }\n\n // If no swaps happened, array is already sorted\n if (!swapped) {\n break;\n }\n }\n}\n```\n\n```go\npackage main\n\n// BubbleSort sorts the array using bubble sort.\nfunc BubbleSort(arr []int) {\n\tn := len(arr)\n\n\tfor i := 0; i < n-1; i++ {\n\t\tswapped := false\n\n\t\t// Last i elements are already in place\n\t\tfor j := 0; j < n-i-1; j++ {\n\t\t\tif arr[j] > arr[j+1] {\n\t\t\t\t// Swap arr[j] and arr[j+1]\n\t\t\t\tarr[j], arr[j+1] = arr[j+1], arr[j]\n\t\t\t\tswapped = true\n\t\t\t}\n\t\t}\n\n\t\t// If no swaps happened, array is already sorted\n\t\tif !swapped {\n\t\t\tbreak\n\t\t}\n\t}\n}\n```\n\n```csharp\npublic class BubbleSort {\n public static void Sort(int[] arr) {\n int n = arr.Length;\n\n for (int i = 0; i < n - 1; i++) {\n bool swapped = false;\n\n // Last i elements are already in place\n for (int j = 0; j < n - i - 1; j++) {\n if (arr[j] > arr[j + 1]) {\n // Swap arr[j] and arr[j+1]\n int temp = arr[j];\n arr[j] = arr[j + 1];\n arr[j + 1] = temp;\n swapped = true;\n }\n }\n\n // If no swaps happened, array is already sorted\n if (!swapped) {\n break;\n }\n }\n }\n}\n```\n\n```rust\npub struct BubbleSort;\n\nimpl BubbleSort {\n pub fn sort(arr: &mut Vec) {\n let n = arr.len();\n\n for i in 0..n.saturating_sub(1) {\n let mut swapped = false;\n\n // Last i elements are already in place\n for j in 0..n - i - 1 {\n if arr[j] > arr[j + 1] {\n // Swap arr[j] and arr[j+1]\n arr.swap(j, j + 1);\n swapped = true;\n }\n }\n\n // If no swaps happened, array is already sorted\n if !swapped {\n break;\n }\n }\n }\n}\n```\n\n```javascript\nfunction bubbleSort(arr) {\n const n = arr.length;\n\n for (let i = 0; i < n - 1; i++) {\n let swapped = false;\n\n // Last i elements are already in place\n for (let j = 0; j < n - i - 1; j++) {\n if (arr[j] > arr[j + 1]) {\n // Swap arr[j] and arr[j+1]\n [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];\n swapped = true;\n }\n }\n\n // If no swaps happened, array is already sorted\n if (!swapped) {\n break;\n }\n }\n}\n```\n\n```typescript\nfunction bubbleSort(arr: number[]): void {\n const n = arr.length;\n\n for (let i = 0; i < n - 1; i++) {\n let swapped = false;\n\n // Last i elements are already in place\n for (let j = 0; j < n - i - 1; j++) {\n if (arr[j] > arr[j + 1]) {\n // Swap arr[j] and arr[j+1]\n [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];\n swapped = true;\n }\n }\n\n // If no swaps happened, array is already sorted\n if (!swapped) {\n break;\n }\n }\n}\n```\n\n\nThe implementation has three parts: an outer loop that counts passes, an inner loop that does comparisons and swaps within a pass, and an early termination check at the end of each pass.\n\n\n\n\n\n---\n\n# Example Walkthrough\n\nTrace bubble sort on the array `[5, 3, 8, 4, 2]`, tracking every comparison and swap.\n\n\n```shell\nInitial array: [5, 3, 8, 4, 2]\n\nPass 1 (i=0): inner loop runs from j=0 to j=3\n j=0: Compare 5 and 3 → 5 > 3, swap → [3, 5, 8, 4, 2]\n j=1: Compare 5 and 8 → 5 < 8, no swap → [3, 5, 8, 4, 2]\n j=2: Compare 8 and 4 → 8 > 4, swap → [3, 5, 4, 8, 2]\n j=3: Compare 8 and 2 → 8 > 2, swap → [3, 5, 4, 2, 8]\n swapped = true, continue\n Result: [3, 5, 4, 2, | 8] (8 is now in its final position)\n\nPass 2 (i=1): inner loop runs from j=0 to j=2\n j=0: Compare 3 and 5 → 3 < 5, no swap → [3, 5, 4, 2, 8]\n j=1: Compare 5 and 4 → 5 > 4, swap → [3, 4, 5, 2, 8]\n j=2: Compare 5 and 2 → 5 > 2, swap → [3, 4, 2, 5, 8]\n swapped = true, continue\n Result: [3, 4, 2, | 5, 8] (5 is now in its final position)\n\nPass 3 (i=2): inner loop runs from j=0 to j=1\n j=0: Compare 3 and 4 → 3 < 4, no swap → [3, 4, 2, 5, 8]\n j=1: Compare 4 and 2 → 4 > 2, swap → [3, 2, 4, 5, 8]\n swapped = true, continue\n Result: [3, 2, | 4, 5, 8] (4 is now in its final position)\n\nPass 4 (i=3): inner loop runs from j=0 to j=0\n j=0: Compare 3 and 2 → 3 > 2, swap → [2, 3, 4, 5, 8]\n swapped = true, continue\n Result: [2, | 3, 4, 5, 8] (3 is now in its final position)\n\nFinal sorted array: [2, 3, 4, 5, 8]\n```\n\n\nThe inner loop range shrinks with each pass: 4 comparisons in pass 1, then 3, then 2, then 1. The total is `4 + 3 + 2 + 1 = 10`, which equals `n(n-1)/2` for `n = 5`. This is where the O(n^2) complexity comes from.\n\nCompare this with the best-case scenario on an already sorted input like `[1, 2, 3, 4, 5]`:\n\n\n```shell\nInitial array: [1, 2, 3, 4, 5]\n\nPass 1 (i=0): inner loop runs from j=0 to j=3\n j=0: Compare 1 and 2 → 1 < 2, no swap\n j=1: Compare 2 and 3 → 2 < 3, no swap\n j=2: Compare 3 and 4 → 3 < 4, no swap\n j=3: Compare 4 and 5 → 4 < 5, no swap\n swapped = false → STOP (early termination)\n\nArray is sorted after just 1 pass with 4 comparisons.\n```\n\n\nThe `swapped` flag is what drops the best case to O(n). Without it, bubble sort still runs all `n-1` passes and does `n(n-1)/2` comparisons even on an already sorted array.\n\n---\n\n# Complexity Analysis\n\n\n| Case | Time Complexity | Explanation |\n|------|----------------|-------------|\n| Best | O(n) | Array is already sorted. One pass with no swaps triggers early termination. We make `n-1` comparisons and zero swaps. |\n| Average | O(n^2) | Elements are in random order. On average, about half the pairs need swapping, but the nested loop structure still gives us quadratic time. |\n| Worst | O(n^2) | Array is sorted in reverse order. Every pair in every pass requires a swap. We make exactly `n(n-1)/2` comparisons and swaps. |\n| Space | O(1) | Bubble sort is in-place. It only uses a constant amount of extra memory for the temporary swap variable and the `swapped` flag. |\n\n\n### Stability\n\nBubble sort is stable. The swap condition uses strict greater-than (`arr[j] > arr[j+1]`), so two elements with equal values are never swapped. Equal elements retain their original relative order after sorting.\n\nThis matters when sorting records by a secondary key while preserving the order from a previous primary-key sort. For example, sorting employees by salary after first sorting by name produces employees grouped by salary, with each salary group still in name order.\n\nFor an array of 10,000 elements, the gap between inputs is large:\n\n- Best case (already sorted): roughly 10,000 comparisons\n- Worst case (reverse sorted): roughly 50,000,000 comparisons\n\nThe early termination check is what creates the best case. On an already sorted array, the `swapped` flag stops the algorithm after one pass of about 10,000 comparisons. Without the flag, the same input would still run all `n-1` passes and do `n(n-1)/2`, roughly 50,000,000 comparisons. That is a 5,000x reduction in work on input that is already in order.\n\n---\n\n# When to Use and When Not to Use\n\nBubble sort is rarely the right choice for production code, but it does have legitimate use cases.\n\n### Good Use Cases\n\n- **Nearly sorted data.** If the array is almost sorted (only a few elements are out of place), the early termination optimization makes bubble sort run close to O(n). This is one of the few scenarios where bubble sort can compete with more advanced algorithms.\n- **Small arrays.** For arrays with fewer than 20-30 elements, the overhead of more complex algorithms like merge sort or quicksort is not worth it. The constant factors matter, and bubble sort's simplicity becomes an advantage.\n- **Detecting if an array is sorted.** One pass of bubble sort with the `swapped` flag determines whether the array is already in order. This costs O(n) time and uses O(1) space.\n- **Teaching and learning.** Bubble sort is the simplest comparison-based sorting algorithm, which makes it a good starting point for understanding sorting concepts, loop invariants, and algorithm analysis.\n- **Memory-constrained environments.** Since bubble sort is in-place and uses O(1) extra space, it works in situations where you cannot afford to allocate additional arrays.\n\n### Poor Use Cases\n\n- **Large datasets.** O(n^2) is too slow for thousands of elements or more. Merge sort (O(n log n)) or quicksort (O(n log n) average) are significantly better choices.\n- **Performance-critical applications.** Even on medium-sized arrays, the number of swaps bubble sort makes is much higher than alternatives like insertion sort.\n- **Random or reverse-sorted data.** Bubble sort has no meaningful advantage over other quadratic algorithms on random data, and insertion sort typically outperforms it because it does fewer swaps.\n\nThe value of bubble sort is conceptual. Its simplicity makes it a good place to see what stability, in-place sorting, and a best case of O(n) actually mean, and understanding why faster algorithms exist starts with understanding why this one is slow.\n\n---\n\n# Quiz","pageType":"dsa"}

Get Premium