Cocktail Shaker Sort
- Ω( n )
- Θ( n2 )
- O( n2 )
- space O( 1 )
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How cocktail shaker sort works
Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, shaker sort, ripple sort, shuffle sort, or shuttle sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from bubble sort in that it sorts in both directions on each pass through the list. This sorting algorithm is only marginally more difficult to implement than bubble sort, and solves the problem of turtles in bubble sort.
Read more
The cocktail shaker sort is only marginally more efficient than bubble sort, so it is not often used in practice.
| Best time | Ω( n ) | good |
|---|---|---|
| Average time | Θ( n2 ) | poor |
| Worst time | O( n2 ) | poor |
| Worst space | O( 1 ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.