Umíte pascalsky - 19.lekce ... |
Umíte pascalsky? 19.lekce |
Vytisknout |
||||||||||||||||||||||||||||||||||||||||||||||||||||||
Třídění (řazení) pole Vzestupné (nebo sestupné) uspořádání konečného počtu hodnot nazýváme třídění. Ukážeme si některé metody třídění na třídění pole celých čísel. V této lekci to bude : A. Třídění pomocí minima - SelectSort B. Třídění bubláním - BubbleSort Třídění pomocí minima - SelectSort Příklad: Uspořádejte čísla 8 3 1 2 5 pomocí výběru minima Značka odděluje neuspořádaný úsek (vpravo) od uspořádaného úseku pole. Na začátku třídění je tedy u prvního prvku pole. Projdeme celé pole, najdeme minimum (1) a vyměníme ho s prvním prvkem (8). Tím je určen 1.prvek seřazeného pole , proto posuneme značku k druhému prvku pole a pokračujeme. Projdeme neseřazenou část pole (od značky do konce pole) a opět najdeme minimum (2) a vyměníme ho s s prvkem u značky (3). Dostaneme 2.prvek seřazeného pole. Značku posuneme k třetímu prvku a pokračujeme stejným způsobem...Naposled tento postup opakujeme je-li značka u předposledního prvku - pak porovnáme předposlední a poslední prvek, menší z nich (minimum) dáme ke značce a větší na konec a celé pole bude uspořádané. Myšlenka (hrubý algoritmus): Pro značku od prvního do předposledního prvku pole opakujeme tuto činnost: -najdeme minimum z neuspořádaného úseku -vyměníme minimum s 1.prvkem neuspořádaného úseku Tedy: for znacka:=1 to pocet-1 do <najdi minimum> <vyměň s 1.prvkem neusp.úseku> Nalezení minima lze upřesnit takto: poradi:=znacka; (nasazení minima na prvek u značky) for ktere:=znacka+1 to pocet do if cisla[ktere]<cisla{poradi] then poradi:=ktere; No a výměna minima s 1.prvkem je už triviální. Výslednou proceduru Trideni_minimum najdete o kousek dál. Třídění bubláním - BubbleSort Příklad: Uspořádejte čísla 4 8 1 4 5 2 3 postupnými výměnami. Značka odděluje neuspořádaný úsek (vlevo) od uspořádaného úseku pole. Na začátku třídění je tedy u posledního prvku pole. Procházíme celé pole od začátku do konce a je-li předcházející prvek větší než následující , vyměníme je. Tím se po prvním průchodu polem dostane (probublá) největší prvek na konec a je posledním prvkem uspořádaného úseku. Značku posuneme o jedno místo dopředu a procházíme podruhé neuspořádaný úsek pole (od prvního prvku do značky) a je-li předcházející prvek větší než následující , vyměníme je. Tím se uspořádaný úsek zvětší o druhý prvrk (druhý největší). Takto pokračujeme dále ... Naposled tento postup opakujeme, je-li značka u druhého prvku. Porovnáme první dva prvky a je-li třeba, vyměníme. Tím bude celé pole seřazené. Myšlenka (hrubý algoritmus): Pro značku od posledního zpět do druhého prvku pole opakujeme tuto činnost: -projít zkoumaný úsek od počátku až do značky a zaměnit ty sousední prvky, které nejsou podle velikosti Tedy: for znacka:=pocet downto 2 do <projdi neusp.úsek, je-li třeba vyměň> Procházení s eventuální výměnou lze upřesnit takto: for ktere:=1 to znacka-1 do if cisla[ktere]>cisla[ktere+1] then <vyměň prvky> No a výměna sousedních prvků je už zase triviální. Výslednou proceduru Trideni_bublani najdete o kousek dál. Příklad: Sestavte program Razeni, umožňující podle volby uživatele: 1) Zadat zvolený počet celých čísel 2) Seřadit pole pomocí minima 3) Seřadit pole pomocí bublání 0) Ukončit činnost Všechny úkoly řešte užitím procedur s parametry. Program Razeni může vypadat takto:
Domácí úkol: Doplňte program Razeni o volby Trideni_maximum a Lepsi_bublani. Trideni_maximum seřadí pole opakovaným vybíráním maxima (obdoba Trideni_minimum). Lepsi_bublani ukončí proces procházení a výměn sousedních prvků dřív než dojde značka k druhému prvku. Lze totiž cyklus ukončit pokud již nedojde při průchodu zkoumaným úsekem ani k jedné výměně. Při řazení čísel 4 8 1 5 2 3 4 lze ukončit po čtyřech krocích (a ne po šesti, až dorazí značka k druhému prvku) On-line účast na řešení úkolu Pomocí volby Řešit můžete (po přihlášení) odeslat vaše řešení domácího úkolu (každý úkol smíte řešit jen jednou). Volbou Hodnocení si přečtete hodnocení a komentář od vyučujícího. Dotaz nebo připomínku můžete opakovaně zasílat pomocí tlačítka Dotazy, Komunikace (na levém okraji) zobrazuje příklad možné komunikace s vyučujícím. |