Bubble sort
Bubble sort is a simple comparison-based sorting algorithm that repeatedly iterates through an unsorted list, comparing adjacent elements and swapping them if they are in the wrong order, thereby gradually moving larger elements toward the end of the list in each pass, like bubbles rising to the surface.[1][2] The process continues for multiple passes until no further swaps are required, indicating the list is fully sorted.[3] The algorithm's origins trace back to at least 1956, when a variant was described in a thesis as a "filing scheme for establishing... sort order," though the term "bubble sort" first appeared in print in 1962, coined by Kenneth E. Iverson in reference to the way elements "bubble" to their correct positions.[4][5] Despite its simplicity, bubble sort has persisted in educational contexts as an introductory example of sorting, even as more efficient algorithms have been developed, due to its straightforward implementation and intuitive visualization of the sorting process.[6][7] In terms of performance, bubble sort has a time complexity of O(n²) in the worst and average cases, where n is the number of elements, due to the nested loops that perform up to n passes, each involving up to n comparisons and swaps.[8][9] The best-case time complexity is O(n) when the list is already sorted, as an early termination optimization can detect no swaps after a single pass.[8] Its space complexity is O(1), making it an in-place algorithm that requires no additional storage beyond the input array.[3][8] Bubble sort is stable, preserving the relative order of equal elements, which is a desirable property in certain applications like sorting records with secondary keys.[3] However, its quadratic time complexity renders it inefficient for large datasets compared to advanced algorithms like quicksort or mergesort, limiting its practical use to small lists or pedagogical demonstrations.[9][10] Variants, such as cocktail shaker sort, extend the basic approach by traversing the list in both directions to potentially reduce passes.Algorithm Description
Core Mechanism
Bubble sort is a simple comparison-based sorting algorithm that operates by repeatedly traversing a list of elements, comparing adjacent pairs, and swapping them if they are in the incorrect order relative to the desired sorting direction, such as ascending or descending.[8] This process ensures that misplaced elements gradually move toward their correct positions through successive iterations. The algorithm assumes the input is an array or list of comparable elements, such as integers or other data types that support a total ordering, and requires no prior knowledge of the data's sorted state.[11] The name "bubble sort" derives from the "bubbling" effect observed during execution, where the largest (in ascending sort) or smallest (in descending sort) elements progressively rise to the end of the list, akin to bubbles rising in a liquid.[12] In each traversal, an element that is out of place will be swapped multiple times with its neighbors until it reaches its appropriate position at the boundary of the unsorted portion, simulating this upward movement. This mechanism relies solely on pairwise comparisons and adjacent swaps, making it straightforward but inefficient for large datasets, with a quadratic time complexity that is explored in greater detail elsewhere.[11] The algorithm's structure involves an outer loop that controls the number of passes through the list, typically iterating n-1 times for a list of n elements, as each pass positions one more element correctly at the end.[13] Within each outer iteration, an inner loop performs the comparisons and swaps, starting from the beginning of the list and proceeding up to the last unsorted index, which decreases by one after each pass to avoid re-examining the already sorted suffix. This reduction in the inner loop's range ensures that only the unsorted portion is processed in subsequent passes, optimizing the comparisons without altering the core logic.[14]Step-by-Step Example
To illustrate the bubble sort algorithm, consider the following unsorted array of five elements: [5, 3, 8, 4, 2]. The process involves repeated passes over the array, where in each pass, adjacent elements are compared from left to right, and any pair that is out of order (with the larger element preceding the smaller one) is swapped. This "bubbling" action gradually moves larger elements toward the end of the array.[8] The table below shows the state of the array after each comparison and swap during the passes. For an array of n = 5 elements, the algorithm requires up to n-1 = 4 passes, though it can potentially terminate early if the array becomes fully sorted before completing all passes. In this example, swaps occur in every pass until the array is sorted.| Pass | Comparisons and Swaps | Array State After Pass |
|---|---|---|
| Initial | - | [5, 3, 8, 4, 2] |
| 1 (largest element bubbles to end) | Compare indices 0-1: 5 > 3, swap → [3, 5, 8, 4, 2] Compare indices 1-2: 5 < 8, no swap Compare indices 2-3: 8 > 4, swap → [3, 5, 4, 8, 2] Compare indices 3-4: 8 > 2, swap → [3, 5, 4, 2, 8] | [3, 5, 4, 2, 8] |
| 2 (second-largest bubbles to second-last position) | Compare indices 0-1: 3 < 5, no swap Compare indices 1-2: 5 > 4, swap → [3, 4, 5, 2, 8] Compare indices 2-3: 5 > 2, swap → [3, 4, 2, 5, 8] | [3, 4, 2, 5, 8] |
| 3 (third-largest bubbles to third-last position) | Compare indices 0-1: 3 < 4, no swap Compare indices 1-2: 4 > 2, swap → [3, 2, 4, 5, 8] | [3, 2, 4, 5, 8] |
| 4 (remaining elements sorted) | Compare indices 0-1: 3 > 2, swap → [2, 3, 4, 5, 8] | [2, 3, 4, 5, 8] (sorted) |
Analysis
Time and Space Complexity
Bubble sort exhibits a time complexity of O(n^2) in both the worst and average cases, where n is the number of elements in the array, as it performs \frac{n(n-1)}{2} comparisons regardless of the input arrangement.[15] This arises from the nested loop structure: the outer loop iterates n-1 times (from i = 0 to n-2), and the inner loop executes n - i - 1 comparisons per iteration of the outer loop.[15] The total number of comparisons is thus given by the summation \sum_{i=0}^{n-2} (n - i - 1) = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}, which is \Theta(n^2).[15] In the worst case, the number of swaps also reaches this upper bound of \frac{n(n-1)}{2}, occurring when the input is in reverse order.[15] In the best case, with a sorted input, bubble sort achieves O(n) time complexity, as no swaps are needed and early termination can be applied after a single pass.[15] Regarding space complexity, bubble sort requires O(1) auxiliary space, operating in-place on the input array without needing additional data structures beyond a few constant variables for indexing and swapping.[15]Performance Behaviors
Bubble sort is a stable sorting algorithm, meaning it preserves the relative order of elements with equal keys in the input array. This property arises because the algorithm only performs swaps between adjacent elements that are out of order, ensuring that equal elements are never swapped unnecessarily.[16][3] The algorithm exhibits partial adaptivity in that it can complete fewer passes through nearly sorted data when implemented with an early termination flag that checks for swaps in each pass; however, the basic version without such a flag remains quadratic in time complexity regardless of input order.[16][17] As an in-place sorting method, bubble sort requires no additional memory proportional to the input size beyond a constant amount for variables like indices and flags, making it suitable for environments with limited memory availability.[3][18] Despite these traits, bubble sort suffers from significant drawbacks in efficiency, including a high number of unnecessary comparisons even when the input is already sorted, as it always performs a fixed number of passes without early stopping. Additionally, its repeated traversals can lead to suboptimal cache performance in modern hardware due to the pattern of accesses, though its adjacent swaps maintain some locality.[19][20]Rabbits and Turtles Effect
In bubble sort, the rabbits and turtles effect describes the asymmetric movement patterns of elements during sorting, particularly evident in random input permutations. Rabbits refer to large elements positioned near the beginning of the array, which rapidly "bubble" to the right toward their final positions through successive swaps in early passes. In contrast, turtles denote small elements located near the end, which advance leftward slowly, often requiring nearly as many passes as the array length to reach the front.[21] This phenomenon arises from the algorithm's pairwise adjacent comparisons and swaps, where each pass fixes the largest unsorted element at the end but only shifts smaller elements one position leftward per iteration. According to Donald E. Knuth's analysis in random permutations, large elements tend to travel far to the right early in the process, as they participate in multiple swaps during initial passes, while small elements lag behind, often remaining misplaced until later stages.[22] For instance, in a conceptual random array of length n, the largest element starting at the beginning may undergo up to n-1 rightward swaps across the first pass alone if it is larger than all succeeding elements, yet smaller elements' progress remains gradual over subsequent passes. The rabbits and turtles effect contributes to bubble sort's inefficiency by elevating the total number of swaps beyond what might be expected from uniform element movement, as turtles necessitate additional full passes to resolve their positions. This pattern exacerbates the quadratic time complexity in average cases for random data, highlighting why variants like cocktail sort address turtles by incorporating reverse passes.[23]Implementation
Pseudocode
The standard pseudocode for the unoptimized bubble sort algorithm, which sorts an array of comparable elements in ascending order, is presented below. This formulation uses nested loops to iteratively compare and swap adjacent elements that are out of order, ensuring larger elements progressively "bubble" toward the end of the array.[24][25]The outer loop, indexed byprocedure bubbleSort(arr: array of integers, n: integer) for i from 0 to n-2 do for j from 0 to n-i-2 do if arr[j] > arr[j+1] then swap arr[j] and arr[j+1] end if end for end for end procedureprocedure bubbleSort(arr: array of integers, n: integer) for i from 0 to n-2 do for j from 0 to n-i-2 do if arr[j] > arr[j+1] then swap arr[j] and arr[j+1] end if end for end for end procedure
i from 0 to n-2, represents the n-1 passes through the array, where each pass fixes the position of the next largest element at the end.[24] The inner loop, indexed by j from 0 to n-i-2, performs adjacent pairwise comparisons and potential swaps up to the unsorted portion of the array, reducing the comparison range by one element per outer iteration to avoid redundant work on already-sorted suffixes.[25]
This pseudocode assumes 0-based indexing for the array and sorts elements in non-decreasing (ascending) order by using the strict greater-than (>) comparison, which only swaps when necessary.[24] It is stable, meaning that equal elements maintain their relative order since swaps occur only for strictly unequal adjacent pairs, preserving the original sequence of duplicates.[3] The algorithm can be adapted for descending order by replacing the > operator with < in the comparison.[26]
Language-Specific Examples
Bubble sort implementations in popular programming languages closely follow the abstract pseudocode structure, adapting to each language's syntax for data structures, loops, and element swapping. These examples demonstrate unoptimized versions that perform full passes regardless of early sorting, focusing on integer arrays or lists for clarity.Python
Python's dynamic typing and built-in list support enable concise implementations without explicit type declarations or size parameters beyond the list length. Swapping uses tuple assignment, which is efficient and readable.This function modifies the input list in place and returns nothing, aligning with Python's emphasis on mutable sequences.[10]pythondef bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j]def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j]
C++
In C++, arrays require explicit sizing and pointer handling, with the<algorithm> header providing std::swap for safe element exchange. The function operates on a fixed-size array passed by pointer, ensuring no bounds issues within the loops.
Static typing in C++ demands careful array management, differing from dynamic languages, and the void return type indicates in-place modification.[27]cpp#include <algorithm> // for std::swap void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } }#include <algorithm> // for std::swap void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } }
Java
Java's fixed-size arrays and object-oriented paradigm require length access via.length, with manual temporary variables for swapping to avoid built-in utilities in basic implementations. The static method suits utility classes for sorting.
Like C++, Java enforces static typing but includes automatic garbage collection, simplifying memory handling compared to manual allocation in C++.[11] These examples illustrate key language differences: Python prioritizes simplicity with dynamic structures, while C++ and Java emphasize explicit control over static arrays, all achieving in-place sorting without additional space beyond the input.javapublic static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
Optimizations and Variations
Standard Optimizations
One common optimization to the basic bubble sort algorithm involves reducing the range of the inner loop in each pass. After the ith pass, the last i elements are guaranteed to be in their correct sorted positions, so subsequent passes need only compare and swap up to the unsorted portion of the array, specifically from index 0 to n-i-2. This adjustment halves the number of comparisons in the unoptimized version, changing the total from (n-1)^2 to n(n-1)/2 for the worst case.[28] The following pseudocode illustrates this reduced inner loop:This optimization is inherent to the standard formulation of bubble sort and focuses on eliminating redundant checks on already-sorted suffixes.[17] A further enhancement introduces a boolean flag, often named "swapped," to enable early termination. At the start of each outer loop iteration, the flag is set to false; it is then set to true whenever a swap occurs in the inner loop. If the flag remains false after a full pass—indicating no swaps were needed—the array is fully sorted, and the algorithm can exit immediately. This prevents unnecessary passes over sorted data. The modified pseudocode incorporating both the reduced inner loop and the swapped flag is:for i from 0 to n-2: for j from 0 to n-i-2: if array[j] > array[j+1]: swap array[j] and array[j+1]for i from 0 to n-2: for j from 0 to n-i-2: if array[j] > array[j+1]: swap array[j] and array[j+1]
This flag-based approach is widely adopted in educational and practical implementations to improve efficiency on partially sorted inputs.[17][28] Another standard tweak is the cocktail shaker sort, a bidirectional variant that alternates passes from left-to-right and right-to-left to bubble both large and small elements toward their positions more quickly; however, its full mechanics are covered among notable variants.[5][29] These optimizations yield a best-case time complexity of O(n) for already sorted arrays due to early termination after one pass, while the average- and worst-case complexities remain O(n²), offering only marginal improvements for random inputs. Space complexity stays O(1) as an in-place algorithm.[30][17]swapped = true i = 0 while i < n-1 and swapped: swapped = false for j from 0 to n-i-2: if array[j] > array[j+1]: swap array[j] and array[j+1] swapped = true i = i + 1swapped = true i = 0 while i < n-1 and swapped: swapped = false for j from 0 to n-i-2: if array[j] > array[j+1]: swap array[j] and array[j+1] swapped = true i = i + 1