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

VB – 45. lekceVB – 45. lekce

 

VB – 45. lekce

Google       Google       14. 7. 2006       13 687×

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

Obrázek ke článku RAD Studio a Windows Store

RAD Studio a Windows Store

RAD Studio je první vývojové prostředí se zabudovanou podporou balení aplikací typu Win32 a Win64 pro jejich umístění a šíření prostřednictvím Windows 10 Store.

Reklama
Reklama
Obrázek ke článku Testujte na 2 400+ Android a iOS zařízení

Testujte na 2 400+ Android a iOS zařízení

V dnešní době, kdy většina softwaru pro mobilní aplikace je tvořena a distribuována průběžně, mnohdy do celého světa je třeba zajistit také průběžnou automatizaci testování mobilního softwaru. V případě mobilních aplikací pro Android a iOS začíná být problém, jak testovat na obrovském množství kombinací HW variant, rozměrů, edic operačních systémů různých výrobců v různých částech světa na reálných zařízení. Simulátory a emulátory nejsou většinou to pravé. Pokud již testuji, jak si udělat vlastní beta distribuci opravdovým reálným testerům napříč platformami?

Obrázek ke článku Funkcie main vo Windows API

Funkcie main vo Windows API

V tretej časti seriálu o Windows API budeme hovoriť o funkčných prototypoch main. Funkčný prototyp je tvorený názvom funkcie a typom signatúry, pričom sa vynecháva telo funkcie. 

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ý