A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Counting sort je triediaci algoritmus, ktorý v lineárnom čase utriedi prvky v konečnej množine. Všetky prvky sú celé čísla z intervalu <0; k-1> pre .[1]
Algoritmus
Pre každý prvok x vo vstupnej množine sa určí počet prvkov, ktoré sú rovné ako daný prvok x. Tento údaj sa uloží do pomocného poľa. Ku každej položke v pomocnom poli sa následne pripočíta počet výskytov predchádzajúcich položiek. Takýmto spôsobom sa získa presná pozícia hranice, ktorá sa využije na priame umiestnenie prvku x vo výstupnom zoradenom poli. Algoritmus začne sprava prechádzať neutriedené prvky vo vstupnom poli a pre každý prvok sa pozrie na jeho hornú hranicu, ktorú má uloženú v pomocnom poli. Na túto pozíciu ho uloží do výstupného poľa a následne toto číslo zníži o 1. Obdobným spôsobom prejde celé vstupné pole sprava doľava a výstup – utriedené prvky - sa budú nachádzať vo výstupnom poli.
Pseudokód
Pole A - vstupná množina
Pole B - výstup (utriedená množina)
Pole C - pomocné pole, v ktorom sa ukladá počet výskytov vstupných prvkov
procedure Counting_Sort;
begin
for i := 0 to k do
C := 0; //inicializácia poľa C na 0
for j := 1 to length(A) do
Cj := CAj + 1; // Ci teraz obsahuje počet výskytov prvku i v poli A
for i := 1 to k do
Ci := Ci + Ci – 1; // Ci teraz obsahuje počet prvkov menších alebo rovných ako i
for j := length(A) downto 1 do
begin
BCAj := Aj; // B je utriedená množina
CAj := CAj – 1;
end;
end;
Príkladupraviť | upraviť zdroj
Majme vstupnú množinu prvkov 3,1,5,2,1,5,1.
Do pomocného poľa si uložíme počet výskytov jednotlivých prvkov
1 – 3x 2 – 1x 3 – 1x 5 – 2x
Prepočítame ich na hranice prvkov:
1 – 3 2 – 4 (tri výskyty prvku 1 a jeden výskyt prvku 2) 3 – 5 5 – 7
Zaradenie prvého prvku (ideme sprava doľava)
, ,1, , , ,
Upravíme pomocné pole a hranice prvkov:
1 – 2x (hranica:2) 2 – 1x (hranica:4) 3 – 1x (hranica:5) 5 – 2x (hranica:7)
Zaradenie ostatných prvkov (analogicky)
, ,1, , , ,5 ,1,1, , , ,5 ,1,1,2, , ,5 ,1,1,2, ,5,5 1,1,1,2, ,5,5 1,1,1,2,3,5,5 1,1,1,2,3,5,5
Vlastnostiupraviť | upraviť zdroj
Časová zložitosť: Inicializácia poľa C – nastavenie prvkov na 0 a jeden ďalší prechod týmto poľom trvajú O(k), algoritmus prejde navyše dvakrát pole A, to trvá O(n). Takto je celkový beh v čase O(n + k).[2] Za predpokladu, že rozsah 1..k nie je väčší než n, teda možno uvažovať, že k = O(n) a teda je potom celkový čas behu countingsortu O(n). [3]
Pamäťová zložitosť: Counting sort využíva polia dĺžok k+1 a n. Celková pamäťová zložitosť preto je O(n + k).[2]. Za rovnakého predpokladu, ako je uvedený pri časovej zložitosti, je pamäťová zložitosť O(k).
Stabilita: Countingsort je stabilné triedenie. Znamená to, že prvky rovnakej hodnoty na vstupe budú v rovnakom poradí na výstupe. Je to z toho dôvodu, že nie je založený na porovnaní. Avšak keby sme pole začali triediť smerom zľava doprava, výsledná množina by nebola stabilná.
Referencieupraviť | upraviť zdroj
- ↑ EDMONDS, Jeff. How to Think about Algorithms. s.l. : Cambridge University Press, 2008. ISBN 978-0-521-84931-9. Kapitola 5.2 Counting Sort (a Stable Sort), s. 72–75. (po anglicky).
- ↑ a b CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L., ai. Introduction to Algorithms. MIT Press and McGraw-Hill, 2001. (2nd.) Kapitola 8.2 Counting Sort, s. 168–170. ISBN 0-262-03293-7. (po anglicky)
- ↑ ZEMIANEK, Juraj. Triediace algoritmy (Bakalárska práca). Bratislava: 2007.
Iné projektyupraviť | upraviť zdroj
- Commons ponúka multimediálne súbory na tému Counting sort
Externé odkazyupraviť | upraviť zdroj
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk