Shell Sort

In questo tutorial imparerai come funziona l'ordinamento della shell. Inoltre, troverai esempi funzionanti di ordinamento shell in C, C ++, Java e Python.

L'ordinamento della shell è un algoritmo che prima ordina gli elementi molto distanti l'uno dall'altro e successivamente riduce l'intervallo tra gli elementi da ordinare. È una versione generalizzata dell'ordinamento per inserzione.

Nell'ordinamento della shell, vengono ordinati gli elementi a un intervallo specifico. L'intervallo tra gli elementi viene gradualmente ridotto in base alla sequenza utilizzata. Le prestazioni dell'ordinamento della shell dipendono dal tipo di sequenza utilizzata per un dato array di input.

Alcune delle sequenze ottimali utilizzate sono:

• Sequenza originale di Shell: N/2 , N/4 ,… , 1
• Gli incrementi di Knuth: 1, 4, 13,… , (3k - 1) / 2
• Gli incrementi di Sedgewick: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
• Gli incrementi di Hibbard: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• Incremento di Papernov e Stasevich: 1, 3, 5, 9, 17, 33, 65,…
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Come funziona l'ordinamento della shell?

1. Supponiamo di dover ordinare il seguente array. Matrice iniziale
2. Stiamo usando la sequenza originale della shell (N/2, N/4,… 1) come intervalli nel nostro algoritmo.
   Nel primo ciclo, se la dimensione dell'array è N = 8allora, gli elementi che si trovano nell'intervallo di N/2 = 4vengono confrontati e scambiati se non sono in ordine.
   1. Lo 0 ° elemento viene confrontato con il 4 ° elemento.
   2. Se lo 0 ° elemento è maggiore del 4 °, il 4 ° elemento viene prima memorizzato in tempvariabile e l' 0thelemento (cioè l'elemento maggiore) viene memorizzato nella 4thposizione e l'elemento memorizzato in tempviene memorizzato nella 0thposizione. Riorganizzare gli elementi con un intervallo n / 2
      Questo processo continua per tutti gli elementi rimanenti. Riorganizza tutti gli elementi con un intervallo n / 2
3. Nel secondo ciclo, N/4 = 8/4 = 2viene preso un intervallo di e di nuovo gli elementi che si trovano a questi intervalli vengono ordinati. Riorganizza gli elementi con un intervallo n / 4
   A questo punto potresti confonderti. Vengono confrontati tutti gli elementi dell'array che si trovano nell'intervallo corrente.
   Gli elementi in 4a e 2ndposizione vengono confrontati. Vengono confrontati anche gli elementi in seconda e 0thposizione. Vengono confrontati tutti gli elementi dell'array che si trovano nell'intervallo corrente.
4. Lo stesso processo va avanti per gli elementi rimanenti. Riorganizza tutti gli elementi con un intervallo n / 4
5. Infine, quando l'intervallo è, N/8 = 8/8 =1gli elementi dell'array che si trovano nell'intervallo 1 vengono ordinati. L'array è ora completamente ordinato. Riorganizza gli elementi con un intervallo n / 8

Algoritmo di ordinamento della shell

 shellSort (array, size) per intervallo i <- size / 2n fino a 1 per ogni intervallo "i" nell'array ordina tutti gli elementi all'intervallo "i" end shellSort

Esempi di Python, Java e C / C ++

Python Java C C ++

# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)

// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 

// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 

// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); ) 

Complessità

L'ordinamento della shell è un algoritmo di ordinamento instabile perché questo algoritmo non esamina gli elementi che si trovano tra gli intervalli.

Complessità temporale

• Complessità del caso peggiore : minore o uguale a La complessità del caso peggiore per l'ordinamento della shell è sempre minore o uguale a . Secondo Poonen Teorema, caso peggiore complessità per le coperture di tipo è o o o qualcosa tra.O(n2)
O(n2)
Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
• Complessità caso migliore : O(n*log n)
  quando l'array è già ordinato, il numero totale di confronti per ogni intervallo (o incremento) è uguale alla dimensione dell'array.
• Complessità media dei casi : O(n*log n)
  è intorno .O(n1.25)

La complessità dipende dall'intervallo scelto. Le complessità di cui sopra differiscono per le diverse sequenze di incremento scelte. La migliore sequenza di incremento è sconosciuta.

Complessità spaziale:

La complessità dello spazio per l'ordinamento della shell è O(1).

Applicazioni di ordinamento shell

L'ordinamento della shell viene utilizzato quando:

• chiamare uno stack è un sovraccarico. La libreria uClibc usa questo tipo.
• la ricorsione supera un limite. bzip2 compressor lo usa.
• L'ordinamento per inserzione non funziona bene quando gli elementi di chiusura sono molto distanti. L'ordinamento della shell aiuta a ridurre la distanza tra gli elementi vicini. Pertanto, il numero di scambi da eseguire sarà inferiore.