Tomuto článku alebo sekcii chýbajú odkazy na spoľahlivé zdroje, môže preto obsahovať informácie, ktoré je potrebné ešte overiť. Pomôžte Wikipédii a doplňte do článku citácie, odkazy na spoľahlivé zdroje.

Shaker sort je stabilný triediaci algoritmus s asymptotickou zložitosťou O(n^2). Shakersort je vylepšením bubble sortu.

Princíp

Shaker sort na rozdiel od bubble sortu neradí pole iba jedným smerom, ale oboma. Každá interakcia algoritmu sa teda skladá z dvoch častí - v prvej časti stúpa najmenší člen na začiatok a pri druhej časti klesá najväčší člen na koniec. Týmto postupom sa zamedzí nedostatku bubble sortu tzv. problému korytnačiek a zajacov, ktorý spočíva v tom, že vysoké hodnoty sa dostanú na koniec poľa rýchle zatiaľ čo tie nízke postupujú na začiatok veľmi pomaly.

Algoritmus

Toto je kód v niekoľkých programovacích jazykoch:

Java

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 < array) {
               int tmp = array;
               array = array;
               array = tmp;
               swapped = true;
           }
       }
       for (int j = array.length - 2 - i; j > i; j--) {
           if (array > array) {
               int tmp = array;
               array = array;
               array = tmp;
               swapped = true;
           }
       }
       if(!swapped) break;
   }
}

C++

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 < array) {
               int tmp = array;
               array = array;
               array = tmp;
               swapped = true;
           }
       }
       for (int j = size - 2 - i; j > i; j--) { //a zpatky
           if (array > array) {
               int tmp = arrayj;
               arrayj = arrayj-1;
               arrayj-1 = tmp;
               swapped = true;
           }
       }
       if(!swapped) break; //zarazka (pokud nebylo prohozeno, je serazeno)
   }
}

C#upraviť | upraviť zdroj

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 (arrayj < arrayj + 1)
           {
               int tmp = arrayj;
               arrayj = arrayj + 1;
               arrayj + 1 = tmp;
               swapped = true;
           }
       }
       for (int j = array.Length - 2 - i; j > i; j--)
       {
           if (arrayj > arrayj - 1)
           {
               int tmp = arrayj;
               arrayj = arrayj - 1;
               arrayj - 1 = tmp;
               swapped = true;
           }
       }
       if (!swapped) break;
   }
}

Pascalupraviť | upraviť zdroj

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 (XJ < XJ - 1) then
       begin
         Swap(XJ, XJ - 1);
         K := J
       end;
   L := K + 1;
   for J := L to R do
     if (XJ < XJ - 1) then
       begin
         Swap(XJ, XJ - 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;

VisualBasic.NETupraviť | upraviť zdroj

Public Sub ShakerSort(ByVal array() As Integer)
       For i As Integer = 0 To array.Length / 2
           Dim swapped As Boolean = False
           For j As Integer = i To array.Length - i - 2
               If (array(j) < array(j + 1)) Then
                   Dim tmp As Integer = array(j)
                   array(j) = array(j + 1)
                   array(j + 1) = tmp
                   swapped = True
               End If
           Next
           For j As Integer = array.Length - 2 - i To i + 1 Step -1
               If (array(j) > array(j - 1)) Then
                   Dim tmp As Integer = array(j)
                   array(j) = array(j - 1)
                   array(j - 1) = tmp
                   swapped = True
               End If
           Next
       Next
   End Sub