Insertion sort in C++

In questa lezione affronteremo l’insertion sort in C++, un algoritmo di ordinamento che utilizza un metodo molto simile a quello usato da un essere umano per ordinare un mazzo di carte.

L’algoritmo di ordinamento insertion sort è molto semplice da implementare e non utilizza un array di appoggio, è dunque un algoritmo in place. In questo modo si risparmia memoria.

L’algoritmo utilizza due indici, ad esempio i e j, dove i punta al secondo elemento, mentre j punta al primo.

Quindi, per un ordinamento crescente, si confrontano i due elementi e se l’elemento puntato dall’indice j è maggiore dell’elemento puntato dall’indice i si scambiano, altrimenti l’indice avanza.

Il procedimento si ripete finché non si trova la posizione dove inserire l’elemento. In questo modo gli elementi maggiori vengono spostati verso destra.

Se volessimo ordinare l’array in ordine decrescente, dovremmo agire in maniera opposta.


Esempio funzionamento insertion sort

Facciamo subito un esempio per capire la logica di funzionamento.

Partiamo dunque da un array con questi elementi:

6 2 4 9 1 8

Innanzitutto si confronta il 6 con 2, dato che 6 è maggiore di 2 si sposta il 6 e si procede all’inserimento del 2.
Primo passaggio: 2 6 4 9 1 8


Adesso si confronta 6 con 4, dato che 6 è maggiore di 4 si dovrebbero scambiare ma prima dobbiamo confrontare il 4 anche con il 2. Dato che 2 non è maggiore di 4 si può scambiare la posizione del 6 con quella del 4.
Secondo passaggio: 2 4 6 9 1 8


Dopo viene confrontato 6 con 9, dato che 6 non è maggiore di 9 non si fa nulla, si incrementa solo l’indice.
Terzo passaggio: 2 4 6 9 1 8


Poi si confronta 9 con 1, dato che 9 è maggiore di 1 si continua a confrontare 1 con gli altri elementi. Quindi, in questo caso essendo tutti maggiori, si sposteranno verso destra lasciando libera la prima posizione dove poter inserire l’elemento.
Quarto passaggio: 1 2 4 6 9 8


Infine si confronta il 9 con il 8, dato che è superiore si procede a confrontare il numero 8 con il 4, ma essendo superiore scambiamo il 9 con il numero 8.
Quarto passaggio: 1 2 4 6 8 9


Sviluppo insertion sort in C++

Per realizzare l’algoritmo chiediamo innanzitutto di inizializzare un array a[] con i valori inseriti da tastiera.

Dopo, per l’ordinamento, si utilizza un ciclo esterno con indice i che parte da 1 e una variabile temporanea temp nella quale memorizziamo il secondo valore (a[1]). L’indice j parte da 0.

Quindi inizialmente i punta al secondo elemento mentre j punta al primo. Dopo utilizziamo il while che si ripete finché è vera questa condizione: il valore puntato dall’indice j è maggiore di temp e j>=0.

All’interno del while memorizziamo il valore puntato dall’indice j nella posizione successiva a j e decrementiamo j di 1.

Quando si finisce il ciclo più interno (while) allora nella posizione j+1 memorizziamo il valore di temp.

Continuiamo finché si verifica questa condizione: i<n.

Ecco il listato completo dell’insertion sort in C++.

#include<iostream>
using namespace std;

#define MAX 10 

int main() { 
	int n, a[MAX], i, j, temp; 
	
	cout<<"Quanti elementi?: "; 
	cin>>n; 
	
	for(i=0;i<n;i++) {
		cout<<"Elemento numero "<<i+1<<": "; 
		cin>>a[i]; 
	}
	
	cout<<"Ordiniamo l'array \n"; 
	for(i=1;i<n;i++) { 
		temp=a[i]; 
                j=i-1; 
		while((a[j]>temp) && (j>=0)) { 
			a[j+1]=a[j]; 
                        j--;
                } 
		a[j+1]=temp; 
		} 
		
		cout<<"Array dopo l'ordinamento: \n"; 
		for(i=0; i<n; i++) 
			cout<<a[i]<<" ";
	
	return 0; 
}

Algoritmo spiegato passo passo:

Partiamo da questo array non ordinato:

6 2 4 9 1 8

for(i=1;i<n;i++) // Inizialmente l’indice i parte da 1, cioè i=1

temp=arr[i]; //temp=2

j=i-1; //j=0

while(a[j]>temp && j>=0)

/*6>2 vero j>=0 vero. Dunque la condizione è vera*/

a[j+1]=a[j]; //a[1]=6

j–; //j=-1.

/*Dato che la condizione j>=0 non è verificata si esce dal ciclo while*/

a[j+1]=temp; //a[0]=2


Ci troveremo quindi in questa situazione:
2 6 4 9 1 8

for(i=1;i<n;i++) //i viene incrementato di 1, quindi parte da 2, cioè i=2

temp=a[i]; //temp=4

j=i-1; //j=1

while(a[j]>temp && j>=0)

/* 6>4 vero j>=0 vero. Dunque la condizione è vera*/

a[j+1]=a[j]; //cioè ad a[2] assegno il valore di a[1]. Quindi a[2]=6

j–; //j=0

/*Dato che a[j]>temp cioè 2>4 non è verificata, non si continua con il while*/
a[j+1]=temp; // cioè a[1]=4


Questa dunque la nuova situazione:

2 4 6 9 1 8

for(i=1;i<n;i++) //i viene incrementato di 1, quindi parte da 3, cioè i=3

temp=a[i]; //temp=9

j=i-1; //j=2

while(a[j]>temp && j>=0) // 6>9 falsa. Dunque la condizione è falsa.

/*Non si entra dentro al ciclo while perciò a[2] rimane a 6, quindi la prossima istruzione sarà:*/

a[j+1]=temp; //cioè a[3]=9

 

Ecco dunque l’array fino a questo punto:
2 4 6 9 1 8

for(i=1;i<n;i++) //i viene incrementato di 1, quindi parte da 4, cioè i=4

temp=a[i]; //temp=1

j=i-1; //j=3

while(a[j]>temp && j>=0)

/* 9>1 vero; j>=0 vero. Quindi la condizione è vera*/

a[j+1]=a[j]; //a[4]=9

j–; //j=2

/*Dato che a[j]>temp cioè 9>1 è verificata e j>=0 anche, si continua con il while*/

a[j+1]=a[j]; //a[3]=6

j–; //j=1

/*Dato che a[j]>temp cioè 6>1 è verificata e j>=0 anche, si continua con il while*/

a[j+1]=a[j]; //a[2]=4

j–; //j=0

/*Dato che a[j]>temp cioè 4>1 è verificata e j>=0 anche, si continua con il while*/

a[j+1]=a[j]; //a[1]=2

j–; //j=-1

/*Dato che a[j]>temp cioè 2>1 è verificata e j>=0 non è verificata, si esce dal while*/

a[j+1]=temp; //cioè a[0]=1

Come si può notare gli elementi 2, 4, 6, 9 sono stati shiftati a destra.


Quindi avremo:

1 2 4 6 9 8

for(i=1;i<n;i++) // l’indice i parte da 5, cioè i=5

temp=arr[i]; //temp=8

j=i-1; //j=4

while(a[j]>temp && j>=0)

/*9>8 vero e j>=0 vero. Dunque la condizione è vera*/

a[j+1]=a[j]; //a[5]=9

j–; //j=3.

/*Dato che la condizione a[j]>temp non è verificata si esce dal ciclo while*/

a[j+1]=temp; //a[4]=8

Adesso l’indice i diventa 6 che non è minore di 6 (i<n) e quindi si esce dal for.

Ecco l’algoritmo ordinato:

1 2 4 6 8 9

Questa è l’implementazione dell’algoritmo insertion sort in C++ che volevo presentare in questa lezione.

Alcuni link utili

Esercizi con gli array in C++

Esercitazione sugli array in C++

Array in C++

Passaggio di parametri per valore o per riferimento

Equazioni di secondo grado in C++

Le variabili globali e loali in C++

Uso delle funzioni in C++

Funzioni in C++

Definizione di funzioni in C++

Libreria cmath

Come usare il for in C++

Massimo tra n numeri in C++

Iterazioni in C++

Ciclo while in C++

Ciclo do while

Operatori logici in C++

Esercizi con switch case in C++

If else in C++

Casting in C++

Tutorial C++

Successione di Fibonacci in C++

Autore dell'articolo: cristina

Avatar per Coding Creativo

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *