Strutture dati - Unisci algoritmo di ordinamento

Merge sort è una tecnica di ordinamento basata sulla tecnica divide et impera. Poiché la complessità temporale nel caso peggiore è Ο (n log n), è uno degli algoritmi più rispettati.

Unisci ordinamento divide prima l'array in due metà uguali, quindi le combina in modo ordinato.

Come funziona Merge Sort?

Per comprendere l'ordinamento di tipo merge, prendiamo un array non ordinato come segue:

Sappiamo che l'unione dell'ordinamento divide prima l'intero array in modo iterativo in metà uguali a meno che non vengano raggiunti i valori atomici. Vediamo qui che un array di 8 elementi è diviso in due array di dimensione 4.

Ciò non modifica la sequenza di apparizione degli elementi nell'originale. Ora dividiamo questi due array a metà.

Dividiamo ulteriormente questi array e otteniamo un valore atomico che non può più essere diviso.

Ora, li combiniamo esattamente nello stesso modo in cui sono stati suddivisi. Si prega di notare i codici colore forniti a questi elenchi.

Per prima cosa confrontiamo l'elemento per ogni elenco e poi li combiniamo in un altro elenco in modo ordinato. Vediamo che 14 e 33 sono in posizioni ordinate. Confrontiamo 27 e 10 e nell'elenco di destinazione di 2 valori mettiamo prima 10, seguito da 27. Modifichiamo l'ordine di 19 e 35 mentre 42 e 44 sono posti in sequenza.

Nella successiva iterazione della fase di combinazione, confrontiamo elenchi di due valori di dati e li uniamo in un elenco di valori di dati trovati, posizionandoli tutti in un ordine ordinato.

Dopo la fusione finale, l'elenco dovrebbe apparire così:

Ora dovremmo imparare alcuni aspetti di programmazione del merge sorting.

Algoritmo

Unisci ordinamento continua a dividere l'elenco in metà uguali fino a quando non può più essere diviso. Per definizione, se è solo un elemento nell'elenco, viene ordinato. Quindi, unisci ordinamento combina gli elenchi ordinati più piccoli mantenendo ordinato anche il nuovo elenco.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Pseudocodice

Vedremo ora gli pseudocodici per le funzioni di merge sort. Come i nostri algoritmi sottolineano due funzioni principali: divide & unisci.

Merge sort funziona con la ricorsione e vedremo la nostra implementazione allo stesso modo.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

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