Struttura dei dati e ordinamento di inserimento degli algoritmi

Questo è un algoritmo di ordinamento basato sul confronto sul posto. Qui viene mantenuto un sottoelenco che è sempre ordinato. Ad esempio, la parte inferiore di un array viene mantenuta per essere ordinata. Un elemento che deve essere "inserito" in questo sotto-elenco ordinato, deve trovare la sua posizione appropriata e quindi deve essere inserito lì. Da qui il nome,insertion sort.

L'array viene ricercato in sequenza e gli elementi non ordinati vengono spostati e inseriti nel sottoelenco ordinato (nello stesso array). Questo algoritmo non è adatto per set di dati di grandi dimensioni poiché la sua complessità media e peggiore è di Ο (n ² ), doven è il numero di elementi.

Come funziona l'ordinamento di inserzione?

Prendiamo un array non ordinato per il nostro esempio.

L'ordinamento di inserzione confronta i primi due elementi.

Si scopre che sia 14 che 33 sono già in ordine crescente. Per ora, 14 è in un sottoelenco ordinato.

L'ordinamento per inserzione va avanti e confronta 33 con 27.

E scopre che 33 non è nella posizione corretta.

Scambia 33 con 27. Controlla anche con tutti gli elementi della sotto-lista ordinata. Qui vediamo che il sottoelenco ordinato ha solo un elemento 14 e 27 è maggiore di 14. Quindi, il sottoelenco ordinato rimane ordinato dopo lo scambio.

Ormai abbiamo 14 e 27 nella sotto-lista ordinata. Successivamente, confronta 33 con 10.

Questi valori non sono in un ordine ordinato.

Quindi li scambiamo.

Tuttavia, lo scambio rende 27 e 10 non ordinati.

Quindi, li scambiamo anche.

Ancora una volta troviamo 14 e 10 in un ordine non ordinato.

Li scambiamo di nuovo. Alla fine della terza iterazione, abbiamo un sottoelenco ordinato di 4 elementi.

Questo processo continua fino a quando tutti i valori non ordinati sono coperti in un sottoelenco ordinato. Ora vedremo alcuni aspetti di programmazione dell'ordinamento per inserzione.

Algoritmo

Ora abbiamo un quadro più ampio di come funziona questa tecnica di ordinamento, quindi possiamo ricavare semplici passaggi da cui possiamo ottenere l'ordinamento per inserzione.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Pseudocodice

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

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