Algoritm de sortare Shell cu EXEMPLU

Ce este Shell Sort

Metoda lui Shell, sau sortarea Shell în structura de date, este un algoritm eficient de sortare de comparație la loc. Este numit după Donald Shell când a propus ideea inițială în 1959. Sortarea Shell este o extensie generalizată a algoritmului de sortare prin inserție.

Ideea fundamentală a acestui algoritm de sortare este de a grupa elementele care sunt îndepărtate și de a le sorta în consecință. Apoi reduceți treptat distanța dintre ele. Sortarea Shell depășește complexitatea medie a timpului de caz a sortării prin inserție prin compararea și schimbul de elemente aflate la distanță.

Acest interval, cunoscut sub numele de interval, este redus în funcție de unele secvențe de decalaj optime. Timpul de rulare a sortării shell depinde, de asemenea, de aceste secvențe. Există mai multe secvențe de decalaje, cum ar fi secvența originală a lui Shell, formula lui Knuth, incrementele lui Hibbard etc. Secvența de decalaj inițială a lui Shell este - n/2, n/4, n/8, ……….1

Algoritmul de sortare Shell

Pașii sau procedura pentru algoritmul de sortare shell sunt următorii:

Pas 1) Inițializați valoarea intervalului, h = n/2. (În acest exemplu, n este dimensiunea matricei)

Pas 2) Puneți toate elementele la o distanță de intervalul h într-o sub-listă.

Pas 3) Sortați acele subliste folosind sortarea prin inserare.

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

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

Pas 6) Ieșirea rezultată va fi matricea sortată.

Cum funcționează sortarea Shell

În sortarea prin inserare, elementele sunt mutate doar cu o singură poziție la un moment dat. Dimpotrivă, sortarea shell împarte matricea în bucăți mai mici pe baza valorii intervalului și execută sortarea prin inserție pe acele piese.

Treptat, valoarea intervalului scade, iar dimensiunea pieselor divizate crește. Deoarece piesele sunt sortate individual în prealabil, îmbinarea acelor piese necesită mai puțini pași decât sortare inserție.

Următorul GIF arată o demonstrație a sortării shell-ului. În această demonstrație, valoarea indicată roșu și albastru este comparată și schimbată în funcție de sortarea inserției. Apoi intervalul scade și sortarea shell inițiază sortarea prin inserare în acele date aproape sortate.

Funcționarea algoritmului de sortare Shell

Să vedem următorul exemplu de algoritm de sortare shell. În acest exemplu, vom sorta următoarea matrice folosind sortarea shell:

Pas 1) Aici, dimensiunea matricei este 8. Astfel, valoarea intervalului va fi h = 8/2 sau 4.

Pas 2) Acum, vom stoca toate elementele la o distanță de 4. Pentru cazul nostru, sublistele sunt- {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Pas 3) Acum, acele subliste vor fi sortate folosind sortarea prin inserare, unde o variabilă temporară este folosită pentru a compara ambele numere și pentru a sorta în consecință.

Matricea ar fi așa după operațiunile de schimbare:

Pas 4) Acum, vom scădea valoarea inițială a intervalului. Noul interval va fi h=h/2 sau 4/2 sau 2.

Pas 5) Ca 2>0, vom merge la pasul 2 pentru a stoca toate elementele la o distanță de 2. Pentru acest timp, sublistele sunt-

{1, 5, 8, 7}, {4, 2, 6, 3}

Apoi aceste subliste vor fi sortate folosind sortarea prin inserare. După compararea și schimbarea primei subliste, matricea ar fi următoarea.

După sortarea celei de-a doua subliste, matricea originală va fi:

Apoi, din nou, intervalul va fi redus. Acum intervalul va fi h=h/2 sau 2/1 sau 1. Prin urmare, vom folosi algoritmul de sortare prin inserare pentru a sorta tabloul modificat.

Următoarea este o descriere procedurală pas cu pas a sortării prin inserare.

Intervalul este din nou împărțit la 2. Până în acest moment, intervalul devine 0. Deci trecem la pasul 6.

Pas 6) Întrucât intervalul este 0, matricea este sortată după acest timp. Matricea sortată este...

Pseudo cod

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

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

Iată aplicații importante ale Shell Sort:

• sortarea Shell este folosită în Linux kernel deoarece nu folosește o stivă de apeluri.
• Biblioteca uClibc folosește sortarea Shell.
• Compresorul bzip2 folosește sortarea Shell pentru a opri depășirea recursiunii.

Avantaje și dezavantaje ale sortării Shell

Avantaje	Dezavantaje
Nu este necesar niciun apel de stivă.	Nu este eficient pentru matrice de dimensiuni mari.
Implementare ușoară.	Ineficient pentru elementele larg răspândite.
Eficient pentru elementele mai puțin distanțate.

Analiza complexității sortării Shell

Complexitatea timpului a sortării Shell

Complexitatea temporală a algoritmului de sortare shell este O(n^2). Raționamentul este următorul:

Pentru cel mai bun scenariu, cantitatea totală de teste pentru toate intervalele când matricea a fost aranjată anterior este egală cu log n. Astfel, complexitatea ar fi O(n*log n).

Pentru cel mai rău caz, să considerăm că tabloul constă în așa fel încât elementele necesită cel mai mare număr de comparații. Apoi, toate elementele nu vor fi comparate și comutate până la ultima iterație. Prin urmare, comparațiile totale necesare pentru incrementul final este O(n^2).

În concluzie, complexitățile de timp ar fi

1. Cel mai bun caz de complexitate: O(n*log n)
2. Complexitatea medie a cazului: O(n*log n)
3. Complexitatea celui mai rău caz: O(n^2)

Complexitatea timpului de rulare a sortării shell depinde în mare măsură de secvențele de incrementare a intervalului utilizate. Cu toate acestea, cea mai bună secvență de increment pentru sortarea shell este încă necunoscută.

Complexitatea spațiului de sortare a carcasei

În acest tip de comparație, nu avem nevoie de spațiu suplimentar suplimentar. Astfel, complexitatea spațială a acestui tip de algoritm este O(1).