Informatica I - l'analisi delle prestazioni di InsertionSort

Codice di InsertionSort

Codice di InsertionSort:

public class ArrayAlgs {
    ...
    public static void insertionSort(int[] v, int vSize) {
        for (int i = 1; i < vSize; i++) {
            int temp = v[i]; //nuovo el. da inserire
            int j;
            for (j = i; j > 0 && temp < v[j-1]; j--)
                v[j] = v[j-1];
            v[j] = temp; // inserisci temp
        }
    }
    ...
}

Ordiniamo con inserimento un array di n elementi

• Ciclo esterno n-1 esegue iterazioni
• Ad ogni iterazione vengono eseguiti 2 accessi (uno prima del ciclo interno ed uno dopo)
  • Il ciclo interno
• 3 accessi per ogni sua iterazione

Quante iterazioni esegue?

Dipende da come sono ordinati i dati.

Caso peggiore

I dati sono ordinati al rovescio:

• Ciascun nuovo elemento inserito richiede lo spostamento di tutti gli elementi alla sua sinistra perché deve essere inserito in posizione 0.

Caso migliore

I dati sono già ordinati:

• Il ciclo più interno non esegue mai iterazioni, quindi richiede un solo accesso per la prima verifica.

• Il ciclo esterno esegue n-1 iterazioni. Ad ogni iterazione vengono eseguiti
  • 2 accessi (uno prima del ciclo interno ed uno dopo)
  • 1 accesso (per verificare la condizione di terminazione del ciclo interno)

Caso medio

I dati sono in ordine casuale:

• In media, ciascun nuovo elemento inserito richiede lo spostamento di metà degli elementi alla sua sinistra.