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.

  • 📊 Meghatározás: Donald Shell által 1959-ben javasolt inplace általánosítás a beszúrási rendezésről, amely csökkenő réssorozatot használ.
  • 🔀 Rés szekvenciák: A Shell eredeti sorozata n/2, n/4, …, 1; a Knuth-, Sedgewick- és Ciura-sorozatok a gyakorlatban jobban teljesítenek.
  • ⚡ Bonyolultság: O(n log n) legjobb eset, O(n^2) legrosszabb eset és O(1) segédtér.
  • ✅ Használási esetek: A Linux kernel, az uClibc és a bzip2 Shell Sort módszert használ a rekurzió és a plusz veremmemória elkerülése érdekében.
  • 🤖 AI szög: A mesterséges intelligencia által fejlesztett asszisztensek igény szerint javasolhatnak réssorozatokat és animált Shell Sort vizualizációkat generálhatnak.

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.

Shell rendezés működik

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.

Shell rendezési algoritmus működése

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}.

Shell rendezési algoritmus működése

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.

Shell rendezési algoritmus működése

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}.

Shell rendezési algoritmus működése

Rendezd az első részlistát. A tömb a következőképpen alakul:

Shell rendezési algoritmus működése

A második allida rendezése után:

Shell rendezési algoritmus működése

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.

Shell rendezési algoritmus működése

Shell rendezési algoritmus működése

Shell rendezési algoritmus működése

Step 6) Az intervallum újbóli elosztása 0-t eredményez. A tömb most már teljesen rendezett:

Shell rendezési algoritmus működése

Á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.

  1. Legjobb eset komplexitása: O(n log n)
  2. Átlagos esetbonyolultság: O(n log n) - O(n^(4/3)) a réssorozattól függően
  3. 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.

GYIK

A Shell Sort egy helyszíni összehasonlító rendezési algoritmus, amelyet Donald Shell javasolt 1959-ben. Általánosítja a beszúrásos rendezést azáltal, 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, ami drámaian csökkenti a cserék számát.

A Shell eredeti szekvenciájával a legjobb eset időbonyolultsága O(n log n), a legrosszabb eset komplexitása pedig O(n^2). A jobb résszekvenciák, mint például a Sedgewick-féle, a legrosszabb esetet körülbelül O(n^(4/3))-ra csökkentik. A térbonyolultság O(1).

Nem, a Shell rendezés nem stabil. Mivel az elemek összehasonlítása és cseréje nagy réseken keresztül történik, két egyenlő kulcs megváltoztathatja a relatív sorrendet egy menet során. Ha a stabilitás számít, használjon összevont rendezést vagy a beszúró rendezés egy stabil változatát.

A beszúrásos rendezés egyszerre egy pozícióval mozgatja az elemeket. A rendszerelemes rendezés először az egymástól távol eső elemeket hasonlítja össze, majd fokozatosan csökkenti a rést. Az eredmény egy majdnem rendezett tömb lesz, mire a rés eléri az egyet, így a végső beszúrásos rendezés nagyon gyorsan befejeződik.

Az AI-asszisztensek elemezhetik az adathalmaz méretét, eloszlását és korlátozásait, majd javasolhatnak egy algoritmust, például a Shell Sort-ot, a gyorsrendezést vagy a radix rendezést. Emellett benchmark szkripteket is generálhatnak, amelyek összehasonlítják a futásidejű és a memóriahasználatot, így a javaslat valós munkaterheléseken validálható.

Igen. A mesterséges intelligencia eszközök képesek animált vizualizációkat generálni a Shell Sortról, amelyek valós időben emelik ki a réscsoportokat, összehasonlításokat és cseréket. Az ilyen vizualizációk segítenek a tanulóknak abban, hogy lássák, hogyan zsugorodik az intervallum, és hogyan konvergál a tömb egy rendezett állapot felé menetről menetre.

Foglald össze ezt a bejegyzést a következőképpen: