Algoritmo di ordinamento della shell con ESEMPIO
Sara Chen
Che cos'è l'ordinamento della shell
Il metodo di Shell, o Shell sort in Data Structure, è un efficiente algoritmo di ordinamento per confronto sul posto. Prende il nome da Donald Shell quando propose l'idea iniziale nel 1959. Lo Shell sort è un'estensione generalizzata dell'algoritmo di ordinamento per inserzione.
L'idea fondamentale di questo algoritmo di ordinamento è di raggruppare gli elementi che sono distanti e ordinarli di conseguenza. Quindi ridurre gradualmente lo spazio tra di loro. Shell sort supera la complessità media del tempo del caso di insert sort confrontando e scambiando elementi che sono distanti.
Questo gap, noto come intervallo, viene ridotto secondo alcune sequenze di gap ottimali. Anche il tempo di esecuzione dello shell sort dipende da queste sequenze. Esistono diverse sequenze di gap, come la sequenza originale di Shell, la formula di Knuth, gli incrementi di Hibbard, ecc. La sequenza di gap originale di Shell è: n/2, n/4, n/8, ……….1
Algoritmo di ordinamento della shell
I passaggi o la procedura per l'algoritmo di ordinamento della shell sono i seguenti:
Passo 1) Inizializzare il valore dell'intervallo, h = n/2. (In questo esempio, n è la dimensione dell'array)
Passo 2) Metti tutti gli elementi entro una distanza dall'intervallo h in una sottolista.
Passo 3) Ordina questi sottoelenchi utilizzando l'ordinamento per inserzione.
Passo 4) Imposta un nuovo intervallo, h=h/2.
Passo 5) Se h>0, andare al passo 2. Altrimenti andare al passo 6.
Passo 6) L'output risultante sarà l'array ordinato.
Come funziona l'ordinamento della shell
Nell'ordinamento per inserimento, gli elementi vengono spostati solo di una posizione alla volta. Al contrario, lo shell sort divide l'array in parti più piccole in base al valore dell'intervallo ed esegue l'ordinamento per inserzione su tali parti.
Gradualmente, il valore dell'intervallo diminuisce e la dimensione dei pezzi divisi aumenta. Poiché i pezzi vengono ordinati individualmente in anticipo, unirli richiede meno passaggi rispetto al file ordinamento per inserzione.
La GIF seguente mostra una dimostrazione di shell sort. In questa demo, il valore rosso e quello blu indicati vengono confrontati e scambiati in base all'ordinamento per inserimento. Quindi l'intervallo diminuisce e shell sort avvia l'ordinamento per inserimento in quei dati quasi ordinati.
Funzionamento dell'algoritmo Shell Sort
Vediamo un esempio seguente di un algoritmo di ordinamento shell. In questo esempio, ordineremo il seguente array usando l'ordinamento shell:
Passo 1) Qui, la dimensione dell'array è 8. Pertanto, il valore dell'intervallo sarà h = 8/2 o 4.
Passo 2) Ora memorizzeremo tutti gli elementi a una distanza di 4. Nel nostro caso, le sottoliste sono: {8, 1}, {6, 4}, {7, 5}, {2, 3}.
Passo 3) Ora, questi sottoelenchi verranno ordinati utilizzando l'ordinamento per inserzione, in cui viene utilizzata una variabile temporanea per confrontare entrambi i numeri e ordinarli di conseguenza.
L'array sarebbe simile al seguente dopo le operazioni di scambio:
Passo 4) Ora diminuiremo il valore iniziale dell'intervallo. Il nuovo intervallo sarà h=h/2 o 4/2 o 2.
Passo 5) Poiché 2>0, andremo al passaggio 2 per memorizzare tutti gli elementi a una distanza di 2. Per questa volta, le sottoliste sono:
{1, 5, 8, 7}, {4, 2, 6, 3}
Quindi queste sottoliste saranno ordinate usando l'ordinamento per inserimento. Dopo aver confrontato e scambiato la prima sottoliste, l'array sarà il seguente.
Dopo aver ordinato la seconda sottolista, l'array originale sarà:
Poi di nuovo, l'intervallo verrà ridotto. Ora l'intervallo sarà h=h/2 o 2/1 o 1. Quindi utilizzeremo l'algoritmo di ordinamento per inserimento per ordinare l'array modificato.
Di seguito è riportata la descrizione dettagliata della procedura di ordinamento per inserimento.
L'intervallo viene nuovamente diviso per 2. A questo punto l'intervallo diventa 0. Quindi andiamo al passaggio 6.
Passo 6) Poiché l'intervallo è 0, l'array viene ordinato in base a questo tempo. L'array ordinato è-
Pseudo-codice
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
Programma di ordinamento della shell in C/C++
Ingresso:
//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";
}
Produzione:
Sorted Output: 1 2 3 4 5 6 7 8
Esempio di ordinamento della shell in Python
Ingresso:
#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)
Produzione:
Sorted Output: [1, 2, 3, 4, 5, 6, 7, 8]
Applicazioni di Shell Sort
Ecco alcune importanti applicazioni di Shell Sort:
- L'ordinamento della shell viene utilizzato in Kernel Linux perché non utilizza uno stack di chiamate.
- La libreria uClibc utilizza l'ordinamento Shell.
- Il compressore bzip2 utilizza l'ordinamento Shell per interrompere la ricorsione eccedente.
Vantaggi e svantaggi di Shell Sort
| Vantaggi | Svantaggi |
|---|---|
| Non è richiesta alcuna chiamata allo stack. | Non efficiente per array di dimensioni enormi. |
| Facile implementazione. | Inefficiente per elementi ampiamente diffusi. |
| Efficiente per elementi meno distanziati. |
Analisi della complessità di Shell Sort
Complessità temporale dell'ordinamento Shell
La complessità temporale dell'algoritmo di ordinamento shell è O(n^2). Il ragionamento è il seguente:
Per lo scenario migliore, la quantità totale di test per tutti gli intervalli quando l'array era stato precedentemente organizzato è uguale a log n. Quindi la complessità sarebbe O(n*log n).
Per lo scenario peggiore, consideriamo che l'array sia costituito in modo tale che gli elementi richiedano il maggior numero di confronti. Quindi tutti gli elementi non verranno confrontati e scambiati fino all'ultima iterazione. Pertanto, il totale dei confronti richiesti per l'incremento finale è O(n^2).
In conclusione, le complessità temporali sarebbero
- Migliore complessità del caso: O(n*log n)
- Complessità media del caso: O(n*log n)
- Complessità del caso peggiore: O(n^2)
La complessità del tempo di esecuzione di shell sort dipende in larga misura dalle sequenze di incremento gap utilizzate. Tuttavia, la migliore sequenza di incremento per shell sort è ancora sconosciuta.
Complessità dello spazio di ordinamento delle shell
In questo ordinamento per confronto, non abbiamo bisogno di alcuno spazio ausiliario aggiuntivo. Quindi la complessità spaziale di questo tipo di algoritmo è O(1).
