{"title":"Bubble Sort","description":"","content":"Bubble Sort is one of the simplest sorting algorithms and often the first one people learn. The idea is straightforward: repeatedly compare adjacent elements and swap them if they are in the wrong order. With each pass, the largest unsorted element “bubbles up” to its correct position.\n\nWhile Bubble Sort is not efficient for large inputs, it plays an important role in building intuition. It helps you understand how sorting works step by step, how swaps affect order, and how repeated passes gradually lead to a sorted array.\n\nIn this chapter, you will learn how Bubble Sort works, how to implement it, and how small optimizations can improve its performance. More importantly, you will use it as a stepping stone to understand 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, much like a bubble rising to the surface of water. That is where the name comes from.\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\nThe analogy is simple. In 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\nLet us break down the algorithm step by step.\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 actually practical on nearly sorted data. Without it, you always run `n-1` passes even if the array becomes sorted after the second pass. With early termination, if a pass completes with zero swaps, you know the array is already in order and 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\nThere are two things worth noting in this flowchart. First, 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. Second, the `swapped` flag is reset 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\nAll six implementations follow the same structure: 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. The only differences are language syntax.\n\n\n\n\n---\n\n# Example Walkthrough\n\nLet us trace through bubble sort with the array `[5, 3, 8, 4, 2]`. We will track every comparison and swap so you can see exactly how the algorithm progresses.\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\nNotice how the inner loop range shrinks with each pass. In pass 1 we made 4 comparisons, in pass 2 we made 3, then 2, then 1. The total number of comparisons is `4 + 3 + 2 + 1 = 10`, which is `n(n-1)/2` for `n=5`. This is exactly where the O(n^2) comes from.\n\nNow let us look at the best-case scenario. If the input were already sorted, say `[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\nThis is why the `swapped` flag matters so much. Without it, bubble sort would still run all `n-1` passes, doing `n(n-1)/2` comparisons for an already sorted array. With it, the best case drops to O(n).\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:** Bubble sort is a stable sorting algorithm. Two elements with equal values are never swapped (because the condition is strictly greater than, not greater-than-or-equal). This means equal elements maintain their original relative order after sorting.\n\n**In-place:** Bubble sort does not require any additional arrays or data structures. All swaps happen within the original array, making the space complexity O(1).\n\nTo put the numbers in perspective, for an array of 10,000 elements:\n\n- Best case (already sorted): roughly 10,000 comparisons\n- Worst case (reverse sorted): roughly 50,000,000 comparisons\n\nThat is a 5,000x difference, which is why the early termination optimization is not just a nice-to-have. It fundamentally changes the algorithm's behavior on nearly sorted data.\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 tells you whether the array is already in order. This costs O(n) and uses O(1) space.\n- **Teaching and learning.** Bubble sort is the simplest comparison-based sorting algorithm. It is the perfect 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#### **Bad use cases:**\n\n- **Large datasets.** O(n^2) is simply too slow for thousands of elements or more. Merge sort (O(n log n)) or quicksort (O(n log n) average) are dramatically 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. If every millisecond matters, you should not be using bubble 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 in practice because it does fewer swaps.\n\nA useful rule of thumb: if someone asks you about bubble sort in an interview, they are probably testing whether you understand its properties (stability, in-place, best case O(n)) and whether you can articulate why better alternatives exist. They are not asking you to advocate for using it in production.","pageType":"dsa"}

Bubble Sort

Ashish Pratap Singh

Get Premium