VB - 44. lekce
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

VB - 44. lekceVB - 44. lekce

 

VB - 44. lekce

Google       Google       29. 6. 2006       13 930×

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

Reklama
Reklama

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.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Jiří ChytilAutor programuje ve VB, zajímá se o elektrotechniku, studuje na SOŠ Elektrotechnické - obor číslicová technika.
Web    

Nové články

Obrázek ke článku NEWTON Media prohledá 200  milionů mediálních zpráv během sekund díky Cisco UCS

NEWTON Media prohledá 200 milionů mediálních zpráv během sekund díky Cisco UCS

Česká společnost NEWTON Media provozuje největší archiv mediálních zpráv ve střední a východní Evropě. Mezi její zákazníky patří například ministerstva, evropské instituce nebo komerční firmy z nejrůznějších oborů. NEWTON Media rozesílá svým zákazníkům každý den monitoring médií podle nastavených klíčových slov a nabízí online službu, kde lze vyhledat mediální výstupy v plném znění od roku 1996.

Reklama
Reklama
Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý