10-Trideni_ucinejsi_metody
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
BPC-ALD
10. přednáška
Účinnější metody vnitřního třídění - Shellovo třídění (Shell Sort),
Quick Sort
rev. 2019.4
Ing. T. Macho, Ph.D. (macho@feec.vutbr.cz)
Shellovo třídění
Shellovo třídění
• Třídění vkládáním (Donald Shell, 1952).
• Vychází z třídění přímým vkládáním.
• Vstupní posloupnost 𝑎1, 𝑎2, … , 𝑎𝑛 s 𝑛 prvky rozdělíme na ℎ kratších
posloupností (ℎ > 1):
1. posloupnost: 𝑎1, 𝑎ℎ+1, 𝑎2ℎ+1, …
2. posloupnost: 𝑎2, 𝑎ℎ+2, 𝑎2ℎ+2, …
...
ℎ-tá. posloupnost: 𝑎ℎ, 𝑎ℎ+2, 𝑎2ℎ+2, …
• Každá posloupnost má 𝑛 ℎ
prvků.
Shellovo třídění
• Průměrný počet srovnání i přesunů byl u metody přímého vkládání
přibližně
𝑛2
4 (zanedbáme členy nižšího řádu).
• Budeme-li uvažovat posloupnosti o
𝑛
ℎ prvcích, bude počet operací pro
každou z ℎ posloupností přibližně:
𝑛
ℎ
2
4
=
𝑛2
4ℎ2.
• To je ℎ2 krát méně, než když metodu přímého třídění aplikujeme na
celou posloupnost.
Shellovo třídění
• Tříděním jednotlivých samostatných posloupností nedosáhneme
setřídění celé posloupnosti.
• Prvky se však dostanou do určité blízkosti ke své cílové pozici.
• Čím bude ℎ menší, tím blíže budou prvky u své cílové pozice.
• Čím bude ℎ větší, tím bude potřeba méně operací.
• Tento rozpor řešíme tak, že během třídění posloupnost dělíme na
podposloupnosti vícekrát, přičemž počet podposloupností snižujeme,
až se dostaneme k jedné posloupnosti (ℎ = 1).
• Na závěr tedy proběhne běžné třídění přímým vkládáním (Insert Sort).
Shellovo třídění
• Bylo zjištěno, že optimální je volit počet podposloupností v
jednotlivých krocích podle předpisu:
ℎ1 = 1, ℎ𝑖 = 2ℎ𝑖−1 + 1 𝑝𝑟𝑜 𝑖 > 1, tedy … , 127, 63, 31, 15, 7, 3, 1.