Struttura dei dati e algoritmi - Ordinamento shell

L'ordinamento della shell è un algoritmo di ordinamento altamente efficiente e si basa su un algoritmo di ordinamento per inserzione. Questo algoritmo evita grandi spostamenti come nel caso dell'ordinamento per inserzione, se il valore più piccolo si trova all'estrema destra e deve essere spostato all'estrema sinistra.

Questo algoritmo utilizza l'ordinamento per inserzione su elementi ampiamente distribuiti, prima per ordinarli e poi ordina gli elementi meno distanziati. Questa spaziatura è definita comeinterval. Questo intervallo è calcolato in base alla formula di Knuth come -

Formula di Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

Questo algoritmo è abbastanza efficiente per insiemi di dati di medie dimensioni poiché la sua complessità media e nel caso peggiore di questo algoritmo dipende dalla sequenza di gap la più nota è Ο (n), dove n è il numero di elementi. E il caso peggiore della complessità spaziale è O (n).

Come funziona l'ordinamento della shell?

Consideriamo il seguente esempio per avere un'idea di come funziona l'ordinamento della shell. Prendiamo lo stesso array che abbiamo usato nei nostri esempi precedenti. Per il nostro esempio e per la nostra facilità di comprensione, prendiamo l'intervallo di 4. Crea una sottoelenco virtuale di tutti i valori situati nell'intervallo di 4 posizioni. Questi valori sono {35, 14}, {33, 19}, {42, 27} e {10, 44}

Confrontiamo i valori in ogni sottoelenco e li scambiamo (se necessario) nell'array originale. Dopo questo passaggio, il nuovo array dovrebbe apparire così:

Quindi, prendiamo un intervallo di 1 e questo intervallo genera due sottoelenchi: {14, 27, 35, 42}, {19, 10, 33, 44}

Confrontiamo e scambiamo i valori, se necessario, nell'array originale. Dopo questo passaggio, l'array dovrebbe apparire così:

Infine, ordiniamo il resto dell'array utilizzando l'intervallo di valore 1. L'ordinamento della shell utilizza l'ordinamento per inserimento per ordinare l'array.

Di seguito è riportata la descrizione dettagliata:

Vediamo che sono stati necessari solo quattro scambi per ordinare il resto dell'array.

Algoritmo

Di seguito è riportato l'algoritmo per l'ordinamento della shell.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

Pseudocodice

Di seguito è riportato lo pseudocodice per l'ordinamento della shell.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

Per conoscere l'implementazione dell'ordinamento della shell nel linguaggio di programmazione C, fare clic qui .