Gruntle Software & Testing

Ordinamento per inserimento in C++ con esempi

Di Stewart TristianPubblicato il Pubblicato in Guide

Uno sguardo approfondito all'ordinamento per inserzione con esempi classici.

L'ordinamento a inserzione è una tecnica di ordinamento che può essere vista come un gioco di carte. Come inseriamo o rimuoviamo una carta in un mazzo, l'ordinamento a inserzione funziona in modo simile.

La tecnica dell'algoritmo Insertion sort è più efficiente delle tecniche Bubble sort e Selection sort, ma è meno efficiente di altre tecniche come Quicksort e Merge sort.

Panoramica

Nella tecnica dell'ordinamento per inserzione, si parte dal secondo elemento, lo si confronta con il primo e lo si colloca in una posizione adeguata. Poi si esegue questo processo per gli elementi successivi.

Confrontiamo ogni elemento con tutti gli elementi precedenti e mettiamo o inseriamo l'elemento nella sua posizione corretta. La tecnica dell'ordinamento per inserzione è più praticabile per gli array con un numero minore di elementi ed è utile anche per l'ordinamento di elenchi collegati.

Gli elenchi collegati hanno un puntatore all'elemento successivo (nel caso di un elenco collegato singolarmente) e un puntatore all'elemento precedente (nel caso di un elenco collegato doppiamente). Di conseguenza, diventa più facile implementare l'ordinamento di inserimento per un elenco collegato.

In questa esercitazione analizziamo l'ordinamento di inserimento.

Algoritmo generale

Passo 1 Ripetere i passaggi da 2 a 5 per K = da 1 a N-1.

Passo 2 : set temp = A[K]

Passo 3 : impostare J = K - 1

Passo 4 : Ripetere mentre temp <=A[J]

impostare A[J + 1] = A[J]

impostare J = J - 1

[fine del ciclo interno]

Passo 5 : impostare A[J + 1] = temp

[fine del ciclo]

Passo 6 : uscita

Pertanto, nella tecnica di ordinamento a inserimento, si parte dal secondo elemento, poiché si presuppone che il primo elemento sia sempre ordinato. Poi, dal secondo all'ultimo elemento, si confronta ogni elemento con tutti gli elementi precedenti e lo si colloca nella posizione corretta.

Pseudocodice

Di seguito è riportato il codice pseudo per l'ordinamento di inserimento. 

 procedura insertionSort(array,N ) array - array da ordinare N- numero di elementi begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //localizzare la posizione libera per inserire l'elemento whilefreePosition> 0 and array[freePosition -1]>insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //inserire l'elementonumero in posizione libera array [freePosition] = insert_val fine per fine procedura

Il codice pseudocodice per l'ordinamento per inserzione è riportato qui sopra, mentre l'esempio seguente illustra questa tecnica.

Illustrazione

L'array da ordinare è il seguente:

Ora, per ogni passaggio, si confronta l'elemento corrente con tutti gli elementi precedenti. Quindi, nel primo passaggio, si inizia con il secondo elemento.

Pertanto, sono necessari N passaggi per ordinare completamente un array contenente N elementi.

L'illustrazione precedente può essere riassunta in forma tabellare:

Passo Elenco non ordinato confronto Elenco ordinato
1 {12,3,5,10,8,1} {12,3} {3,12,5,10,8,1}
2 {3,12,5,10,8,1} {3,12,5} {3,5,12,10,8,1}
3 {3,5,12,10,8,1} {3,5,12,10} {3,5,10,12,8,1}
4 {3,5,10,12,8,1} {3,5,10,12,8} {3,5,8,10,12,1}
5 {3,5,8,10,12,1} {3,5,8,10,12,1} {1,3,5,8,10,12}
6 {} {} {1,3,5,8,10,12}

Come mostrato nell'illustrazione precedente, si inizia con il secondo elemento, poiché si presuppone che il primo elemento sia sempre ordinato. Si inizia quindi con il confronto del secondo elemento con il primo e si scambia la posizione se il secondo elemento è inferiore al primo.

Questo processo di confronto e scambio posiziona i due elementi al posto giusto. Successivamente, si confronta il terzo elemento con gli elementi precedenti (primo e secondo) e si esegue la stessa procedura per posizionare il terzo elemento al posto giusto.

In questo modo, per ogni passaggio, si colloca un elemento al suo posto. Per il primo passaggio, si colloca il secondo elemento al suo posto. In generale, quindi, per collocare N elementi al loro posto, occorrono N-1 passaggi.

Successivamente, dimostreremo l'implementazione della tecnica di ordinamento per inserzione in linguaggio C++.

Esempio di C++ 

 #include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<"\nLista di input è \n"; for(int i=0;i<10;i++) { cout < ="" 
 Uscita: 
 L'elenco degli ingressi è 
 12 4 3 1 15 45 33 21 10 2 
 L'elenco ordinato è 
 1 2 3 4 10 12 15 21 33 45 
 Vediamo quindi l'implementazione Java della tecnica di ordinamento Insertion. 
 Esempio Java 
 public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Inserimento lista elementi..."); for(int i=0;i<10;i++) { System.out.print(myarray[i] + " "); } for(int k=1; k=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println("Ordinamento lista elementi..."); for(inti=0;i<10;i++) { System.out.print(myarray[i] + " "); } } } } 
 Uscita: 
 Elenco di elementi in ingresso ... 
 12 4 3 1 15 45 33 21 10 2 
 elenco ordinato di elementi ... 
 1 2 3 4 10 12 15 21 33 45 
 In entrambe le implementazioni, possiamo vedere che iniziamo l'ordinamento dal secondo elemento dell'array (variabile del ciclo j = 1) e confrontiamo ripetutamente l'elemento corrente con tutti gli elementi precedenti e quindi ordiniamo l'elemento per collocarlo nella posizione corretta se l'elemento corrente non è in ordine con tutti gli elementi precedenti. 
 L'ordinamento per inserzione è quello che funziona meglio e può essere completato in un minor numero di passaggi se l'array è parzialmente ordinato, ma quando l'elenco diventa più grande, le sue prestazioni diminuiscono. Un altro vantaggio dell'ordinamento per inserzione è che si tratta di un ordinamento stabile, il che significa che mantiene l'ordine degli elementi uguali nell'elenco. 
 Analisi della complessità dell'algoritmo di ordinamento per inserzione 
 Dallo pseudo-codice e dall'illustrazione precedente, l'ordinamento per inserzione è l'algoritmo più efficiente rispetto all'ordinamento a bolle o all'ordinamento per selezione. Invece di utilizzare il ciclo for e le condizioni presenti, utilizza un ciclo while che non esegue ulteriori passaggi quando l'array è ordinato. 
 Tuttavia, anche se passiamo l'array ordinato alla tecnica di ordinamento per inserzione, questa eseguirà comunque il ciclo for esterno, richiedendo quindi un numero n di passi per ordinare un array già ordinato. Questo rende la migliore complessità temporale dell'ordinamento per inserzione una funzione lineare di N, dove N è il numero di elementi dell'array. 
 Di seguito sono riportate le varie complessità della tecnica Insertion sort: 
 Complessità temporale nel caso peggiore  O(n 2 ) 
 Complessità temporale del caso migliore  O(n) 
 Complessità temporale media  O(n 2 ) 
 Complessità dello spazio  O(1) 
 Nonostante queste complessità, possiamo comunque concludere che l'Insertion sort è l'algoritmo più efficiente rispetto ad altre tecniche di ordinamento come il Bubble sort e il Selection sort. 
 Conclusione 
 L'ordinamento per inserzione è la più efficiente tra le tre tecniche discusse finora. In questo caso, si assume che il primo elemento sia ordinato e si confronta ripetutamente ogni elemento con tutti gli elementi precedenti, per poi collocare l'elemento corrente nella sua posizione corretta nell'array. 
 In questa esercitazione, discutendo l'ordinamento per inserzione, abbiamo notato che gli elementi vengono confrontati con un incremento di 1 e sono contigui. Questa caratteristica richiede più passaggi per ottenere l'elenco ordinato. 
 Nel prossimo tutorial parleremo dell'"ordinamento a conchiglia", che è un miglioramento dell'ordinamento a selezione. 
 Nell'ordinamento a conchiglia si introduce una variabile nota come "incremento" o "divario" con la quale si divide l'elenco in sottoelenchi contenenti elementi non contigui che si "divaricano" l'uno dall'altro. L'ordinamento a conchiglia richiede meno passaggi rispetto all'ordinamento a inserzione ed è anche più veloce. 
 Nelle prossime esercitazioni impareremo a conoscere due tecniche di ordinamento, "Quicksort" e "Mergesort", che utilizzano la strategia "Divide et impera" per ordinare gli elenchi di dati.
Scorri verso l'alto