Algoritm de sortare Shell cu exemplu

Ce este sortarea Shell?

Sortarea prin shell, numită și metoda Shell, este un algoritm eficient de sortare bazat pe comparații in-place. Numit după Donald Shell, care a introdus ideea în 1959, este o extensie generalizată a sortării prin inserție care depășește comportamentul său pătratic pe date împrăștiate.

Ideea fundamentală este de a grupa elementele care sunt depărtate, de a sorta fiecare grup folosind sortarea prin inserție și de a micșora spațiul pas cu pas până ajunge la unu. Până atunci, matricea este aproape sortată.

Acest interval, respectiv intervalul, urmează o secvență aleasă, cum ar fi originalul lui Shell, al lui Knuth, al lui Hibbard sau al lui Sedgewick. Originalul lui Shell este n/2, n/4, ..., 1.

Algoritmul de sortare Shell

Pas 1) Inițializați valoarea intervalului h = n/2, unde n este dimensiunea matricei.

Pas 2) Plasați toate elementele aflate la o distanță de intervalul h într-o sublistă.

Pas 3) Sortați fiecare sublistă folosind sortarea prin inserție.

Pas 4) Setați un nou interval h = h/2.

Pas 5) Dacă h > 0, reveniți la Pasul 2. În caz contrar, treceți la Pasul 6.

Pas 6) Matricea rezultată este acum complet sortată.

Cum funcționează sortarea Shell

În sortarea prin inserție, elementele se mișcă doar cu o poziție la un moment dat. Sortarea prin shell împarte în schimb matricea în subliste distanțate larg pe baza intervalului și rulează sortarea prin inserție pe fiecare sublistă.

Pe măsură ce intervalul se micșorează, dimensiunea sublistei crește. Deoarece trecerile anterioare lasă datele parțial sortate, intervalele mai mici necesită mult mai puține schimbări decât rularea sortare inserție de la zero. Figura de mai jos ilustrează o pasă de sortare Shell.

Funcționarea algoritmului de sortare Shell cu exemplu

Să sortăm matricea de mai jos folosind sortarea Shell.

Pas 1) Dimensiunea matricei este 8, deci valoarea intervalului inițial este h = 8/2 = 4.

Pas 2) Grupează elementele la patru poziții distanță. Subliste: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Pas 3) Sortează fiecare sublistă folosind sortarea prin inserție. O variabilă temporară reține valoarea plasată în timp ce elementele se deplasează. După schimbări, matricea arată astfel.

Pas 4) Micșorează intervalul. Noul interval este h = 4/2 = 2.

Pas 5) Deoarece 2 > 0, reveniți la Pasul 2 și grupați elementele la două poziții distanță: {1, 5, 8, 7} și {4, 2, 6, 3}.

Sortează prima sublistă. Tabloul devine:

După sortarea celei de-a doua subliste:

Micșorați din nou intervalul la h = 2/2 = 1. Cu un interval de unu, Shell Sort execută o pasă finală de sortare prin inserție asupra întregului array, așa cum se arată mai jos.

Pas 6) Împărțirea din nou a intervalului dă 0. Tabloul este acum complet sortat:

Pseudo-Code pentru sortare Shell

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

Program de sortare Shell în C/C++

Intrare:

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

ieșire:

Sorted Output:

1 2 3 4 5 6 7 8

Exemplu de sortare Shell în Python

Intrare:

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

ieșire:

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

Aplicații ale sortării Shell

Sortarea Shell apare încă în sistemele moderne unde spațiul stivei sau simplitatea contează.

• Linux kernel folosește sortarea Shell în locurile în care evitarea unei stive de apeluri este importantă.
• Biblioteca C încorporată uClibc folosește sortarea Shell pentru a menține utilizarea memoriei la un nivel scăzut.
• bzip2 folosește sortarea prin Shell pentru a evita recursivitatea profundă în timpul sortării pe blocuri.
• Firmware-ul încorporat favorizează sortarea Shell pentru seturi de date mici unde recursivitatea este restricționată.

Avantajele și dezavantajele sortării Shell

Analiza complexității sortării Shell

Complexitatea timpului a sortării Shell

Complexitatea temporală a sortării Shell depinde de secvența de gap-uri utilizată.

În cel mai bun caz, când matricea este deja aproape aranjată, fiecare trecere necesită doar un număr logaritmic de teste, rezultând O(n log n).

În cel mai rău caz, matricea este aranjată astfel încât elementele să necesite comparații maxime, iar incrementul final domină la O(n^2) cu secvența originală a Shell.

1. Complexitatea în cel mai bun caz: O(n log n)
2. Complexitatea medie a cazurilor: O(n log n) până la O(n^(4/3)) în funcție de secvența de gap-uri
3. Complexitatea în cel mai rău caz: O(n^2) cu secvența originală a lui Shell

Cea mai bună secvență de gap-uri de uz general este încă o întrebare de cercetare deschisă, deși secvențele Sedgewick și Ciura performează bine în practică.

Complexitatea spațiului de sortare a carcasei

Sortarea în shell nu necesită tablouri auxiliare, deci complexitatea spațiului este O(1) indiferent de dimensiunea intrării, acesta fiind unul dintre cele mai puternice avantaje practice ale sale.

Întrebări frecvente