Hél rendezési algoritmus példával
⚡ Okos összefoglaló
A Shell Sort egy helyben végzett összehasonlító algoritmus, amely általánosítja a beszúrásos rendezést úgy, hogy összehasonlítja az egymástól távol eső elemeket, majd csökkenti a rést, amíg a szomszédos elemek rendezve nem lesznek.

Mi a Shell Sort?
A Shell-rendezés, más néven Shell-módszer, egy hatékony, helybeni összehasonlításon alapuló rendezési algoritmus. Donald Shellről nevezték el, aki 1959-ben vezette be az ötletet, és a beszúrásos rendezés általánosított kiterjesztése, amely legyőzi annak kvadratikus viselkedését szétszórt adatokon.
Az alapötlet az, hogy csoportosítsuk az egymástól távol eső elemeket, rendezzük az egyes csoportokat beszúró rendezéssel, és lépésről lépésre csökkentsük a rést, amíg el nem éri az egyet. Addigra a tömb majdnem rendezett.
Ez a rés, az intervallum, egy kiválasztott sorozatot követ, például Shell eredeti, Knuth, Hibbard vagy Sedgewick sorozatát. Shell eredetije a következő: n/2, n/4, ..., 1.
Shell rendezési algoritmus
Step 1) Inicializálja a h = n/2 intervallumértéket, ahol n a tömb mérete.
Step 2) Helyezzük el egy allistába az összes elemet a h intervallumon belül.
Step 3) Rendezze az egyes allistákat beszúrásos rendezés segítségével.
Step 4) Állítson be egy új h = h/2 intervallumot.
Step 5) Ha h > 0, térjen vissza a 2. lépéshez. Ellenkező esetben folytassa a 6. lépéssel.
Step 6) A kapott tömb most már teljesen rendezett.
Hogyan működik a Shell rendezés
A beszúrós rendezésnél az elemek egyszerre csak egy pozícióval mozdulnak el. A shell rendezés ehelyett a tömböt széles távolságra lévő allistákra osztja az intervallum alapján, és minden allistán beszúrós rendezést futtat.
Ahogy az intervallum csökken, az allista mérete növekszik. Mivel a korábbi menetek részben rendezett állapotban hagyják az adatokat, a kisebb intervallumok sokkal kevesebb cserét igényelnek, mint a futtatott függvények. beszúrási rendezés a nulláról. Az alábbi ábra egy Shell rendezési menetet szemléltet.
A Shell rendezési algoritmus működése példával
Rendezzük az alábbi tömböt a Shell Sort segítségével.
Step 1) A tömb mérete 8, tehát a kezdeti intervallumérték h = 8/2 = 4.
Step 2) Az elemeket négy pozíciónyi távolságra csoportosítsa. Allisták: {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Step 3) Rendezd az egyes allistákat beszúró rendezéssel. Egy ideiglenes változó tárolja az elemek eltolódása közben elhelyezett értéket. A cserék után a tömb így néz ki.
Step 4) Csökkentsd az intervallumot. Az új intervallum h = 4/2 = 2.
Step 5) Mivel 2 > 0, térjünk vissza a 2. lépéshez, és csoportosítsuk az elemeket két pozícióval egymástól: {1, 5, 8, 7} és {4, 2, 6, 3}.
Rendezd az első részlistát. A tömb a következőképpen alakul:
A második allida rendezése után:
Csökkentse ismét az intervallumot h = 2/2 = 1-re. Egy rés esetén a Shell Sort egy végső beszúrási rendezést futtat a teljes tömbön, az alábbiak szerint.
Step 6) Az intervallum újbóli elosztása 0-t eredményez. A tömb most már teljesen rendezett:
Ál-Code a Shell Sorthoz
Start Input array a of size n for (interval = n / 2; interval > 0; interval /= 2) for (i = interval; i < n; i += 1) temp = a[i]; for (j = i; j >= interval && a[j - interval] > temp; j -= interval) a[j] = a[j - interval]; a[j] = temp; End
Shell rendezési program C/C++
Bemenet:
//Shell Sort Program in C/C++ #include <bits/stdc++.h> using namespace std; void ShellSort(int data[], int size) { for (int interval = size / 2; interval > 0; interval /= 2) { for (int i = interval; i < size; i += 1) { int temp = data[i]; int j; for (j = i; j >= interval && data[j - interval] > temp; j -= interval) { data[j] = data[j - interval]; } data[j] = temp; } } } int main() { int data[] = {8, 6, 7, 2, 1, 4, 5, 3}; int size = sizeof(data) / sizeof(data[0]); ShellSort(data, size); cout << "Sorted Output: \n"; for (int i = 0; i < size; i++) cout << data[i] << " "; cout << "\n"; }
output:
Sorted Output:
1 2 3 4 5 6 7 8
Shell rendezési példa itt Python
Bemenet:
#Shell Sort Example in Python def ShellSort(data, size): interval = size // 2 while interval > 0: for i in range(interval, size): temp = data[i] j = i while j >= interval and data[j - interval] > temp: data[j] = data[j - interval] j -= interval data[j] = temp interval //= 2 data = [8, 6, 7, 2, 1, 4, 5, 3] ShellSort(data, len(data)) print('Sorted Output:') print(data)
output:
Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]
A Shell Sort alkalmazásai
A Shell Sort továbbra is megjelenik a modern rendszerekben, ahol a veremméret vagy az egyszerűség számít.
- Az Linux kernel A Shell Sort funkciót olyan helyeken használja, ahol fontos a hívásverem elkerülése.
- Az uClibc beágyazott C könyvtára Shell Sort-ot használ a memóriahasználat alacsonyan tartása érdekében.
- A bzip2 Shell Sort módszert használ a mély rekurzió elkerülésére a blokkrendezés során.
- A beágyazott firmware a Shell Sort módszert részesíti előnyben kis adathalmazok esetén, ahol a rekurzió korlátozott.
A Shell Sort előnyei és hátrányai
| Előnyök | Hátrányok |
|---|---|
| Nincs szükség hívásveremre, ami ideális beágyazott rendszerekhez. | Nem a leggyorsabb megoldás nagyon nagy tömbökhöz. |
| Könnyen megvalósítható kis mennyiségű kóddal. | A teljesítmény romlik a széles körben elterjedt elemeket tartalmazó adatokon. |
| Hatékony közepes méretű vagy részben rendezett tömbök esetén. | A legrosszabb eset időbeli komplexitása érzékeny a kiválasztott réssorozatra. |
| Helyben működik, tehát konstans segédmemóriát használ. | Nem stabil rendezés, így az egyenlő kulcsok megváltoztathatják a relatív sorrendet. |
Shell rendezési komplexitás elemzése
A Shell rendezés időbeli összetettsége
A Shell Sort időbeli komplexitása a használt réssorozattól függ.
A legjobb esetben, amikor a tömb már majdnem elrendezett, minden menethez csak logaritmikus számú tesztre van szükség, ami O(n log n) értéket eredményez.
A legrosszabb esetben a tömb úgy van elrendezve, hogy az elemeknek a lehető legtöbb összehasonlításra van szükségük, és a végső növekmény O(n^2)-nél dominál a Shell eredeti sorozatával.
- Legjobb eset komplexitása: O(n log n)
- Átlagos esetbonyolultság: O(n log n) - O(n^(4/3)) a réssorozattól függően
- Legrosszabb eset bonyolultsága: O(n^2) a Shell eredeti sorozatával
A legjobb általános célú résszekvencia továbbra is nyitott kutatási kérdés, bár a Sedgewick és Ciura szekvenciák a gyakorlatban jól teljesítenek.
Shell rendezési tér összetettsége
A Shell Sort nem igényel segédtömböket, így a helybonyolultság O(1) a bemeneti mérettől függetlenül, ami az egyik legerősebb gyakorlati előnye.










