Třídíme data - Builder.cz - Informacni server o programovani

Navigace:  » Úvodní stránka  » Rubriky  » Delphi  

19. února 2002, 00.00 | Téměř v každém programu potřebujeme nějaká data setřídit
např. podle abecedy nebo podle číselné hodnoty. K tomu nám slouží třídící algoritmy.
V tomto článku si ukážeme jak na to.

Téměř v každém programu potřebujeme nějaká data setřídit např. podle abecedy nebo podle číselné hodnoty. K tomu nám slouží třídící algoritmy. V tomto článku bych vám chtěl ukázat, jak na to.

Na třídícím algoritmu může záležet rychlost celého výsledného programu. A právě proto musíme zvolit takový, který je dostatečně rychlý a stabilní. Samozřejmě je rozdíl řadit položek deset a stotisíc. V prvním případě si vystačíme s jakýmkoli algoritmem, protože výsledná doba bude zanedbatelná. Ale v druhém případě, pokud zvolíme pomalý třídící algoritmus, může doba přesáhnout i pár desítek minut.

Zde uvedu základní přehled nejznámějších třídících algoritmů:

• Bubble Sort
• Select Sort
• Insert Sort
• Binary Insert Sort
• Shell Sort
• Shaker Sort
• Heap Sort
• Radix Sort
• Merge Sort
• Quick Sort

Pro náš účel budeme řadit pole, protože je z hlediska řazení a jiných operací s daty zdaleka nejnázornější. Prvky tohoto pole budou čísla, které budeme řadit vzestupně. Tj. od nejmenší hodnoty po největší. Podotýkám, že řazení řetězců by fungovalo na zcela stejném principu.

Bubble Sort

Ze všech zde uvedeným metod je tato nejjednodušší, ale také nejpomalejší. Její metoda spočívá v postupném porovnávání sousedních prvků pole. V případě, že druhý z porovnávaných prvků je menší než první, provede se jejich záměna. Tímto způsobem se pokračuje do té doby, dokud nenarazíme na menší prvek nebo na začátek pole.

Procedure BubbleSort(Var A:Array Of Integer); Var I,J,T : Integer; Begin For I:=High(A) Downto Low(A) Do For J:=Low(A) To High(A)-1 Do If (A[J] > A[J+1] Then Begin T:=A[J]; A[J]:=A[J+1]; A[J+1]:=T; End; End;

Existuje také vylepšená metoda, která ukončí činnost v okamžiku, kdy je již celá posloupnost uspořádaná. Tudíž algoritmus nemusí probíhat prvky pole zbytečně:

Procedure ExtBubbleSort(Var A:Array Of Integer); Var I,J,T : Integer; Konec : Boolean; Begin For I:=High(A) Downto Low(A) Do Begin Konec:=True; For J:=Low(A) To High(A)-1 Do If A[J] > A[J+1] Then Begin T:= A[J]; A[J]:=A[J+1]; A[J+1]:= T; Konec:=False; End; If Konec Then Break; End; End;

Na začátku jsem uvedl, že je tato metoda nejpomalejší. Ano, v případě, že pole je neseřazené. Ale pokud necháme algoritmem projít již seřazenou posloupnost, je tato metoda jedna z nejrychlejších ! Tohoto můžeme využít, pokud chceme např. zjistit, zda je pole již seřazené.

Select Sort

Tato metoda pracuje tak, že vyhledá nejmenší prvek v nesetřízené části a zařadí ho na konec již setřízené části. Tzn. že musíme projít celé pole, najít nejmenší prvek a zařadit ho na první místo. Poté znova musí projít pole od druhého prvku pole (protože první prvek má již svou konečnou pozici) a vyhledá opět nejmenší prvek. Ten zařadí na druhou pozici. Tato činnost se opakuje tak dlouho, dokud neprojde celou posloupnost a nesetřídí ji.

Procedure SelectSort(Var A:Array Of Integer); Var I, J, T: Integer; Begin For I:=Low(A) To High(A)-1 Do For J:=High(A) Downto I+1 Do If A[I] > A[J] Then Begin T:=A[I]; A[I]:=A[J]; A[J]:=T; End; End;

Jak vidíme, tak metoda je také značně jednoduchá, ale opět časově nevýhodná.

Insert Sort

Algoritmus Insert Sort pracuje tak, že vyhledává index, kam se má prvek zařadit a zároveň zbývající prvky posune o jednu pozici směrem ke konci pole. Nejdříve ovšem musíme na začátek pole přidat jeden prvek k třízené posloupnosti, který budeme používat jako pomocný.

Procedure InsertSort(Var A:Array Of Integer); Var I,J:Integer; X:Integer; Begin For I:=2 to High(A) Do Begin X:=A[I]; A[0]:=X; J:=I-1; While X < A[J] Do Begin A[J+1]:=A[J]; J:=J-1; End; A[J+1]:=X; End; End;

Pozor! Nesmíme zapomenout, že algoritmus nám vrátí i první prvek pole, který je pomocný. I zde existuje drobná úprava, díky které metodu výrazně urychlíme. Tu si ovšem ukážeme až příště ...

Pro srovnání rychlosti metod jsem vytvořil program, který seřazuje pole a zobrazí výsledný čas v milisekundách. Po stisku tlačítka Generate se vygenerují náhodné hodnoty v rozsahu typu Integer. Samozřejmě, že by se toto mohlo vykonat při stisku tlačítka Start. Ale byl to úmysl. Takto je totiž možné si ukázat rychlost jednotlivých metod na již setřízeném poli.

V dalším díle si popíšeme některé z výše jmenovaných metod.

Zdrojové kódy dnes ukázaných metod naleznete zde - velikost 173 kB.