Shelli sortimise algoritm koos näitega

Mis on Shell Sort?

Shelli sortimine, mida nimetatakse ka Shelli meetodiks, on tõhus kohapealne võrdluspõhine sortimisalgoritm. See sai nime Donald Shelli järgi, kes selle idee 1959. aastal tutvustas, ning on üldistatud lisamissortimise laiendus, mis ületab selle ruutsortimise käitumise hajutatud andmete puhul.

Põhiidee on grupeerida üksteisest kaugel asuvad elemendid, sorteerida iga rühm lisamissortimise abil ja vähendada tühimikku samm-sammult, kuni see jõuab üheni. Selleks ajaks on massiiv peaaegu sorteeritud.

See tühik, intervall, järgib valitud järjestust, näiteks Shelli originaali, Knuthi, Hibbardi või Sedgewicki oma. Shelli originaal on n/2, n/4, ..., 1.

Shelli sortimise algoritm

Step 1) Initsialiseeri intervalli väärtus h = n/2, kus n on massiivi suurus.

Step 2) Paiguta kõik intervalli h piires olevad elemendid alamloendisse.

Step 3) Sorteeri iga alamloend lisamissortimise abil.

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

Step 5) Kui h > 0, minge tagasi 2. sammu juurde. Vastasel juhul minge 6. sammu juurde.

Step 6) Saadud massiiv on nüüd täielikult sorteeritud.

Kuidas Shelli sortimine töötab

Lisamissortimise puhul liiguvad elemendid korraga ainult ühe positsiooni võrra. Shell Sort jagab massiivi hoopis intervalli alusel laiali paigutatud alamloenditeks ja käivitab iga alamloendi puhul lisamissortimise.

Intervalli lühenedes alamloendi suurus kasvab. Kuna varasemad läbimised jätavad andmed osaliselt sorteerituks, nõuavad lühemad intervallid palju vähem vahetusi kui sisestamise sort nullist. Allolev joonis illustreerib ühte Shelli sortimise etappi.

Shelli sortimisalgoritmi toimimine näitega

Sorteerime allolevat massiivi Shell Sort'i abil.

Step 1) Massiivi suurus on 8, seega on intervalli algväärtus h = 8/2 = 4.

Step 2) Rühmita elemendid nelja positsiooni kaugusele. Alamloendid: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Step 3) Sorteeri iga alamloend lisamissortimise abil. Ajutine muutuja hoiab elementide nihkumise ajal väärtust, mis lisatakse. Pärast vahetusi näeb massiiv välja selline.

Step 4) Vähenda intervalli. Uus intervall on h = 4/2 = 2.

Step 5) Kuna 2 > 0, siis naaske 2. sammu juurde ja grupeerige elemendid kahe positsiooni kaugusele: {1, 5, 8, 7} ja {4, 2, 6, 3}.

Sorteeri esimene alamloend. Massiiv saab olema:

Pärast teise alamloendi sortimist:

Vähenda intervalli uuesti väärtuseni h = 2/2 = 1. Ühe tühimiku korral teostab Shell Sort kogu massiivi ulatuses viimase lisamissortimise, nagu allpool näidatud.

Step 6) Intervalli uuesti jagamine annab tulemuseks 0. Massiiv on nüüd täielikult sorteeritud:

pseudo-Code Shell Sort'i jaoks

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

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

Shell Sort esineb endiselt tänapäevastes süsteemides, kus on oluline pinu suurus või lihtsus.

• . Linux kernel kasutab Shell Sort'i kohtades, kus on oluline vältida väljakutsete pinu.
• uClibc sisseehitatud C-teek kasutab mälukasutuse madalal hoidmiseks kesta sortimist.
• bzip2 kasutab plokkide sortimise ajal sügava rekursiooni vältimiseks kesta sortimist.
• Sisseehitatud püsivara eelistab väikeste andmekogumite puhul, kus rekursioon on piiratud, kesta sortimist.

Shell Sort'i eelised ja puudused

Shelli sortimise keerukuse analüüs

Shelli sortimise ajaline keerukus

Shell Sort'i ajaline keerukus sõltub kasutatavast tühimike järjestusest.

Parimal juhul, kui massiiv on juba peaaegu korrastatud, vajab iga läbimine ainult logaritmilist arvu teste, andes tulemuseks O(n log n).

Halvimal juhul on massiiv paigutatud nii, et elemendid vajavad maksimaalset võrdlust ja lõplik juurdekasv domineerib O(n^2) juures Shelli algse järjestusega.

1. Parima juhtumi keerukus: O(n log n)
2. Keskmise juhtumi keerukus: O(n log n) kuni O(n^(4/3)), olenevalt tühikujadast
3. Halvima juhu keerukus: O(n^2) Shelli algse järjestusega

Parima üldotstarbelise tühimike järjestuse leidmine on endiselt lahtine uurimisküsimus, kuigi Sedgewicki ja Ciura järjestused toimivad praktikas hästi.

Shelli sortimise ruumi keerukus

Shell Sort ei vaja abimassiive, seega on ruumi keerukus O(1) olenemata sisendi suurusest, mis on selle üks tugevamaid praktilisi eeliseid.

KKK