Shaker sort

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[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;
   }
}

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[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)
   }
}

C#

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;
   }
}

Pascal

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;

VisualBasic.NET

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