Shaker sort (shake sort, cocktail sort) je stabilní řadící algoritmus s asymptotickou složitostí . Shakersort je vylepšením
bubble sortu.
Princip
Shaker sort narozdíl od bubble sortu neřadí pole pouze jedním směrem, ale oběma. Každá iterace algoritmu se tedy skládá z dvou fází - při dopředné stoupá nejlehčí bublinka vzhůru, pří zpětné klesá nejtěžší bublinka ke dnu. Tímto postupem se předejde nedostatku bubble sortu tzv. problému želv a zajíců, který spočívá v tom, že vysoké hodnoty probublají na konec pole rychle, ale ty nízké postupují na začátek velmi pomalu.
Vizualizace
Kód
/**
* Shaker sort (obousmerny Bubblesort)
* radi od nejvyssiho
* @param array pole k serazeni
*/
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 (obousmerny Bubblesort)
* radi od nejvyssiho
* @param array pole k serazeni
* @param size velikost pole
*/
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++) { //tam
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--) { //a zpatky
if (array[j] > array[j-1]) {
int tmp = array[j];
array[j] = array[j-1];
array[j-1] = tmp;
swapped = true;
}
}
if(!swapped) break; //zarazka (pokud nebylo prohozeno, je serazeno)
}
}
/**
* 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;