Cocktail sort

From Free net encyclopedia

Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort, ripple sort, shuttle sort or happy hour sort, is a stable sorting algorithm that varies from bubble sort in that instead of repeatedly passing through the list from top to bottom, it passes alternately from top to bottom and then from bottom to top. It can achieve slightly better performance than a standard bubble sort. It is a comparison sort.

Note that 'shaker sort' can also refer to a variant of selection sort.

The complexity of cocktail sort in Big O notation is O(n²) for a worst case, but becomes closer to O(n) if the list is mostly ordered at the beginning.

Implementation

For implementations in real programming languages, see Cocktail sort at Wikisource.it:Shaker sort