Jak Začít?

Máš v počítači zápisky z přednášek
nebo jiné materiály ze školy?

Nahraj je na studentino.cz a získej
4 Kč za každý materiál
a 50 Kč za registraci!




10-Trideni_ucinejsi_metody

PDF
Stáhnout kompletní materiál zdarma (587.04 kB)

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. 

Témata, do kterých materiál patří