Shaker sort
Vzhľad
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
[upraviť | upraviť zdroj]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
[upraviť | upraviť zdroj]Toto je kód v niekoľkých programovacích jazykoch:
Java
[upraviť | upraviť zdroj]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++
[upraviť | upraviť zdroj]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#
[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 (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
[upraviť | 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 (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
[upraviť | 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