# bidirectional bubble sort

(algorithm)

**Definition:**
A variant of *bubble sort* that compares each adjacent pair of items in a *list* in turn, swapping them if necessary, and alternately passes through the list from the beginning to the end then from the end to the beginning. It stops when a pass does no swaps.

**Also known as** cocktail shaker sort, shaker sort, double-direction bubble sort.

**Generalization** (I am a kind of ...)

*sort*.

**See also**
*bubble sort*, *gnome sort*.

*Note:
Complexity is **O(n*^{2}) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning. Bidirectional bubble sort usually does better than bubble sort since at least one item is moved forward or backward to its place in the list with each pass. Bubble sort moves items forward into place, but can only move items backward one location each pass.

Authors: PEB,BB

## Implementation

demonstration and source code (Java); animation and code, see cocktail sort (Java).

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with
Paul E. Black.

Entry modified 24 August 2009.

HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:

Paul E. Black and Bob Bockholt, "bidirectional bubble sort", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 24 August 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bidirectionalBubbleSort.html