Cocktail Shaker Sort
Bidirectional bubble sort that traverses in both directions.
Repeatedly swaps adjacent elements until the array is sorted.
Bubble Sort is one of the simplest and most widely taught sorting algorithms in computer science. It works by repeatedly stepping through the list, comparing each pair of adjacent elements, and swapping them if they are in the wrong order. The pass through the list is repeated until no more swaps are needed, indicating the list is sorted. The algorithm gets its name because smaller elements gradually "bubble" toward the top (beginning) of the list with each successive pass, while larger elements sink to the bottom (end).
Bubble Sort is one of the earliest sorting algorithms to be analyzed. Its first description in the literature dates to the 1950s, and it appeared in early programming textbooks as a straightforward introduction to sorting. Despite its simplicity, it has been the subject of ongoing debate. In 2005, Owen Astrachan published a paper titled "Bubble Sort: An Archaeological Algorithmic Analysis," arguing that Bubble Sort should no longer be taught because it is rarely the best choice even among simple sorts. Nonetheless, it remains a staple of introductory computer science courses worldwide because its logic is easy to follow and implement.
swapped flag during each pass. If a complete pass produces no swaps, the array is already sorted and the algorithm can terminate immediately.In pseudocode terms, the outer loop runs up to n-1 times, and the inner loop compares adjacent pairs, shrinking by one position each time since the end of the array accumulates sorted elements.
| Case | Time | Space |
|---|---|---|
| Best | O(n) | O(1) |
| Average | O(n²) | O(1) |
| Worst | O(n²) | O(1) |
The best case of O(n) only applies when the early-exit optimization is implemented and the input is already sorted -- a single pass with no swaps confirms this. Without the optimization, Bubble Sort always performs O(n^2) comparisons. On average, Bubble Sort makes approximately n^2/4 swaps, which is significantly more data movement than algorithms like Insertion Sort or Selection Sort.
Bubble Sort has an inherent asymmetry. Large elements near the beginning of the array move quickly to the end -- these are called "rabbits" because they leap forward by one position per comparison within a single pass. However, small elements near the end move only one position toward the beginning per pass -- these are called "turtles." A single turtle element can force the algorithm to use the maximum number of passes. This observation led to the invention of Cocktail Shaker Sort, which adds a backward pass, and Comb Sort, which uses a shrinking gap to move turtles faster.
Among simple O(n^2) sorting algorithms, Insertion Sort is almost always superior to Bubble Sort. Insertion Sort performs fewer comparisons on average, adapts naturally to partially sorted data, and shifts elements rather than performing costly adjacent swaps. Selection Sort makes fewer swaps overall -- at most O(n) -- but always performs O(n^2) comparisons regardless of input order.
Bubble Sort is primarily used for educational purposes to introduce sorting concepts, loop invariants, and algorithmic analysis. Its O(n) best case with the early-exit flag makes it acceptable when you can guarantee the data is nearly sorted. It is also useful as a baseline when benchmarking other sorting algorithms. For all practical purposes on datasets of any meaningful size, more efficient algorithms like Merge Sort, Quick Sort, or Timsort should be used instead.