Shellovo řazení: Porovnání verzí

Smazaný obsah Přidaný obsah
m Shell sort je nazván podle Donalda Shella
Řádek 1:
{{Různé významy|stránka=Shell}}
[[Soubor:Shell sorting algorithm color bars.svg|thumb|Shell sort algoritmus barevné pruhy]]
'''Shellovo řazení''' ({{Vjazyce|en}} {{Cizojazyčně|en|'''shellShell sort'''}}, nebo též řazení se snižujícím se přírůstkem) je [[řadicí algoritmus]] podobný [[insert sort]]u, který objevil a v roce 1959 publikoval [[Donald Shell]].
 
Shell sort je [[Stabilní řazení|nestabilní]] řadicí metoda (tj. nezachovává původní pořadí dvou prvků se stejným klíčem - mají-li prvky X a Y stejný klíč a v původním neseřazeném poli se prvek X vyskytuje před prvkem Y, ve výsledném seřazeném poli tomu tak po použití nestabilního řazení nemusí být).
 
Asymptotická složitost je <math>O(n^2)</math>. Přesto je shellShell sort z kvadratických řadicích [[algoritmus|algoritmů]] nejvýkonnější. Časová složitost shellShell sortu je přibližně rovna <math>n^{3/2}</math>.
 
== Princip ==
Shell sort funguje podobně jako [[insert sort]]. Ovšem shellShell sort neřadí prvky umístěné vedle sebe, nýbrž prvky mezi nimiž je určitá mezera. V každém následujícím kroku je mezera zmenšena. V okamžiku, kdy je mezera zmenšena na velikost 1, tak je principiálně řazeno pomocí insert sortu. Výhoda tohoto přístupu (řazení se snižujícím se přírůstkem) je rychlé přemístění nízkých a vysokých hodnot. Poslední iterace totiž přesune jen minimum prvků.
 
=== Velikost mezery ===
Řádek 35:
 
=== Shell sort v jazyce C/C++ ===
Následující implementace shellShell sortu v [[C (programovací jazyk)|jazyce C]] seřadí [[pole (datová struktura)|pole]] celočíselných typů (''int''ů).
 
<source lang=c>