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

VB – 45. lekceVB – 45. lekce

 

VB – 45. lekce

Google       Google       14. 7. 2006       13 977×

45.1 ShellSort
45.2 Přihrádkové třídění (RadixSort)
45.3 Třídění slučováním (MergeSort)
45.4 Domácí úkol
45.5 V další lekci

Reklama
Reklama

45.1 ShellSort

V tomto díle se prokoušeme posledními třemi typy třídění, které mám v úmyslu probrat. Jsou to ShellSort, RadixSort a MergeSort. Tyto metody si probereme spíše teoreticky. Začneme tedy ShellSortem. Je to metoda poněkud zvláštní a přišel na ni jistý pan Donald Shell. Ze svých pozorování a experimentů zjistil, že prvek se v poli posune průměrně o jednu třetinu vzdálenosti. Tento algoritmus pracuje podobným způsobem jako BubbleSort, ale hlavní rozdíl je v tom, že se neporovnávají dva sousední prvky, ale prvky, které jsou od sebe vzdáleny na určitou délku. Takže se porovnává například prvek 0 s 4 a 9, prvek 1 s 5 a 10 prvek, 2 s 6 a 11 a prvek 3 s 7 případně i s 12, pokud je v poli tolik prvků. To je první průchod, a z něj vyplývá, že vzdálenost mezi prvky je 5. Další průchod se vzdálenost mezi prvky zmenší o 1. Budeme tedy porovnávat prvek 0 s prvky 3 a 7 a 11, prvek 1 s prvky 4 a 8 atd. Další průchod se vzdálenost mezi prvky opět sníží o 1, bude tedy 3. Až se pole vytřídí i cyklem, kde je vzdálenost mezi prvky 1, je hotovo. Pole musí být při prvním třídění rozděleno tak, aby vzdálenost mezi tříděnými prvky byla větší nebo rovna 1/3. Třídění prvků, které porovnáváme, probíhá tak, že když máme zvolené např. prvky 0, 3, 7, 11, tak je seřadíme od nejmenšího po největší. Napsání kódu není složité, nechám to tedy na vás.

45.2 Přihrádkové třídění (RadixSort)

Přihrádkové třízení je zvláštní v tom, že se třídí podle cifer. Pokud vezmeme například čísla trojciferná, rozdělíme je do přihrádek 0, 1, 2 … 9, a to podle jejich poslední cifry. Poté vezmeme přihrádku 0, ze které budeme vybírat čísla a přiřazovat je podle druhé cifry do přihrádek 0, 1, 2 … 9. Nebudou to ovšem ty samé přihrádky, ale přihrádky pro druhý řád. Tak budeme pokračovat i s čísly z přihrádek 1 – 9 prvního řádu. Teď postupně budeme brát čísla z přihrádek 2. řádu. Začneme opět u 0 a umístíme je do přihrádky 0 – 9 třetího řádu, a to právě podle třetí cifry. Čísla z přihrádek se berou v takovém pořadí, v jakém jsme je vložili. Použijeme tedy frontu (data, která jdou první dovnitř, jdou první ven, narozdíl od zásobníku, kde data, která jsme uložili naposledy, čteme jako první). Jako příklad uvedu cestu čísla 473. V prním rozmisťování se číslo dostane do přihrádky číslo 3. Z té je při následujícím přemístění přesunuto do přihrádky druhého řádu s číslem 7 a na závěr je přesunuto do přihrádky třetího řádu.

45.3 Třídění slučováním (MergeSort)

Poslední probíranou metodou třídění bude MergeSort. Ten pracuje s tím, že slučuje dvě již vytříděná pole v jedno setříděné pole. Metoda je tedy vhodná, pokud máme například dva záznamy a potřebujeme je setřídit v jeden setříděný. Nevýhoda MergeSortu je především v tom, že potřebujeme jedno pomocné pole. Je možné napsat to i bez něj, ale algoritmus se stává mnohem složitější.

45.4 Domácí úkol

Vaším úkolem pro tuto lekci je dokončit program na porovnání výkonnosti algoritmů.

45.5 V další lekci

Příště se konečně vrhneme na objektově orientované programování. Budeme tvořit objekty třídy, a tak dál, a tak dál. Toto téma, tedy OOP, nám zabere několik lekcí.

×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

Reklama
Reklama
Obrázek ke článku Blockchain & Bitcoin konference

Blockchain & Bitcoin konference

V pátek 19. 5. 2017 se v pražském konferenčním centru Andel’s konala Blockchain & Bitcoin konference. Řada odborníků a podnikatelů v oboru blockchainu a kryptoměn představila možnosti budoucího směřování tohoto oboru. Speakeři většinou rusky mluvící provenience prezentovali řešení svých firem založená na technologii blockchainu.

Obrázek ke článku Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Bezpečnostní tým Cisco Talos odhalil celkem 4 kampaně dosud neobjeveného malwaru, který dostal jméno KONNI. Ten se dokázal úspěšně maskovat od roku 2014. Zpočátku se malware zaměřoval pouze na krádeže citlivých dat. Za 3 roky se ale několikrát vyvinul, přičemž jeho současná verze umožňuje útočníkovi z infikovaného počítače nejenom krást data, ale i mapovat stisky na klávesnici, pořizovat screenshoty obrazovky či v zařízení spustit libovolný kód. Pro odvedení pozornosti oběti zasílali útočníci v příloze také obrázek, zprávu a výhružkách severokorejského režimu či kontakty na členy mezinárodních organizací.

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 © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý