Shell sort algoritam s primjerom

Što je Shell sortiranje?

Shellovo sortiranje, također nazvano Shellovom metodom, učinkovit je algoritam sortiranja temeljen na usporedbi na mjestu. Nazvan po Donaldu Shellu, koji je predstavio tu ideju 1959. godine, to je generalizirano proširenje sortiranja umetanjem koje prevladava njegovo kvadratno ponašanje na raspršenim podacima.

Temeljna ideja je grupirati elemente koji su međusobno udaljeni, sortirati svaku grupu pomoću sortiranja umetanjem i smanjivati ​​razmak korak po korak dok ne dosegne jedan. Do tada je niz gotovo sortiran.

Ovaj razmak, interval, slijedi odabrani slijed kao što je Shellov original, Knuthov, Hibbardov ili Sedgewickov. Shellov original je n/2, n/4, ..., 1.

Algoritam sortiranja ljuske

Korak 1) Inicijalizirajte vrijednost intervala h = n/2, gdje je n veličina polja.

Korak 2) Smjestite sve elemente unutar udaljenosti intervala h u podlistu.

Korak 3) Sortiraj svaku podlistu koristeći sortiranje umetanjem.

Korak 4) Postavi novi interval h = h/2.

Korak 5) Ako je h > 0, vratite se na korak 2. U suprotnom, idite na korak 6.

Korak 6) Rezultirajući niz je sada potpuno sortiran.

Kako Shell Sort radi

U sortiranju umetanjem, elementi se pomiču samo za jednu poziciju odjednom. Shell sortiranje umjesto toga dijeli niz na široko razmaknute podliste na temelju intervala i izvodi sortiranje umetanjem na svakoj podlisti.

Kako se interval smanjuje, veličina podliste raste. Budući da raniji prolazi ostavljaju podatke djelomično sortiranima, manji intervali zahtijevaju puno manje zamjena nego izvođenje umetanje sortirati od nule. Donja slika ilustrira jedan prolaz Shell sortiranja.

Rad algoritma Shell sortiranja s primjerom

Sortirajmo niz ispod koristeći Shell Sort.

Korak 1) Veličina polja je 8, pa je početna vrijednost intervala h = 8/2 = 4.

Korak 2) Grupiraj elemente s razmakom od četiri pozicije. Podliste: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Korak 3) Sortirajte svaku podlistu pomoću sortiranja umetanjem. Privremena varijabla sadrži vrijednost koja se postavlja dok se elementi pomiču. Nakon zamjena, niz izgleda ovako.

Korak 4) Smanjite interval. Novi interval je h = 4/2 = 2.

Korak 5) Budući da je 2 > 0, vratite se na korak 2 i grupirajte elemente s razmakom od dvije pozicije: {1, 5, 8, 7} i {4, 2, 6, 3}.

Sortiraj prvu podlistu. Niz postaje:

Nakon sortiranja druge podliste:

Ponovno smanjite interval na h = 2/2 = 1. S razmakom od jedan, Shell Sort izvršava završni prolaz sortiranja umetanjem preko cijelog polja, kao što je prikazano dolje.

Korak 6) Ponovno dijeljenje intervala daje 0. Niz je sada potpuno sortiran:

Pseudo-Code za Shell sortiranje

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 Sort Program u C/C++

Ulazni:

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

Izlaz:

Sorted Output:

1 2 3 4 5 6 7 8

Shell Sort Primjer u Python

Ulazni:

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

Izlaz:

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

Primjene Shell Sort

Shell sortiranje se još uvijek pojavljuje u modernim sustavima gdje su prostor na stoga ili jednostavnost važni.

• The Linux kernel koristi Shell Sort na mjestima gdje je važno izbjegavanje steka poziva.
• Ugrađena C biblioteka uClibc koristi Shell Sort kako bi korištenje memorije bilo što kraće.
• bzip2 koristi Shell Sort kako bi izbjegao duboku rekurziju tijekom sortiranja blokova.
• Ugrađeni firmware favorizira Shell Sort za male skupove podataka gdje je rekurzija ograničena.

Prednosti i nedostaci Shell sortiranja

Shell Sort Complexity Analiza

Vremenska složenost shell sortiranja

Vremenska složenost Shell sortiranja ovisi o korištenom nizu praznina.

U najboljem slučaju, kada je niz već gotovo posložen, svaki prolaz zahtijeva samo logaritamski broj testova, što daje O(n log n).

U najgorem slučaju, niz je uređen tako da elementi trebaju maksimalan broj usporedbi, a konačni prirast dominira na O(n^2) s Shell-ovim originalnim nizom.

1. Složenost u najboljem slučaju: O(n log n)
2. Prosječna složenost slučaja: od O(n log n) do O(n^(4/3)) ovisno o nizu praznina
3. Složenost u najgorem slučaju: O(n^2) s Shellovim originalnim nizom

Najbolji niz opće namjene za gap je još uvijek otvoreno istraživačko pitanje, iako Sedgewickov i Ciura niz dobro funkcioniraju u praksi.

Shell Sort Space Complexity

Shell sortiranje ne zahtijeva pomoćne nizove, pa je prostorna složenost O(1) bez obzira na veličinu ulaza, što je jedna od njegovih najjačih praktičnih prednosti.

Pitanja i odgovori