Shellovo řazení

Technology

12 hours ago

Author

Shellovo řazení je algoritmus pro třídění dat v počítačové vědě. Tento algoritmus je založen na principu postupného porovnávání prvků seznamu a jejich přesouvání do správného pořadí. Shellovo řazení je optimalizované pro třídění větších množin dat, kde jiné algoritmy by byly neefektivní. Hlavním principem Shellova řazení je rozdělení seznamu na menší části a jejich následné setřídění. Poté probíhá postupné slévání těchto menších sekvencí, přičemž se opakovaně provádí porovnání prvků a jejich přesunutí na správné místo. Tímto postupem se zlepšuje třídění prvků a dosahuje se lepšího výkonu než u některých jiných algoritmů. Shellovo řazení je efektivní zejména v případech, kdy je množství dat větší nebo kdy jsou prvky seznamu již částečně seřazené. Tento algoritmus může být implementován různými způsoby, záleží na konkrétní implementaci a programovacím jazyku. Shellovo řazení bylo představeno v roce 1959 Donaldem Shellovem a dodnes je jedním z nejpoužívanějších algoritmů pro třídění dat. Díky své efektivitě a jednoduchosti implementace je využíváno v různých aplikacích a programovacích jazycích.

Prohazování barevných pruhů Shellovým řazení s mezerami 5, 3, 1 Shellovo řazení, známé také pod anglickým jménem 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 O(n^2). Přesto je Shellovo řazení z kvadratických řadicích algoritmů nejvýkonnější. +more Časová složitost Shellova řazení je přibližně rovna n^{3/2}.

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. +more 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. +more 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 = 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 = 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 . +more 1 : (int) Math. round(prirustek / 2. 2))) { for (int i = prirustek; i = prirustek && a[j - prirustek] > temp; j -= prirustek){ a[j] = a[j - prirustek]; a[j - prirustek] = temp; } } } }.