Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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)


Insertion Sort (segue)


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


Insertion Sort (segue)

Al termina del loop N indica il numero di elementi letti.

Naturalmente questo algoritmo funziona se il numero di elementi da leggere è inferiore alla dimensione fisica del vettore, altrimenti occorrerà un opportuno test su N prima di entrare nel loop interno.

I tre algoritmi di ordinamento illustrati prevedono un numero di operazioni, scambi o confronti, all’incirca proporzionale al quadrato del numero N di elementi da ordinare.

Dunque per ordinare un vettore di mille elementi occorrono circa un milione di operazioni.
Insertion Sort

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion