2.06 Lezione 6

Selection sort

• Nella iterazione i, troviamo l'index min dell'elemento più piccolo presente.

• Scambiamo a[i] e a[min]

Implementazione

public class Selection{
  public static void sort(Comparable[] a){
    int N = a.length;
    for(int i = 0; i<N; i++){
      int min = i;
      for(int j = i+1; j<N; j++){
        if(less(a[j], a[min]))
          min = j;
        exch(a, i, min);		//funzione che scambia
      }
    }
  }
}

Classe Selection Sort principale

// is v < w ?
    private static boolean less(Comparator comparator, Object v, Object w) {
        return comparator.compare(v, w) < 0;
    }

Metodo less()

// exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

Metodo exch() -> scambia i due indici nell'array passato come argomento

Analisi matematica

Il Selection Sort utilizza (N-1) + (N-2) + ... + 1 + 0 ~ N<sup>2</sup> / 2 comfronti e N scambi.

Con questo algoritmo, non è presente un caso peggiore, come conseguenza le prestazioni nel caso migliore, caso peggiore e caso medio coincidono.

Insertion Sort

Questo algoritmo, pur essendo uno degli algoritmi di base, viene utilizzato in alcuni algoritmi più complessi,

Nell'insertion sort, ad ogni iterazione i, scambiamo a[i] con ogni elemento più grande alla sua sinistra. Arresto lo 'scambio all'indietro' quando a[i-1] < a[i]

Video dell'algoritmo

Implementazione

Usiamo un ciclo for per muoverci su ogni elemento dell'array, ed un ciclo for più interno che partendo da i decrementa j finché j == 0.

for(int i = i; j > 0; j--)
  if(less(a[j], a[j-1]))
    exch(a, j, j-1);					//scambio l'elemento corrente e quello precedente
	else break;

snippet di codice

public class Insertion{
  public static void sort(Comparable[] a){
    int N = a.length;
    for(int i = 0; i<N; i++){
      for(int i = i; j > 0; j--)
        if(less(a[j], a[j-1]))
          exch(a, j, j-1);					//scambio l'elemento corrente e quello precedente
        else break;
    }
  }
}

Insertion sort completo

Animazione Algoritmo

Analisi matematica

Per ordinare un array ordinato in modo random, l'insertion sort usa ~1/4 N² confronti e ~1/4 N² scambi di media.

Pf. Questo perchè ci aspettiamo che ogni elemento si muova indietro per metà strada. Ad esempio, c'è già un ordine parziale, quindi l'elemento non deve fare metà strada all'indietro, oppure alcuni elementi sono già ordinati, ecc.

Best case

L'array è già ordinato, quindi devo fare N-1confronti e 0 scambi.

Worst Case

L'array è ordinato al contrario, ad ogni passo dobbiamo tornare all'inizio, per ogni elemento : ~1/2 N²

Arrays parzialmente ordinati

Inversione

Un'Inversione è un paio di elementi che sono fuori ordine.

A E E L M O T R X P S

Ci sono 6 inversioni: T-R T-P T-S R-P X-P X-S

Array parzialmente ordinato

Un array è parzialmente ordinato se il numero di inversioni è <= c N.

• Ex : Un array ordinato ha 0 inversioni.

Proposizione

Per array parzialmente ordinati l'insertion sort esegue in un tempo lineare.

Dimostrazione

Il numero di scambi è uguale a quello delle inversioni:

numero di confronti = scambi + (N-1)

Questa informazione è molto importante, perchè se ho un array parzialmente ordinato, invece di proseguire ad ordinarlo con degli algoritmi più complessi, e che impiegano più tempo, eseguo un cutoff e continuo con l'insertion sort.

Miglioramenti pratici

Half exchanges

Potremmo pensare di effettuare uno shift degli elementi, invece di uno swap.

Questo elimina un movimento di dati inutile, ed inoltre non utilizziamo più less() e exch() per accedere ai dati.

Binary Insertion Sort

Possiamo inoltre utilizzare la ricerca binaria per cercare un punto di inserimento. In questo caso avremmo un numero di confronti pari a ~N lg N , ma ancor un numero quadratico di accessi all'array.