Shellovo řazení
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Shell_sorting_algorithm_color_bars.svg/220px-Shell_sorting_algorithm_color_bars.svg.png)
Shellovo řazení, známé také pod anglickým jménem Shell sort nebo též řazení se snižujícím se přírůstkem, je řadicí algoritmus podobný algoritmu řazení vkládáním, který objevil a v roce 1959 publikoval Donald Shell.
Shellovo řazení je 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 . Přesto je Shellovo řazení z kvadratických řadicích algoritmů nejvýkonnější. Časová složitost Shellova řazení je přibližně rovna .
Princip
Shellovo řazení funguje podobně jako řazení vkládáním. Ovšem Shellovo řazení 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í řazení vkládáním. 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
Aby byla zajištěna nejvyšší efektivita algoritmu, je potřeba zvolit ideální velikost mezery. Marcin Ciura zjistil, že ideální mezerou je 2,2. Jako počáteční mezera je tedy v algoritmu použita největší možná z řady čísel: 1, 4, 10, 23, 57, 132, 301, 701, ... (celočíselné násobky 2,2).
Implementace
Pseudokód s vnitřním řazením vkládáním (posloupnost od Marcin Ciura):
# řazení v poli a[0...n-1]. mezery = [701, 301, 132, 57, 23, 10, 4, 1] foreach (mezera in mezery) { # Proveďte řazení vkládáním pro každou velikost mezery. for (i = mezera; i < n; i += 1) { temp = a[i] for (j = i; j >= mezera and a[j - mezera] > temp; j -= mezera) { a[j] = a[j - mezera] } a[j] = temp } }
Shellovo řazení v jazyce C/C++
Následující implementace Shellova řazení v jazyce C seřadí pole celočíselných typů (intů).
void shellovo_razeni(int A[], int velikost) { int i, j, prirustek, temp; prirustek = velikost / 2; while (prirustek > 0) { for (i = prirustek; i < velikost; i++) { j = i; temp = A[i]; while ((j >= prirustek) && (A[j-prirustek] > temp)) { A[j] = A[j - prirustek]; j = j - prirustek; } A[j] = temp; } if (prirustek == 2) prirustek = 1; else prirustek = (int) (prirustek / 2.2); } }
Shellovo řazení v Javě
Implementace v Javě je následující:
public static void shellovoRazeni(int[] a) { for (int prirustek = a.length / 2; prirustek > 0; prirustek = (prirustek == 2 ? 1 : (int) Math.round(prirustek / 2.2))) { for (int i = prirustek; i < a.length; i++) { int temp = a[i]; for (int j = i; j >= prirustek && a[j - prirustek] > temp; j -= prirustek){ a[j] = a[j - prirustek]; a[j - prirustek] = temp; } } } }
Shellovo řazení v Pythonu
def shellovorazeni(a): def prirustek_generator(a): h = len(a) while h != 1: if h == 2: h = 1 else: h = 5*h//11 yield h for prirustek in prirustek_generator(a): for i in range(prirustek, len(a)): for j in range(i, prirustek-1, -prirustek): if a[j - prirustek] < a[j]: break a[j], a[j - prirustek] = a[j - prirustek], a[j] return a
Reference
- http://dudka.cz/studyIAL
- http://www.algoritmy.net/article/154/Shell-sort