INSERTION SORT
LA LOGICA DELL'ALGORITMO
Si suppone che i primi k elementi (posizioni da 0 a k-1) siano ordinati tra loro (con 0 <= k < n, dove n è il numero degli elementi dell'array), si procede estendendo il numero di elementi ordinati a k+1.
Si prende il (k+1)-esimo elemento (cioè quello in posizione k) e lo si inserisce nella posizione corretta rispetto ai primi k elementi già ordinati.
Vediamo ora un implementazione dell'algoritmo in Java.
/*Supponiamo di voler ordinare degli elementi in un array di interi*/
public void insertionSort(int[] array){for(int k=1; k < array.length; k++){//controlla i primi k elementi gia' ordinati
int j;
int x = array[k];//elemento da inserire
for(i=0; i < k; i++){
if(array[i] > x){
break;
}
if(i < k){
for(int j=k; j > i; j--){
array[j] = array[j-1];
}
array[i] = x;
}
}
}
}
SPIEGAZIONE DELL'IMPLEMENTAZIONE DELL'ALGORITMO
Il for piu' esterno controlla i primi k elementi gia' ordinati (array[0]...array[k-1]). Si "salva" nella variabile x l'elemento da inserire tra i k elementi che ora si trova in posizione k(quindi il k+1-esimo). Nel for piu' interno si compara x con i k elementi gia' ordinati per stabilire dove x va inserito.
Se si trova la posizione tra gli elementi gia' ordinati allora si shifta verso destra¹ tutti i k elementi per far spazio alla posizione che deve essere occupata da x.
Se invece x risulta maggiore di tutti i k elementi gia' ordinati, vuol dire che x e' gia' nella posizione giusta, quindi non si fa nulla.
Alla fine l'array risultera' ordinato in maniera crescente.
COMPLESSITA' TEMPORALE DELL'ALGORITMO
L'algoritmo insertion sort e' di complessita'
L'operazione dominante dell'implementazione proposta e' il confronto array[i] > x.
L'implementazione proposta in java ha complessita' nel caso ottimo di n(n-1)/2 (∑ i=0 a n-1 di i, la sommatoria di Gauss).
Il caso ottimo qui e' inteso come il caso in cui l'array e' gia' ordinato in maniera crescente.
Il caso peggiore e' il caso in cui l'array e' ordinato in ordine decrescente, in questo caso la complessita' e' n-1.
L'ordinamento con l'insertion sort e' di solito considerato il migliore tra gli algoritmi di complessita'
GRAFICO TEMPORALE DELL'INSERTION SORT
[1]: shiftare verso destra vuol dire "scalare" tutti gli elementi verso destra
(Si può anche scrivere: for(int i=0; i < array.length; i++) {
cosi' si lascia un "buco" in array[0] perchè lo shift parte da i=0)
SELECTION SORT
Il for piu' esterno controlla i primi k elementi gia' ordinati (posizioni da 0 a k-1), all'inizio del ciclo si inizializza l'indice imin al valore del primo elemento di quelli non ordinati (posizione k). Il for interno cerca il minimo tra gli elementi non ordinati, infatti l'indice i del ciclo parte da k+1 fino alla fine dell'array. Quando si esce dal for interno si ha in imin l'indice del minore degli elementi non ordinati. Si controlla che imin non sia rimasto a k e infine si scambia il minimo con l'elemento in posizione k.
L'array risultera' ordinato in maniera crescente.
COMPLESSITA' TEMPORALE DELL'ALGORITMO
L'algoritmo selection sort e' di complessita' Θ(n²).
L'operazione dominante dell'implementazione proposta e' il confronto per il minimo array[i] < array[imin].
L'implementazione proposta in java ha complessita' nel caso ottimo, peggiore e medio di n(n-1)/2 (Σ i = 0 a n-1 di i, la sommatoria di Gauss). Quindi i tre casi coincidono, ovvero il numero di confronti non dipende dalla configurazione dei dati in input.
LA "LOGICA" DELL'ALGORITMO
Si suppone che i primi k elementi (posizioni da 0 a k-1) siano ordinati tra loro (con 0 <= k < n, dove n è il numero degli elementi dell'array) e siano i piu' piccoli dell'array. Si procede estendendo il numero di elementi ordinati a k+1.
Si sceglie il minimo tra i rimanenti n-k elementi (cioe' gli elementi non ordinati) e lo si assegna nella posizione k.
Vediamo un implementazione dell'algoritmo in Java.
/*Supponiamo di voler ordinare degli elementi da un array di interi*/
public static void selectionSort(int[] array){
for(int k = 0; i < array.length-1; i++){
int imin = k;
for(i = k + 1; i < array.length; i++){
if(array[i] < array[imin]){
imin = i;
}
}
if(imin != k){
int tmp = array[imin];
array[imin] = array[k];
array[k] = tmp;
}
}
}
Si sceglie il minimo tra i rimanenti n-k elementi (cioe' gli elementi non ordinati) e lo si assegna nella posizione k.
Vediamo un implementazione dell'algoritmo in Java.
/*Supponiamo di voler ordinare degli elementi da un array di interi*/
public static void selectionSort(int[] array){
for(int k = 0; i < array.length-1; i++){
int imin = k;
for(i = k + 1; i < array.length; i++){
if(array[i] < array[imin]){
imin = i;
}
}
if(imin != k){
int tmp = array[imin];
array[imin] = array[k];
array[k] = tmp;
}
}
}
SPIEGAZIONE DELL'IMPLEMENTAZIONE DELL'ALGORITMO
Il for piu' esterno controlla i primi k elementi gia' ordinati (posizioni da 0 a k-1), all'inizio del ciclo si inizializza l'indice imin al valore del primo elemento di quelli non ordinati (posizione k). Il for interno cerca il minimo tra gli elementi non ordinati, infatti l'indice i del ciclo parte da k+1 fino alla fine dell'array. Quando si esce dal for interno si ha in imin l'indice del minore degli elementi non ordinati. Si controlla che imin non sia rimasto a k e infine si scambia il minimo con l'elemento in posizione k.
L'array risultera' ordinato in maniera crescente.
COMPLESSITA' TEMPORALE DELL'ALGORITMO
L'algoritmo selection sort e' di complessita' Θ(n²).
L'operazione dominante dell'implementazione proposta e' il confronto per il minimo array[i] < array[imin].
L'implementazione proposta in java ha complessita' nel caso ottimo, peggiore e medio di n(n-1)/2 (Σ i = 0 a n-1 di i, la sommatoria di Gauss). Quindi i tre casi coincidono, ovvero il numero di confronti non dipende dalla configurazione dei dati in input.
