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;
 







Doporučujeme