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

Kategória:Triediacie algoritmy