Shellovo řazení
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
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 .
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ů.
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).
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 } }
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);
}
}
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;
}
}
}
}
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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.