Shell Lajittelualgoritmi EXAMPLE:n avulla
Sarah Chen
Mikä on Shell Sort
Shellin menetelmä eli Shell-lajittelu tietorakenteessa on tehokas vertailulajittelualgoritmi. Se on nimetty Donald Shellin mukaan, kun hän ehdotti alkuperäistä ideaa vuonna 1959. Shell-lajittelu on lisäyslajittelualgoritmin yleistetty laajennus.
Tämän lajittelualgoritmin perusideana on ryhmitellä toisistaan kaukana olevat elementit ja lajitella ne sen mukaan. Pienennä sitten niiden välistä rakoa vähitellen. Shell-lajittelu voittaa lisäyslajittelun keskimääräisen tapausaikaisen monimutkaisuuden vertaamalla ja vaihtamalla kaukana olevia elementtejä.
Tätä väliä, joka tunnetaan nimellä intervalli, pienennetään joidenkin optimaalisten aukkosekvenssien mukaan. Shell-lajittelun ajoaika riippuu myös näistä sekvensseistä. On olemassa useita aukkojaksoja, kuten Shellin alkuperäinen sekvenssi, Knuthin kaava, Hibbardin inkrementit jne. Shellin alkuperäinen aukkosekvenssi on – n/2, n/4, n/8, ……….1
Shell-lajittelualgoritmi
Shellin lajittelualgoritmin vaiheet tai menettelytavat ovat seuraavat:
Vaihe 1) Alusta välin arvo, h = n/2. (Tässä esimerkissä n on taulukon koko)
Vaihe 2) Sijoita kaikki alkiot, jotka ovat välin h etäisyydellä aliluettelosta.
Vaihe 3) Lajittele nämä aliluettelot lisäyslajittelulla.
Vaihe 4) Aseta uusi intervalli, h=h/2.
Vaihe 5) Jos h>0, siirry vaiheeseen 2. Muussa tapauksessa siirry vaiheeseen 6.
Vaihe 6) Tuloksena oleva tulos on lajiteltu matriisi.
Kuinka Shell-lajittelu toimii
Lisäyslajittelussa elementtejä siirretään vain yhden sijainnin verran kerrallaan. Päinvastoin, shell-lajittelu jakaa taulukon pienempiin osiin intervalliarvon perusteella ja suorittaa lisäyslajittelun näille kappaleille.
Vähitellen intervalliarvo pienenee ja jaettujen kappaleiden koko kasvaa. Koska palat lajitellaan erikseen etukäteen, näiden osien yhdistäminen vaatii vähemmän vaiheita kuin lisäyslaji.
Seuraava GIF näyttää shell-lajittelun esityksen. Tässä esittelyssä punaista ja sinistä ilmoitettua arvoa verrataan ja vaihdetaan lisäyslajittelun perusteella. Sitten aikaväli pienenee, ja komentotulkkilajittelu aloittaa lisäyslajittelun lähes lajiteltuun dataan.
Shell-lajittelualgoritmin toiminta
Katsotaan seuraava esimerkki shell-lajittelualgoritmista. Tässä esimerkissä lajittelemme seuraavan taulukon käyttämällä komentotulkkilajittelua:
Vaihe 1) Tässä taulukon koko on 8. Siten intervalliarvo on h = 8/2 tai 4.
Vaihe 2) Nyt tallennamme kaikki elementit 4:n etäisyydelle. Meidän tapauksessamme alilistat ovat {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Vaihe 3) Nyt nuo aliluettelot lajitellaan lisäyslajittelulla, jossa väliaikaista muuttujaa käytetään vertaamaan molempia numeroita ja lajittelemaan sen mukaan.
Taulukko olisi seuraavanlainen vaihtotoimintojen jälkeen-
Vaihe 4) Nyt pienennämme intervallin alkuarvoa. Uusi väli on h=h/2 tai 4/2 tai 2.
Vaihe 5) Kuten 2>0, siirrymme vaiheeseen 2 tallentamaan kaikki elementit 2:n etäisyydelle. Tällä kertaa aliluettelot ovat
{1, 5, 8, 7}, {4, 2, 6, 3}
Sitten nämä aliluettelot lajitellaan lisäyslajittelulla. Ensimmäisen aliluettelon vertailun ja vaihtamisen jälkeen matriisi olisi seuraava.
Kun olet lajitellut toisen aliluettelon, alkuperäinen matriisi on:
Sitten taas väliä lyhennetään. Nyt väli on h=h/2 tai 2/1 tai 1. Tästä syystä käytämme lisäyslajittelualgoritmia lajitellaksesi muokatun taulukon.
Seuraavassa on vaiheittainen esitys lisäyslajittelusta.
Väli jaetaan jälleen kahdella. Tässä vaiheessa väli on 2. Siirrymme siis vaiheeseen 0.
Vaihe 6) Koska väli on 0, taulukko lajitellaan tämän ajan mukaan. Lajiteltu matriisi on-
Pseudokoodi
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 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
Tässä on tärkeitä Shell Sort -sovelluksia:
- Shell lajittelua käytetään Linux-ytimen koska se ei käytä puhelupinoa.
- uClibc-kirjasto käyttää Shell-lajittelua.
- bzip2-kompressori käyttää Shell-lajittelua estääkseen rekursion ylityksen.
Shell-lajittelun edut ja haitat
| edut | Haitat |
|---|---|
| Pinokutsua ei tarvita. | Ei tehokas suurille ryhmille. |
| Helppo toteutus. | Tehoton laajalle levinneille elementeille. |
| Tehokas vähemmän erillään oleville elementeille. |
Shell Lajittelun monimutkaisuusanalyysi
Shell-lajittelun aika monimutkaisuus
Shellin lajittelualgoritmin aikamonimutkaisuus on O(n^2). Perustelut ovat seuraavat:
Parhaassa tapauksessa testien kokonaismäärä kaikilta aikaväleiltä, kun taulukko oli aiemmin järjestetty, on yhtä suuri log n. Siten kompleksisuus olisi O(n*log n).
Pahimmassa tapauksessa katsotaan, että taulukko koostuu siten, että elementit vaativat eniten vertailuja. Silloin kaikkia elementtejä ei verrata ja vaihdeta ennen viimeistä iteraatiota. Siksi lopulliseen lisäykseen tarvittavat vertailut ovat O(n^2).
Lopuksi aika monimutkaisuus olisi
- Parhaan tapauksen monimutkaisuus: O(n*log n)
- Tapausten keskimääräinen monimutkaisuus: O(n*log n)
- Huonoin tapauksen monimutkaisuus: O(n^2)
Shell-lajittelun ajoaika monimutkaisuus riippuu suuresti käytetyistä aukon lisäyssekvensseistä. Paras kuorilajittelun lisäysjärjestys on kuitenkin vielä tuntematon.
Shell lajittelutilan monimutkaisuus
Tässä vertailulajittelussa emme tarvitse ylimääräistä aputilaa. Siten tämäntyyppisen algoritmin avaruuskompleksisuus on O(1).
