Shell rendezési algoritmus az EXAMPLE segítségével

Mi az a Shell Sort

A Shell metódusa vagy a Shell rendezés adatstruktúrában egy hatékony helybeni összehasonlító rendezési algoritmus. Nevét Donald Shellről kapta, amikor 1959-ben felvetette az eredeti ötletet. A Shell rendezés a beillesztési rendezési algoritmus általánosított kiterjesztése.

Ennek a rendezési algoritmusnak az alapötlete, hogy az egymástól távol eső elemeket csoportosítsa, és ennek megfelelően rendezze őket. Ezután fokozatosan csökkentse a köztük lévő távolságot. A Shell-rendezés a távoli elemek összehasonlításával és cseréjével legyőzi a beillesztési rendezés átlagos esetidő-bonyolultságát.

Ezt az intervallumnak nevezett rést néhány optimális réssorozatnak megfelelően csökkentjük. A shell rendezés futási ideje is ezektől a sorozatoktól függ. Számos réssorozat létezik, mint például a Shell eredeti sorozata, Knuth képlete, Hibbard növekményei stb. A Shell eredeti résszekvenciája: n/2, n/4, n/8, ……….1

Shell rendezési algoritmus

A shell rendezési algoritmus lépései vagy eljárása a következő:

Step 1) Inicializálja az intervallum értékét, h = n/2. (Ebben a példában n a tömb mérete)

Step 2) Tegye az összes elemet a h intervallum távolságán belül egy részlistába.

Step 3) Rendezze ezeket az allistákat a beillesztési rendezés segítségével.

Step 4) Új intervallum beállítása, h=h/2.

Step 5) Ha h>0, folytassa a 2. lépéssel. Ellenkező esetben folytassa a 6. lépéssel.

Step 6) Az eredményül kapott kimenet a rendezett tömb lesz.

Hogyan működik a Shell rendezés

A beszúrásos rendezésnél az elemek egyszerre csak egy pozícióval mozognak. Éppen ellenkezőleg, a shell-rendezés az intervallumérték alapján kisebb darabokra osztja a tömböt, és beszúrásos rendezést hajt végre ezeken a darabokon.

Fokozatosan csökken az intervallum értéke, és nő a felosztott darabok mérete. Mivel a darabokat előzetesen egyenként rendezik, ezeknek a daraboknak az összevonása kevesebb lépést igényel, mint a beszúrási rendezés.

A következő GIF a shell rendezést mutatja be. Ebben a bemutatóban a piros és a kék jelzett értéket összehasonlítjuk és felcseréljük a beillesztési rendezés alapján. Ezután az intervallum csökken, és a shell-rendezés beszúrásos rendezést kezdeményez abban a majdnem rendezett adatban.

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

Nézzünk egy következő példát egy shell-rendezési algoritmusra. Ebben a példában a következő tömböt a shell-rendezéssel rendezzük:

Step 1) Itt a tömb mérete 8. Így az intervallum értéke h = 8/2 vagy 4 lesz.

Step 2) Most az összes elemet 4-es távolságra tároljuk. Esetünkben az allisták a következők: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Step 3) Most ezek az allisták a beillesztési rendezés segítségével lesznek rendezve, ahol egy ideiglenes változót használnak a számok összehasonlítására és a megfelelő rendezésre.

A tömb a következő lesz a csereműveletek után-

Step 4) Most csökkentjük az intervallum kezdeti értékét. Az új intervallum h=h/2 vagy 4/2 vagy 2 lesz.

Step 5) 2>0-ként megyünk a 2. lépésre, hogy az összes elemet 2 távolságra tároljuk. Ekkor az allisták:

{1, 5, 8, 7}, {4, 2, 6, 3}

Ezután ezek az allisták a beillesztési rendezés segítségével lesznek rendezve. Az első részlista összehasonlítása és cseréje után a tömb a következő lesz.

A második allista rendezése után az eredeti tömb a következő lesz:

Ekkor ismét csökken az intervallum. Most az intervallum h=h/2 vagy 2/1 vagy 1 lesz. Ezért a beillesztési rendezési algoritmust használjuk a módosított tömb rendezésére.

Az alábbiakban a beillesztési rendezés lépésről lépésre történő eljárási leírása látható.

Az intervallumot ismét elosztjuk 2-vel. Ekkorra az intervallum 0 lesz. Így továbblépünk a 6. lépésre.

Step 6) Mivel az intervallum 0, a tömb ez alapján kerül rendezésre. A rendezett tömb:

Pszeudo-kód

Start
Input array an of size n
for (interval = n / 2; interval & gt; 0; interval /= 2)
    for (i = interval; i & lt; n; i += 1)
        temp = a[i];
for (j = i; j & gt; = interval & amp; & amp; a[j - interval] & gt; 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

Íme a Shell Sort fontos alkalmazásai:

• Shell rendezést használnak a Linux kernel mert nem használ hívásveremet.
• Az uClibc könyvtár Shell rendezést használ.
• A bzip2 tömörítő a Shell rendezést használja a rekurzió túllépésének megakadályozására.

A Shell rendezés előnyei és hátrányai

Előnyök	Hátrányok
Nincs szükség veremhívásra.	Hatalmas tömbméreteknél nem hatékony.
Könnyű megvalósítás.	Nem hatékony a széles körben elterjedt elemekhez.
Hatékony kevésbé távoli elemekhez.

Shell rendezési komplexitás elemzése

A Shell rendezés időbeli összetettsége

A shell rendezési algoritmus időbonyolultsága O(n^2). Az indoklás a következő:

A legjobb forgatókönyv esetén a tesztek teljes száma az összes olyan intervallumban, amikor a tömb előzőleg log n volt. Így a komplexitás O(n*log n) lenne.

A legrosszabb forgatókönyv esetén tekintsük úgy, hogy a tömb úgy áll össze, hogy az elemek a legtöbb összehasonlítást igénylik. Ekkor a rendszer az utolsó iterációig nem hasonlítja össze és váltja át az összes elemet. Ezért a végső növekményhez szükséges összes összehasonlítás O(n^2).

Összefoglalva, az idő bonyolultsága a következő lenne

1. Legjobb eset összetettsége: O(n*log n)
2. Az esetek átlagos összetettsége: O(n*log n)
3. A legrosszabb eset bonyolultsága: O(n^2)

A shell-rendezés futási időbeli összetettsége nagymértékben függ a használt hézagnövelési szekvenciáktól. A shell-rendezés legjobb növekményi sorrendje azonban még mindig ismeretlen.

Shell rendezési tér összetettsége

Ebben az összehasonlításban nincs szükségünk további segédtérre. Így ennek a fajta algoritmusnak a térkomplexitása O(1).