Shell-lajittelualgoritmi esimerkin kanssa

Mikä on kuoren lajittelu?

Shell Sort, joka tunnetaan myös Shellin menetelmänä, on tehokas vertailuun perustuva lajittelualgoritmi. Se on nimetty Donald Shellin mukaan, joka esitteli idean vuonna 1959. Se on yleistetty lisäyslajittelun laajennus, joka ratkaisee sen neliöllisen käyttäytymisen hajallaan olevassa datassa.

Perusajatuksena on ryhmitellä kaukana toisistaan ​​olevat elementit, lajitella jokainen ryhmä lisäyslajittelulla ja pienentää rakoa askel askeleelta, kunnes se saavuttaa yhden. Tällöin taulukko on lähes lajiteltu.

Tämä aukko, intervalli, seuraa valittua järjestystä, kuten Shellin alkuperäinen, Knuthin, Hibbardin tai Sedgewickin. Shellin alkuperäinen on n/2, n/4, ..., 1.

Shell-lajittelualgoritmi

Vaihe 1) Alusta välin arvo h = n/2, jossa n on taulukon koko.

Vaihe 2) Sijoita kaikki välin h etäisyydellä olevat elementit alilistaan.

Vaihe 3) Lajittele jokainen alilista lisäyslajittelun avulla.

Vaihe 4) Aseta uusi aikaväli h = h/2.

Vaihe 5) Jos h > 0, palaa vaiheeseen 2. Muussa tapauksessa siirry vaiheeseen 6.

Vaihe 6) Tuloksena oleva taulukko on nyt täysin lajiteltu.

Kuinka Shell-lajittelu toimii

Lisäyslajittelussa elementit liikkuvat vain yhden sijainnin kerrallaan. Shell Sort jakaa taulukon harvaan sijoitettuihin alilistoihin aikavälin perusteella ja suorittaa lisäyslajittelun jokaiselle alilistalle.

Välin kutistuessa alilistan koko kasvaa. Koska aiemmat suoritukset jättävät tiedot osittain lajiteltuina, lyhyemmät välit vaativat paljon vähemmän vaihtoja kuin lisäyslaji alusta alkaen. Alla oleva kuva havainnollistaa yhtä Shell Sort -vaihetta.

Shell-lajittelualgoritmin toiminta esimerkin avulla

Lajitellaan alla oleva taulukko Shell Sort -menetelmällä.

Vaihe 1) Taulukon koko on 8, joten alkuarvon väli on h = 8/2 = 4.

Vaihe 2) Ryhmittele elementit neljän sijainnin välein. Alilistat: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Vaihe 3) Lajittele jokainen alilista lisäyslajittelun avulla. Väliaikainen muuttuja säilyttää sijoitettavaa arvoa elementtien siirtyessä. Vaihtojen jälkeen taulukko näyttää tältä.

Vaihe 4) Pienennä väliä. Uusi väli on h = 4/2 = 2.

Vaihe 5) Koska 2 > 0, palaa vaiheeseen 2 ja ryhmittele elementit kahden aseman päähän toisistaan: {1, 5, 8, 7} ja {4, 2, 6, 3}.

Lajittele ensimmäinen alilista. Taulukosta tulee:

Toisen alilistan lajittelun jälkeen:

Pienennä väliä uudelleen arvoon h = 2/2 = 1. Yhden aukon ollessa Shell Sort suorittaa viimeisen lisäyslajittelun koko taulukon yli, kuten alla on esitetty.

Vaihe 6) Välin jakaminen uudelleen antaa tulokseksi 0. Taulukko on nyt täysin lajiteltu:

Pseudo-Code Shell Sort -sovellukselle

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 lajitteluohjelma C/C++

input:

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

lähtö:

Sorted Output:

1 2 3 4 5 6 7 8

Shell Lajittelu esimerkki sisään Python

input:

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

lähtö:

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

Shell-lajittelun sovellukset

Shell Sort -menetelmää esiintyy edelleen nykyaikaisissa järjestelmissä, joissa pinotila tai yksinkertaisuus ovat tärkeitä.

• Linux-ytimen käyttää Shell Sort -menetelmää paikoissa, joissa kutsupinon välttäminen on tärkeää.
• uClibc:n upotettu C-kirjasto käyttää Shell Sort -ominaisuutta muistin käytön pitämiseksi alhaisena.
• bzip2 käyttää Shell Sort -menetelmää välttääkseen syvän rekursion lohkolajittelun aikana.
• Sulautettu laiteohjelmisto suosii Shell Sort -menetelmää pienille tietojoukoille, joissa rekursio on rajoitettua.

Shell Lajittelun edut ja haitat

Shell Lajittelun monimutkaisuusanalyysi

Shell-lajittelun aika monimutkaisuus

Shell Sort -menetelmän aikavaativuus riippuu käytetystä aukkosekvenssistä.

Parhaassa tapauksessa, kun taulukko on jo lähes järjestetty, jokainen läpimenokerta tarvitsee vain logaritmisen määrän testejä, jolloin saadaan O(n log n).

Pahimmassa tapauksessa taulukko on järjestetty siten, että alkiot tarvitsevat maksimaaliset vertailut ja lopullinen lisäys on hallitseva kohdassa O(n^2) Shellin alkuperäisellä sekvenssillä.

1. Parhaan tapauksen kompleksisuus: O(n log n)
2. Keskimääräinen tapauskompleksisuus: O(n log n) - O(n^(4/3)) riippuen aukkosekvenssistä
3. Pahimman tapauksen monimutkaisuus: O(n^2) Shellin alkuperäisellä sekvenssillä

Paras yleiskäyttöinen aukkosekvenssi on edelleen avoin tutkimuskysymys, vaikka Sedgewickin ja Ciuran sekvenssit toimivat käytännössä hyvin.

Shell lajittelutilan monimutkaisuus

Shell Sort ei vaadi aputaulukoita, joten avaruuskompleksisuus on O(1) syötteen koosta riippumatta, mikä on yksi sen vahvimmista käytännön eduista.

UKK