Shaker sort

Shaker sort (shake sort, cocktail sort) je stabilní řadící algoritmus s asymptotickou složitostí $O(n^{2})$ . 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;

Princip

Vizualizace

Kód

Doporučujeme