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.
Insertion sort – Esempio funzionamento
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 confrontiamo 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:24 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:246 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:1246 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.
Quinto 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 ej>=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 insesrtion sort in C++ spiegato passo passo:
Partiamo da questo array non ordinato:
6 2 4 9 1 8
Il ciclo esterno verrà eseguito 5 volte, perchè partiamo dalla seconda posizione.
Prima iterazione
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
Seconda iterazione
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 veroj>=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:
24 6 9 1 8
Terza iterazione
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
Quarta iterazione
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
Quinta iterazione
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.
In questa lezione affronteremo il selection sort in C++, cioè un algoritmo di ordinamento che consiste nel selezionare volta per volta un elemento, quello minore o quello maggiore, all’interno dell’array per poi posizionarlo nella sequenza ordinata.
L’algoritmo selection sort è anche conosciuto come algoritmo per minimi successivi.
L’algoritmo ha una complessità esponenziale θ (n2) sia nel caso peggiore sia nel caso migliore, quindi risulta essere poco efficiente.
Come il bubble sort ordina l’array in più passate.
Facciamo un esempio pratico di come funziona l’algoritmo selection sort. Ho messo in nero i numeri disordinati, in rosso quelli ordinati e in verde quelli cambiati di posto.
Array iniziale:
20 – 13 – 40 – 7 – 1 – 37
Primo passaggio: trovo il minimo che è 1, quindi lo sposto in prima posizione:
1 – 13 – 40 – 7 – 20 – 37
Secondo passaggio: trovo il minimo che è 7, quindi:
1 – 7 – 40 – 13 – 20 – 37
Terzo passaggio: trovo il minimo che è 13, quindi:
1 – 7 – 13 – 40 – 20 – 37
Quarto passaggio: trovo il minimo che è 20, quindi:
1 – 7 – 13 – 20 – 40 – 37
Quinto passaggio: trovo il minimo che è 37, quindi:
1 – 7 – 13 – 20 – 37 – 40
Procedimento selection sort in C++
Per realizzare l’algoritmo di ordinamento utilizziamo allora un ciclo esterno con un indice i che va da 0 ad n-2.
Dopo utilizziamo la variabile min che memorizza l’indice a cui punta il valore minimo. Questa variabile è inizializzata al primo elemento: min=i.
Poi realizziamo un ciclo interno utilizzando un indice j che va da i+1 (posizione successiva ad i) fino ad n.
Infine controlliamo se il numero puntato dall’indice j è più piccolo del min e se è vero lo scambiamo. Per effettuare lo scambio utilizzo una variabile temporanea temp.
Ecco quindi il listato completo dell’algoritmo selection sort in C++.
#include<iostream>
using namespace std;
#define N 6
int main()
{
int i, j, min, temp;
int a[N];
cout<<"Inserisci gli elementi:\n";
for(i=0;i<N;i++)
cin>>a[i];
for(i=0;i<N-1;i++)
{
min=i;
for(j=i+1;j<N;j++)
if (a[j]<a[min])
min= j;
temp=a[min];
a[min]=a[i];
a[i]=temp;
}
cout<<"Array ordinato con selection sort:";
for(i=0;i<N;i++)
cout<<" "<<a[i];
return 0;
}
Questo è un esempio di possibile implementazione del selection sort in C++.
In questa lezione svilupperemo l’algoritmo bubble sort in C++. Il bubble sort è l’algoritmo di ordinamento più semplice da implementare, ma è anche poco efficiente.
Il bubble sort è
utilizzato in ambito didattico per far apprendere le logiche e le
basi della programmazione.
Il metodo che
utilizza consiste nel confrontare elementi vicini tra loro portando
l’elemento maggiore in ultima posizione durante la prima “passata”
(eseguendo n-1 confronti), poi il secondo massimo in penultima
posizione e così via finché l’array non è ordinato.
La complessità è O(n2), sia nel caso peggiore che nel caso migliore.
Implementazione bubble sort in C++
Innanzitutto inseriamo gli elementi nell’array e dopo procediamo all’ordinamento.
Per fare l’ordinamento, confronto se l’elemento in posizione i è maggiore dell’elemento in posizione i +1. Se è vero effettuo lo scambio. Per scambiare gli elementi utilizzo una variabile di appoggio temp.
Il ciclo interno non è sufficiente per effettuare l’ordinamento. Dunque per ottenere l’ordinamento completo bisogna ripetere n-1 volte il procedimento e questo lo otteniamo con un ciclo for più esterno controllato dall’indice j che va da 0 a n-1.
Dunque segue il listato del bubble sort in C++.
#include<iostream>
#define N 10
using namespace std;
int main()
{
int a[N],i,j,temp;
cout<<"Inserisci gli elementi:\n";
for(i=0;i<N;i++)
cin>>a[i];
//ordino gli elementi
for(j=0;j<N-1;j++)
for(i=0;i<N-1;i++)
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
cout<<"Array ordinato con bubble sort:";
for(i=0;i<N;i++)
cout<<" "<<a[i];
return 0;
}
Come potete notare l’algoritmo è molto semplice, ma purtroppo poco efficiente perché anche nel caso in cui l’array fosse ordinato ripeterebbe in ogni caso n-1 volte il ciclo esterno.
Ottimizzazione bubble sort – ordinamento per scambio con sentinella
Pensiamo a delle ottimizzazioni dell’algoritmo. Ad esempio interrompendo il ciclo esterno se al termine del ciclo interno non si è fatto nessuno scambio.
Quindi utilizziamo una variabile flag che inizializzo a zero. Dopo, nel ciclo interno se effettuo almeno uno scambio la variabile flag la imposto uguale a 1. Potevo anche utilizzare una variabile booleana.
Se rimane a zero, vuol dire che non c’è nulla da ordinare e quindi interrompo il ciclo esterno.
Con valori iniziali poco disordinati questa prima ottimizzazione porta ad un certo guadagno di tempo.
Ecco dunque il listato completo del bubble sort in C++ ottimizzato.
#include<iostream>
using namespace std;
#define N 10
int main()
{
int a[N],i,j,temp,k;
cout<<"Inserisci gli elementi:\n";
for(i=0;i<N;i++)
cin>>a[i];
//ordino gli elementi
do {
k=0;
for(i=0;i<N-1;i++)
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
k=1;
}
} while (k==1);
cout<<"Array ordinato con bubble sort:";
for(i=0;i<N;i++)
cout<<" "<<a[i];
return 0;
}
Seconda ottimizzazione dell’algoritmo bubble sort in C++
Un’altra possibile ottimizzazione si può ottenere considerando che ad ogni incremento di j almeno gli ultimi j+1 elementi sono già ordinati. Questa considerazione è possibile perché di volta in volta, per ogni iterazione, l’elemento più grande è spostato verso destra.
Quindi ad ogni iterazione accorciamo il ciclo dei confronti. Infatti all’n-esima iterazione si può fare a meno di toccare gli ultimi n-1 elementi che ormai sono nella loro posizione definitiva. Dunque decrementiamo n di uno ad ogni iterazione (- -n), in modo da diminuire di 1, di volta in volta, il numero dei confronti effettuati.
Ecco dunque il listato modificato del bubble sort in C++.
#include<iostream>
using namespace std;
int main()
{
int N=6;
int a[N],i,j,temp,k;
cout<<"Inserisci gli elementi:\n";
for(i=0;i<N;i++)
cin>>a[i];
//ordino gli elementi
do {
k=0;
for(i=0;i<N-1;i++)
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
k=1;
}
--N;
} while (k==1);
cout<<"Array ordinato con bubble sort ottimizzato:";
N=6;
for(i=0;i<N;i++)
cout<<" "<<a[i];
return 0;
}
Terza ottimizzazione
Facciamo un’ulteriore ottimizzazione all’algoritmo bubble sort. Infatti consideriamo che ogni ciclo interno si interrompe proprio dove, la volta prima, è avvenuto lo scambio. Pertanto alla fine di ogni iterazione più elementi si trovano nella posizione definitiva e si può evitare di trattarli.
Quindi memorizziamo in una variabile x la posizione i+1 dell’ultimo scambio e ad n assegniamo il valore di x.
#include<iostream>
using namespace std;
int main()
{
int N=6;
int a[N],i,j,temp,k,x;
cout<<"Inserisci gli elementi:\n";
for(i=0;i<N;i++)
cin>>a[i];
//ordino gli elementi
do {
k=0;
for(i=0;i<N-1;i++)
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
k=1;
x=i+1;
}
N=x;
} while (k==1);
cout<<"Array ordinato con bubble sort ottimizzato:";
N=6;
for(i=0;i<N;i++)
cout<<" "<<a[i];
return 0;
}
Questi esempi di implementazione del bubble sort in C++ sono utili a scopo didattico.
Implementiamo il quick sort in C, un algoritmo di ordinamento che così come il merge sort segue il metodo divide et impera. Il quick sort è un algoritmo che viene utilizzato per ordinare i dati in un vettore (array).
Cioè è basato su questa tecnica:
Divide: Si suddivide il problema in sotto-problemi più piccoli;
Impera: si risolvono i problemi in maniera ricorsiva (ovvero un algoritmo che richiama se stesso);
Combina: al fine di ottenere il risultato finale si combina l’output ottenuto dalle precedenti chiamate ricorsive.
Il Quick Sort è infatti un algoritmo ricorsivo che ha, generalmente, prestazioni migliori tra quelli basati su confronto.
In questo algoritmo la ricorsione viene fatta non dividendo il vettore in base agli indici ma in base al suo contenuto.
Prima di risolvere l’algoritmo del quick sort in C, studiamo l’idea di base:
Si sceglie l’elemento centrale del vettore (detto pivot) e lo si memorizza in una variabile
a sinistra si mettono gli elementi >= pivot
a destra si mettono gli elementi < pivot
si ordina ricorsivamente la parte destra e la parte sinistra.
La procedura che divide in due parti il vettore si chiama partition.
Chiaramente la scelta del pivot non è legata necessariamente al primo elemento, potrebbe anche essere l’ultimo o il mediano oppure essere un elemento random.
Esempio del quick sort in C
Scegliamo come Pivot il primo elemento, dunque Pivot=4.
Dobbiamo avere a sinistra gli elementi minori di Pivot, a destra gli elementi maggiori.
Facciamo partire l’indice i da sinistra ovvero dal primo elemento e l’indice j da destra ovvero dall’ultimo elemento.
Per comodità ci riferiremo a primoe ultimo per vedere in dettaglio tutti i passaggi.
Dapprima avremo:
Pivot=4 (si trova in posizione i)
primo=4
ultimo=8
Ci chiediamo Pivot è minore di ultimo? Cioè 4 è minore di 8?
Si, allora procedo e sposto l’indice j (perchè a destra devo avere gli elementi maggiori, quindi non devo scambiarli!)
Quindi avremo:
Pivot=4 (si trova in posizione i)
primo=4
ultimo=3
Ci poniamo allora la domandaPivot è minore di ultimo?
No, allora sposto Pivot in posizione j, cioè in ultimo.
Quindi avrò il terzo passaggio:
Pivot=4 (si trova in posizione j)
primo=3
ultimo=4
Adesso Pivotè in posizione indicata dall’indice j, dunque sposto l’indice i.
Mi chiedo Pivotè maggiore di primo?
Si, allora sposto l’indice i. E continuo spostando l’indice i fino all’elemento 5.
Quindi avrò:
Pivot=4 (si trova in posizione j)
primo=5
ultimo=4
Mi chiedo ancora Pivot è maggiore di primo?
No, allora sostituisco Pivot nella posizione di primo.
Quindi avrò:
Pivot=4 (si trova in posizione i)
primo=4
ultimo=5
Come in figura sotto:
Adesso Pivot si trova in posizione i, facciamo muovere j.
Cioè Pivotè minore di ultimo? Si allora sposto l’indice j e avrò:
Pivot=4 (si trova in posizione i)
primo=4
ultimo=0
Pivotè minore di ultimo?
No allora li scambiamo. Avremo:
Pivot=4 (si trova in posizione j)
primo=0
ultimo=4
Quindi ci chiediamo Pivot è maggiore di primo?
Si, allora spostiamo l’indice i e avremo la situazione:
Pivot=4 (si trova in posizione i)
primo=4
ultimo=2
Adesso chiediamo: Pivotè minore di primo?
Si allora l’indice i coinciderà con j.
Adesso che abbiamo a destra gli elementi maggiori del Pivot e a sinistra gli elementi minori dobbiamo procedere con l’ordinamento dei due sotto-array procedendo allo stesso modo.
Sviluppo dell’algoritmo Quick Sort in C
#include<stdio.h>
#define MAX 100
int insert_array(int a[]) {
int n, i;
printf("Quanti elementi?: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("elemento %d: ", i);
scanf("%d", &a[i]);
}
return(n);
}
void stampa_array(int a[], int n) {
int i;
for (i=0; i<n; i++) {
printf("%d ", a[i]);
}
printf("\n");
return;
}
void quicksort(int a[MAX],int primo,int ultimo){
int i, j, pivot, temp;
/*pivot -- inizialmente il pivot è il primo elemento
primo e ultimo sono le due variabili che servono per scorrere l'array
*/
if(primo<ultimo){
pivot=primo;
i=primo;
j=ultimo;
while(i<j){
while(a[i]<=a[pivot]&&i<ultimo)
i++;
while(a[j]>a[pivot])
j--;
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
quicksort(a,primo,j-1);
quicksort(a,j+1,ultimo);
}
}
int main(){
int n, a[MAX],i;
n = insert_array(a);
printf("Array iniziale: ");
stampa_array(a,n);
quicksort(a,0,n-1);
printf("Array ordinato con quick-sort: ");
stampa_array(a,n);
return 0;
}
Il tempo di esecuzione del quick sort è proporzionale a n log n dunque è molto inferiore a n2.
Chiaramente quella presentata è solo un esempio di possibile implementazione del quick sort in C.
Il merge sort è un algoritmo di ordinamento inventato da Von Neumann nel 1945.
È un algoritmo di ordinamento più complesso ma molto più efficiente degli altri visti in precedenza (selection sort e insertion sort), soprattutto con vettori di grandi dimensioni.
Sfrutta la tecnica divide et impera, ovvero la suddivisione del problema in sotto-problemi della stessa natura di dimensione a mano a mano sempre più piccola, li risolve ricorsivamente e infine combina le soluzioni parziali per ottenere la soluzione al problema di partenza.
Quindi si divide ricorsivamente il vettore in due parti da ordinare separatamente. Successivamente si fondono le due parti per ottenere un array ordinato globalmente.
Il merge sort utilizza inoltre un array di appoggio.
Implementazione del merge sort in C
#include <stdlib.h>
#include <stdio.h>
#define max 100
int insert_array(int V[]) {
int n, i;
printf("Quanti elementi?: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("elemento %d: ", i);
scanf("%d", &V[i]);
}
return(n);
}
void stampa_array(int V[], int n) {
int i;
for (i=0; i<n; i++) {
printf("%d ", V[i]);
}
printf("\n");
return;
}
void merge(int a[], int p, int q, int r) {
int i, j, k=0, b[max];
i = p;
j = q+1;
while (i<=q && j<=r) {
if (a[i]<a[j]) {
b[k] = a[i];
i++;
} else {
b[k] = a[j];
j++;
}
k++;
}
while (i <= q) {
b[k] = a[i];
i++;
k++;
}
while (j <= r) {
b[k] = a[j];
j++;
k++;
}
for (k=p; k<=r; k++)
a[k] = b[k-p];
return;
}
void mergeSort(int a[], int p, int r) {
int q;
if (p < r) {
q = (p+r)/2;
mergeSort(a, p, q);
mergeSort(a, q+1, r);
merge(a, p, q, r);
}
return;
}
int main(void) {
int n, V[max];
n = insert_array(V);
mergeSort(V, 0, n-1);
stampa_array(V, n);
return(0);
}
Prestazioni
L’algoritmo sia nel caso medio che in quello pessimo ha una complessità pari a Θ (n log n). La complessità della funzione merge é lineare Θ(n).
