Shelli sortimise algoritm koos EXAMPLE'iga

Mis on Shelli sortimine

Shelli meetod ehk Shell sortimine andmestruktuuris on tõhus kohapealne võrdlussortimisalgoritm. See on oma nime saanud Donald Shelli järgi, kui ta 1959. aastal esialgse idee välja pakkus. Shell-sorteerimine on sisestamise sortimise algoritmi üldistatud laiendus.

Selle sorteerimisalgoritmi põhiidee on rühmitada üksteisest kaugel asuvad elemendid ja sorteerida need vastavalt. Seejärel vähendage nende vahelist vahet järk-järgult. Shell sortimine ületab sisestamise sortimise keskmise juhtumiaja keerukuse, võrreldes ja vahetades kaugel asuvaid elemente.

Seda vahet, mida nimetatakse intervalliks, vähendatakse vastavalt mõnele optimaalsele vahejärjestusele. Nendest järjestustest sõltub ka kesta sortimise tööaeg. On mitmeid lünkjadasid, nagu Shelli algne jada, Knuthi valem, Hibbardi juurdekasvud jne. Shelli algne vahejada on – n/2, n/4, n/8, ……….1

Shelli sortimise algoritm

Shelli sortimisalgoritmi etapid või protseduur on järgmine:

Step 1) Initsialiseerige intervalli väärtus, h = n/2. (Selles näites on n massiivi suurus)

Step 2) Asetage alamloendisse kõik elemendid, mis jäävad intervalli h kaugusele.

Step 3) Sorteerige need alamloendid sisestussortimise abil.

Step 4) Määra uus intervall, h=h/2.

Step 5) Kui h>0, jätkake 2. sammuga. Muul juhul jätkake 6. sammuga.

Step 6) Tulemuseks on sorteeritud massiiv.

Kuidas Shelli sortimine töötab

Sisestussortimisel liigutatakse elemente korraga ainult ühe positsiooni võrra. Vastupidi, shellisortimine jagab massiivi intervalli väärtuse alusel väiksemateks osadeks ja teostab nende osade sisestussortimise.

Järk-järgult intervalli väärtus väheneb ja jagatud tükkide suurus suureneb. Kuna tükid sorteeritakse eelnevalt eraldi, nõuab nende osade ühendamine vähem samme kui sisestamise sort.

Järgmine GIF näitab kesta sortimise demonstratsiooni. Selles demos võrreldakse punast ja sinist näidatud väärtust ja vahetatakse sisestussortimise alusel. Seejärel intervall väheneb ja shellisortimine käivitab peaaegu sorteeritud andmete sisestamise.

Shelli sortimise algoritmi töö

Vaatame järgmist näidet shellisortimisalgoritmi kohta. Selles näites sorteerime shellisordi abil järgmise massiivi:

Step 1) Siin on massiivi suurus 8. Seega on intervalli väärtus h = 8/2 või 4.

Step 2) Nüüd salvestame kõik elemendid 4 kaugusele. Meie puhul on alamloendid järgmised: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Step 3) Nüüd sorteeritakse need alamloendid sisestussortimise abil, kus mõlema numbri võrdlemiseks ja vastavalt sortimiseks kasutatakse ajutist muutujat.

Massiiv oleks pärast vahetustoiminguid järgmine -

Step 4) Nüüd vähendame intervalli algväärtust. Uus intervall on h=h/2 või 4/2 või 2.

Step 5) Kui 2>0, läheme sammu 2, et salvestada kõik elemendid 2 kaugusele. Sel ajal on alamloendid

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

Seejärel sorteeritakse need alamloendid sisestussortimise abil. Pärast esimese alamloendi võrdlemist ja vahetamist oleks massiiv järgmine.

Pärast teise alamloendi sortimist on algne massiiv järgmine:

Seejärel vähendatakse intervalli uuesti. Nüüd on intervall h=h/2 või 2/1 või 1. Seetõttu kasutame muudetud massiivi sortimiseks sisestamise sortimise algoritmi.

Järgnevalt on esitatud sisestamise sortimise protseduuriline samm-sammuline kirjeldus.

Intervall jagatakse jälle 2-ga. Selleks ajaks muutub intervall 0-ks. Nii et läheme 6. sammu juurde.

Step 6) Kuna intervall on 0, sorteeritakse massiiv selle aja järgi. Sorteeritud massiiv on -

Pseudokood

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

Shelli sortimisprogramm keeles C/C++

sisend:

//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";
}

Väljund:

Sorted Output:

1 2 3 4 5 6 7 8

Shelli sortimise näide sisse Python

sisend:

#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)

Väljund:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Shelli sortimise rakendused

Siin on Shell Sorti olulised rakendused:

• Shell sorti kasutatakse Linux kernel sest see ei kasuta kõnepinu.
• uClibc teek kasutab Shelli sortimist.
• bzip2 kompressor kasutab Shelli sortimist, et peatada rekursiooni ületamine.

Shelli sortimise eelised ja puudused

Eelised	Puudused
Pinnakutset pole vaja.	Ei ole tõhus suurte massiivide jaoks.
Lihtne rakendamine.	Ebaefektiivne laialt levinud elementide jaoks.
Tõhus väiksema vahega elementide jaoks.

Shelli sortimise keerukuse analüüs

Shelli sortimise ajaline keerukus

Shelli sorteerimisalgoritmi ajaline keerukus on O(n^2). Põhjendus on järgmine:

Parima stsenaariumi korral on testide koguhulk kõigi intervallide jaoks, kui massiiv oli eelnevalt paigutatud võrdseks log n. Seega oleks keerukus O(n*log n).

Halvima stsenaariumi puhul kaalume, et massiiv koosneb sellisest, et elemendid nõuavad kõige rohkem võrdlusi. Siis ei võrrelda ega vahetata kõiki elemente enne viimast iteratsiooni. Seetõttu on lõpliku juurdekasvu jaoks vajalik kogu võrdlus O(n^2).

Kokkuvõttes oleks ajaline keerukus

1. Parimal juhul keerukus: O(n*log n)
2. Juhtumi keskmine keerukus: O(n*log n)
3. Halvimal juhul keerukus: O(n^2)

Shelli sortimise tööaja keerukus sõltub suuresti kasutatavatest tühikute suurendamise järjestustest. Kuid kesta sortimise parim juurdekasvu jada on endiselt teadmata.

Shelli sortimise ruumi keerukus

Selles võrdlussordis ei vaja me täiendavat abiruumi. Seega on seda tüüpi algoritmi ruumiline keerukus O(1).