Silvia Rossi » 21.Algoritmi di Ordinamento - parte seconda

Insertion Sort

E’ l’algoritmo più intuitivo. Se ad esempio si ha un mazzo di carte non ordinato possiamo ordinarlo scorrendo le carte una alla volta e inserendo ogni carta immediatamente dopo la carta più piccola tra quelle che la precedono.

Osserviamo però che in questo caso le k schede già ordinate non sono ancora al loro posto definitivo, come accadeva nei due casi precedenti.

Solo al termine della procedura esse acquisteranno tutte la loro giusta posizione.

Insertion Sort (segue)

Tecnica di ordinamento inserendo via via ogni nuovo elemento nella posizione giusta rispetto ai precedenti:

• scorrendo le carte una alla volta e inserendo ogni carta immediatamente dopo la carta più piccola tra le precedenti;
• supponiamo che le prime k carte siano ordinate ma non nella loro posizione definitiva (parzialmente ordinate);

Insertion Sort (segue)

Tecnica di ordinamento inserendo via via ogni nuovo elemento nella posizione giusta rispetto ai precedenti:

• scorrendo le carte una alla volta e inserendo ogni carta immediatamente dopo la carta più piccola tra le precedenti;
• supponiamo che le prime k carte siano ordinate ma non nella loro posizione definitiva (parzialmente ordinate);

Insertion Sort (segue)

Poiché il primo elemento è sicuramente parzialmente ordinato, il for esterno può iniziare da 1.
Prima che inizi il ciclo interno conserviamo il valore di vet[k] in vet[N], il posto k ora è “libero” e può essere sfruttato per spostare verso destra ogni elemento già parzialmente ordinato, a partire dall’ultimo che ha indice k-1, che risulti maggiore di vet[N].

In uscita dal loop interno sappiamo che in vet[j] si trova il più grande dei numeri più piccoli di vet[N] e dunque possiamo terminare il loop interno sistemando vet[N] nella posizione libera j+1.
Naturalmente è possibile adoperare questo algoritmo solo se N non rappresenta la dimensione fisica dell’array a run time.

Insertion Sort (segue)

Insertion sort sugli elementi di un array A di dimensione n:

• diciamo che A è parzialmente ordinato da 0 a k-1 se il sottoarray A[0...k-1] ha gli stessi elementi del sottoarray originario ma in ordine:

Insertion Sort (segue)

Se dobbiamo leggere da un file o da tastiera una successione di elementi che deve essere ordinata, potremmo dapprima inserirli in un array e poi ordinarli, ma in genere è preferibile eseguire le due operazioni contemporaneamente adoperando la tecnica dell’insertion sort. Si ottiene l’algoritmo come nella figura di lato.

Esercizio 21.1 Mostra codice