#REDIRECT [[ it:Shaker sort]] ▼
<noinclude>{{WIP|Fabrymondo}}</noinclude>
'''Cocktail sort''', also known as '''bidirectional bubble sort''', '''cocktail shaker sort''', '''shaker sort''' (which can also refer to a variant of [[selection sort]]), '''ripple sort''', '''shuttle sort''' or '''happy hour sort''', is a variation of [[bubble sort]] that is both a [[stable sort|stable]] [[sorting algorithm]] and a [[comparison sort]]. The algorithm differs from [[bubble sort]] in that sorts in both directions each pass through the list.
== Pseudocode ==
Cocktail sort in [[pseudocode]] inspired by the [[C (programming language)|C programming language]] that sorts a list in increasing order:
'''function''' cocktail_sort(list, list_length) <span style="color:green">// the first element of list has index 0</span>
{
bottom = 0;
top = list_length - 1;
swapped = true;
'''while'''(swapped == true) <span style="color:green">// if no elements have been swapped, then the list is sorted</span>
{
swapped = false;
'''for'''(i = bottom; i < top; i = i + 1)
{
'''if'''(list[i] > list[i + 1]) <span style="color:green">// test whether the two elements are in the correct order</span>
{
swap(list[i], list[i + 1]); <span style="color:green">// let the two elements change places</span>
swapped = true;
}
}
<span style="color:green">// decreases `top` because the element with the largest value in the unsorted
// part of the list is now on the position top </span>
top = top - 1;
'''for'''(i = top; i > bottom; i = i - 1)
{
'''if'''(list[i] < list[i - 1])
{
swap(list[i], list[i - 1]);
swapped = true;
}
}
<span style="color:green">// increases `bottom` because the element with the smallest value in the unsorted
// part of the list is now on the position bottom </span>
bottom = bottom + 1;
}
}
== Optimization ==
One possible optimization would be to add an [[if statement|if-statement]] that checks whether there has been a swap after the first pass each iteration. If there hasn't been a swap the list is sorted and the algorithm can stop.
== Differences from bubble sort ==
Cocktail sort is a slight variation of [[bubble sort]]. It differs in that instead of repeatedly passing through the list from bottom to top, it passes alternately from bottom to top and then from top to bottom. It can achieve slightly better performance than a standard bubble sort. The reason for this is that [[bubble sort]] only passes through the list in one direction and therefore can only move items backward one step each iteration.
An example of a list that proves this point is the list (2,3,4,5,1), which would only need to go through one pass of cocktail sort to become sorted, but if using an ascending [[bubble sort]] would take four passes.
==Complexity==
The complexity of cocktail sort in [[big O notation]] is <math>O(n^2)</math> for both the worst case and the average case, but it becomes closer to <math>O(n)</math> if the list is mostly ordered at the beginning.
==External links==
*[http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html Java source code and an animated demo of cocktail sort (called bi-directional bubble sort) and several other algorithms]
*[http://www.sharpdeveloper.net/content/archive/2007/08/14/dot-net-data-structures-and-algorithms.aspx .NET Implementation of cocktail sort and several other algorithms]
{{sorting}}
[[Category:Sorting algorithms]]
[[Category:Comparison sorts]]
[[Category:Stable sorts]]
[[Category:Articles with example pseudocode]]
[[es:Cocktail sort]]
[[ja:シェーカーソート]]
[[pl:Sortowanie koktajlowe]]
[[pt:Cocktail sort]]
[[ru:Сортировка перемешиванием]]
| 