VB - 44. lekce

44.1 Třídění přetřásáním (ShakeSort)
44.2 Rychlé třídění (QuickSort)
44.3 Třídění haldou (HeapSort)
44.4 Domácí úkol
44.5 V další lekci

44.1 Třídění přetřásáním (ShakeSort)

ShakeSort je prakticky stejný jako BubbleSort, ovšem je dvousměrný, to znamená, že v jednom průběhu se třídí jednou ze začátku pole a potom od jeho konce. Doba potřebná pro seřazení se zkrátí více jak o polovinu.

start:
    Change = False
    For i = 0 To lngVelikostPole - 1
        If pole(i) > pole(i + 1) Then
            temp = pole(i)
            pole(i) = pole(i + 1)
            pole(i + 1) = temp
            Change = True
        End If
    Next i
        
    If Change Then
        Change = False
        For i = lngVelikostPole To 1 Step -1
            If pole(i) < pole(i - 1) Then
                temp = pole(i)
                pole(i) = pole(i - 1)
                pole(i - 1) = temp
                Change = True
            End If
        Next i
    End If
If Change Then GoTo start

44.2 Rychlé třídění (QuickSort)

QuickSort je jeden z nejrychlejších algoritmů na třídění, má ovšem jednu nevýhodu, při zvolení špatného pivotu se jeho výkon extrémně sníží. Funkce je rekurzivní, volá sama sebe. O rekurzi se budeme bavit hned, jak bude v lekcích volno. Teď jí tedy proběhnu jen zběžně. Jde o to, že algoritmus si vybere jeden prvek – pivot. Podle něj rozdělí pole na dvě části, v jedné části se budou nacházet ty prvky, které mají hodnotu menší, než je pivot, a ve druhé části budou prvky s hodnotou větší nebo stejnou. No a totéž se opakuje pro ta dvě pole, ta se také rozdělí – každé na dvě části podle pivotu. A každé z nich se zase rozdělí na další menší kousky až je celé pole setřízené. Třídění je zakončeno poté, co již nelze pole dělit, tedy velikost jednotlivých vzniklých polí je jeden prvek. Jako pivot se volí nejčastěji první prvek pole, které vstupuje do funkce QuickSort. Projedeme si to tedy ještě jednou: Mějme pole například o 10 prvcích. Pole vložíme do funkce QuickSort a vzniknou nám rozdělením dvě další pole, ta se rozdělí podle pivotu (nejvhodnější by pro nás bylo, aby se pole rozdělilo na dvě rovnoměrné části, to ale nemusí být pravidlem, a tudíž zvolíme-li si pole např. 1 000 prvků a ono se nám rozdělí na pole 7 a 992 + pivot (ten již budeme připočítávat automaticky) a pak na 3 a 4 a druhé se rozdělí 973 a 19, pak rychlost klesá. Pokud se ale pole rozdělí na 529 a 470 a pak na 233 a 296 a druhé na 235 a 235, bude situace jiná a třídění bude rychlejší. No ale je načase ukončit tento dlouhý text v závorce.) třeba na dvě pole 4 a 6 prvků. Každé z těchto polí projde dalším rozdělením na další dvě, ale z polí je vyjmut pivot, takže např. na 1 a 2 prvky v případě prvního pole a na 1 a 4 prvky v případě druhého. Tak to pokračuje dál a dál až všechna pole obsahují jen jediný prvek.

Public Sub QSort(pole As Variant, indexD As Long, indexH As Long)
   Dim pivot   As Variant
   Dim tmpSwap As Variant
   Dim indexD0  As Long
   Dim indexH0   As Long
    
   indexD0 = indexD 'přesun dat to pomocných porměnných
   indexH0 = indexH
   
   pivot = pole((indexD + indexH) \ 2) 'volba pivotu
   
   While (indexD0 <= indexH0)
      While (pole(indexD0) < pivot And indexD0 < indexH) 'roztřídění tabulek vzhledem k pivotu
         indexD0 = indexD0 + 1
      Wend
      
      While (pivot < pole(indexH0) And indexH0 > indexD)
         indexH0 = indexH0 - 1
      Wend
      
      If (indexD0 <= indexH0) Then
         tmpSwap = pole(indexD0)
         pole(indexD0) = pole(indexH0)
         pole(indexH0) = tmpSwap
         indexD0 = indexD0 + 1
         indexH0 = indexH0 - 1
      End If
   Wend
   
   If (indexD < indexH0) Then QuickSortVariants pole, indexD, indexH0 'rekurzivní volání pro nově vzniklá pole
   If (indexD0 < indexH) Then QuickSortVariants pole, indexD0, indexH
End Sub

44.3 Třídění haldou (HeapSort)

No a jako poslední třídící algoritmus v této lekci bude HeapSort. Je to velmi rychlý algoritmus, mezi jeho výhody patří také to, že neobsahuje žádné rekurze. To pro nás zaznamená nižší nároky na paměť. Jeho další výhodou, oproti mírně rychlejšímu QuickSortu, je stabilita výkonu.

No než se začneme zabývat tříděním jako takovým, myslím, že by nebylo od věci vysvětlit, co je to ona halda nebo též hromada – anglicky heap. Je to binární strom, ve kterém platí určitá pravidla. Je jich několik a jejch tvar je jakoby pyramida, která může být z jedné strany nekompletní, a to pouze v poslední řadě prvků. Jeden z prvků tedy tvoří vrchol haldy, ten má dva, řekněme, syny a každý z nich má další dva potomky a ty myjí další dva potomky. Pokud je ale počet prvků menší a nevyjde tedy počet prků na to, aby každý mateřský prvek měl dva potomky (tedy krom spodní řady, jinak bychom se dostali do nekonečna), tak poslední z prvků v předposlední řadě nebude mít potomky. Důležité ja pak také to, že každý z prvků je menší nebo roven svým následovníkům. Pokud tedy bude mateřský prvek 12 a potomci budou 6 a 9, tak je to v pořádku.

Třídění pomocí haldy se skládá ze dvou částí; první je přidání nového prvku. Ten se přidá na první volné místo úplně vespod haldy. A poté se porovnává se svými rodiči a v případě, že hodnoty nesplňují pravidla, prvky se přehodí a to se děje tak dlouho, dokud tato pravidla nejsou splněna nebo dokud prvek nedosáhne vrcholu haldy, ten totiž nemá žádné rodičovské prvky. Tím bychom měli první část programu hotovou, tedy stavbu haldy; teď nás čeká druhá část, tou je rozebírání haldy. To se provádí, dá se říci, probubláváním. Odebereme kořenový prvek, tedy ten z nejvyššího místa haldy, a postupně necháváme ostatní prvky probublávat výš. Takto se pokračuje do té doby, než se strom vyprázdní.

44.4 Domácí úkol

Za domácí úkol rozšíříte program který jste vytvořili minule o tyto tři nové algoritmy.

44.5 V další lekci

Třídění pomocí: ShellSort, RadixSort a MergeSort.