Shaker sort (cocktail sort, shake sort) is a stable sorting algorithm with quadratic asymptotic complexity . Shakersort is a bidirectional version of bubble sort.
Description
Shaker sort unlike bubble sort orders the array in both directions. Hence every iteration of the algorithm consists of two phases. In the first one the lightest bubble ascends to the end of the array, in the second phase the heaviest bubble descends to the beginning of the array.
This way an imperfection of bubble sort – the problem of rabbits and turtles – is mitigated. The problem of rabbits and turtles is a situation in bubble sort, when a heavy bubble is placed at the end of the array. While the light bubbles (rabbits) are ascending rapidly, the heavy bubble (turtle) descends only one position per each iteration.
Visualization
Code
/**
* Shaker sort (bidirectional bubble sort)
* Orders in descending order
* @param array array to be sorted
*/
public static void shakerSort(int[] array) {
for (int i = 0; i < array.length/2; i++) {
boolean swapped = false;
for (int j = i; j < array.length - i - 1; j++) {
if (array[j] < array[j+1]) {
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
swapped = true;
}
}
for (int j = array.length - 2 - i; j > i; j--) {
if (array[j] > array[j-1]) {
int tmp = array[j];
array[j] = array[j-1];
array[j-1] = tmp;
swapped = true;
}
}
if(!swapped) break;
}
}
/**
* Shaker sort (bidirectional bubble sort)
* Orders in descending order
* @param array array to be sorted
* @param size length of the array
*/
void shakerSort(int array[], int size) {
for (int i = 0; i < size/2; i++) {
bool swapped = false;
for (int j = i; j < size - i - 1; j++) { //one way
if (array[j] < array[j+1]) {
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
swapped = true;
}
}
for (int j = size - 2 - i; j > i; j--) { //and back
if (array[j] > array[j-1]) {
int tmp = array[j];
array[j] = array[j-1];
array[j-1] = tmp;
swapped = true;
}
}
if(!swapped) break; //block (break if no element was swapped - the array is sorted)
}
}
/**
* Shaker sort (bidirectional bubble sort)
* Orders in descending order
* @param array array to be sorted
*/
public static void ShakerSort(int[] array)
{
for (int i = 0; i < array.Length / 2; i++)
{
bool swapped = false;
for (int j = i; j < array.Length - i - 1; j++)
{
if (array[j] < array[j + 1])
{
int tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
swapped = true;
}
}
for (int j = array.Length - 2 - i; j > i; j--)
{
if (array[j] > array[j - 1])
{
int tmp = array[j];
array[j] = array[j - 1];
array[j - 1] = tmp;
swapped = true;
}
}
if (!swapped) break;
}
}
procedure ShakeSort(var X : ArrayType; N : integer);
var
L,
R,
K,
J : integer;
begin
L := 2;
R := N;
K := N;
repeat
for J := R downto L do
if (X[J] < X[J - 1]) then
begin
Swap(X[J], X[J - 1]);
K := J
end;
L := K + 1;
for J := L to R do
if (X[J] < X[J - 1]) then
begin
Swap(X[J], X[J - 1]);
K := J
end;
R := K - 1;
until L >= R
end;
procedure Swap(var X, Y : integer);
var
Temp : integer;
begin
Temp := X;
X := Y;
Y := Temp
end;