Řadící algoritmy II.
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Merge sort
•metoda Rozděl a panuj
•Nejhorší i průměrná časová složitost O(NlogN)
•Potřebuje navíc pole o velikosti N
•Stabilní, paralelizovatelný
•Postup:
1.Rozdělí neseřazenou množinu dat na dvě podmnožiny o přibližně stejné velikosti.
2.Seřadí obě podmnožiny.
3.Spojí seřazené podmnožiny do jedné seřazené množiny.
•

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Merge sort
•Algoritmus
•mergesort(m)
• var list left, right
• if length(m) ≤ 1
• return m
• else
• middle = length(m) / 2
• for each x in m up to middle
• add x to left
• for each x in m after middle
• add x to right
• left = mergesort(left)
• right = mergesort(right)
• result = merge(left, right)
• return result

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Quicksort
•Jeden z nejrychlejších běžných algoritmů řazení založený na porovnávání prvků
•Časová složitost O(NlogN) – O(N2)
•Metoda Rozděl a panuj
•Rekurzivní algoritmus
•Postup:
•výběr pivot – rozdělení posloupnosti na dvě části – větší a menší než pivot
•Seřaď obě části stejným způsobem
•
•
•

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Quicksort
•Volba pivotu – ideální medián
•První prvek (jakákoli fixní pozice) – nevýhodné na částečně seřazených množinách
•Náhodný prvek – ve skutečnosti pseudonáhodný
•Medián tří (pěti…) – či jiného počtu prvků z fixních nebo náhodných pozic
•Při správné implementaci nepotřebuje paměť navíc
•Nestabilní algoritmus
•Způsob volby pivotu má vliv na řazení
•v průměru jde o nejrychlejší známý univerzální algoritmus pro řazení polí v operační paměti
počítače

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Selection sort
•Jednoduchý algoritmus
•Časová složitost O(N2)
•Vhodný pro malé množství dat
•Univerzální, lokální, nestabilní
•Postup:
1.Rozdělíme si posloupnost na seřazenou a neseřazenou část
2.Najdeme prvek s nejmenší hodnotou v neseřazené části posloupnosti
3.Zaměníme ho s prvkem na první pozici neseřazené části
4.První prvek neseřazené části zahrneme do seřazené části a zároveň neseřazenou část zmenšíme o 1
prvek zleva
5.Zbytek posloupnosti se uspořádá opakováním kroků 2 až 5 pro zbylou neseřazenou část

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Porovnání řadících algoritmů
Název
Časová složitost
Dodatečná paměť
Stabilní
Přirozená
Metoda
Anglicky
Česky
Minimum
Průměrně
Maximum
Bubble sort
Bublinkové řazení
O(n)
O(n²)
O(n²)
O(1)
ano
ano
záměna
Heapsort
Řazení haldou
O(n log n)
O(n log n)
O(n log n)
O(1)
ne
ne
halda, záměna
Insertion sort
Řazení vkládáním
O(n)
O(n²)
O(n²)
O(1)
ano
ano
vkládání
Merge sort
Řazení slučováním
O(n log n)
O(n log n)
O(n log n)
O(log n)
ano
ano
slučování
Quicksort
Rychlé řazení
O(n log n)
O(n log n)
O(n²)
O(log n)
ne
ne
záměna
Selection sort
Řazení výběrem
O(n²)
O(n²)
O(n²)
O(1)
zprav. ne
ne
výběr
Zdroj: www.wikipedia.cz

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Bucket sort
•Rozděluje data do několika přihrádek
•Časová náročnost: O(n*k), kde k=n/m, vstupní data n, počet přihrádek m.
•Předpoklady:
•Vhodný pro rovnoměrně rozložené hodnoty vstupních dat.
•Algoritmus pro seřazení přihrádek musí být stabilní
•Postup:
•Vstupní data jsou rozdělena do předem definovaného počtu přihrádek.
•Na každou přihrádku volán stabilní řadicí algoritmus.
•Jednotlivé přihrádky postupně kopírovány do výstupního pole.
•Výhody: dobře paralelizovatelný, nemusí mít všechna data v paměti najednou
•
•
•

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Radix sort
•Řadí celá čísla procházením všech číslic
•LSD (Least Significant Digit) – řazení podle nejméně významných číslic (odzadu)
•MSD (Most Significant Digit) – nejvíce významné číslice (odpředu)
•Časová složitost: O( (z+n)*logzu), kde z je základ zvolené číselné soustavy, n počet čísel na
vstupu a u je maximální rozmezí čísel na vstupu
•Nehodí se pro neomezeně velké vstupy
•Příklad LSD radix: 170, 45, 75, 90, 802, 2, 24, 66 ⇒ 170, 90, 802, 2, 24, 45, 75, 66 ⇒ 802, 2, 24,
45, 66, 170, 75, 90 ⇒2, 24, 45, 66, 75, 90, 170, 802

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Counting sort
•Vhodný pro velké soubory s malým množstvím diskrétních hodnot
•Stabilní
•Časová náročnost: O(N+M)
•Paměťová náročnost: O(M)
•Předpoklady:
•Počet různých hodnot (M) významně menší než celkový počet prvků (N).
•Pomocné pole – zápis a čtení v konstantním čase (pole indexované hodnotou nebo hashem hodnoty)
•Algoritmus:
•zleva (či zprava) projde vstupní pole
•pro každý prvek zvýší v pom. poli četnost výskytu tohoto prvku
•ke každé položce přičte počet výskytů všech předchozích položek (získá přesnou pozici hranice)
•začne zprava procházet neseřazené pole
•pro každý prvek se podívá do pomocného pole na horní hranici pro umístění
•na tuto hranici ho umístí a zároveň ji sníží o jedna
•takto postupuje, dokud neprojde celé pole