Silvia Rossi

(1)

Lezione n.

Parole chiave:

Corso di Laurea:

Insegnamento:

Email Docente:

A.A. 2009-2010

Silvia Rossi

Algoritmi di Ordinamento (2)

21

Informatica

Programmazione I

srossi@na.infn.it

Insertion Sort

(2)

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

(3)

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)

k

parz. ordinati

non ordinati 0

Insertion Sort

(4)

k

parz. ordinati

non ordinati 0

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

(5)

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.

for (k=1; k<=N-1; k++) vet[N] ¬vet[k]

j¬ k - 1

while (j>=0) and (vet[j]>vet[N]) vet[j+1] ¬ vet[j]

j¬j-1

vet[j+1] ¬vet[N]

Insertion Sort

(6)

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

for k from 1 to n-1:

chiave ß A[k]

# inserisce A[k] nella seq. ordinata A[1..k-1]

j ß k-1

while j ≥ 0 and A[j] > chiave:

A[j+1] ß A[j] # sposta j ß j-1 # inserisci A[j+1] ß chiave

k-1 k

2 4 5 ⁱ6 3 1

chiave

2 4 5 ^j6 ^j+6¹ 1 sposta 2 4 ^j5 ^j+5¹ 6 1 sposta 2 ^j4 ^j+4¹ 5 6 1 sposta 2 ^j+3¹ 4 5 6 1

j inserisci

chiave ^{k-1 k}

5 4 6 2 3 1

Insertion Sort

(7)

Insertion Sort

9 10 19 29 30 12 18 29

3 9 10 19 30 29 12 118 30

[0] [1] [2] [3] [4] [5] [6] [7]

¬j

4 9 10 19 30 29 12 18 29

[0] [1] [2] [3] [4] [5] [6] [7]

¬j k

9 30 29 12 18 19

10

[0] [1] [2] [3] [4] [5] [6] [7]

1

¬j

19

2

[0] [1] ^¬[2]j [3] [4] [5] [6] [7]

9 30 29 12 18 9

10 19

19 30 29 12 18 9

10

19 30 29 12 18 9

9 10

(8)

9 10 19 29 30 18 12

9 10 12 19 29 30 18 12

9 10 12 19 29 30 18

9 10 12 18 19 29 30 18

N° confronti: (n-1)+(n-2)+…+1=(n-1)*n/2

6

[0] [1] [2] [3] [4] [5] [6] [7]

9 10 12 19 29 30 18 18

¬j

5 9 10 19 29 30 12 18 12

[0] [1] [2] [3] [4] [5]^¬j [6] [7]

k

Insertion Sort

(9)

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 il seguente algoritmo:

Insertion Sort

int main () { char ch;

int a[100], elemento,j,N;

cout<<" Fine inserimento= 0"<<endl;

cout<<" Elemento "; cin>>elemento;

a[0]=elemento;

N=-1;

while (elemento!=0) {

cout<<" Elemento "; cin>>elemento;

N=N+1;

j=N;

while ((j>=0) && (a[j]>elemento)) { a[j+1]=a[j];

j=j-1;}

a[j+1]=elemento; } for(int k=0; k<=N+1; k++) {

cout<<a[k]<<" "; } cout<<endl;

system("pause");

return 0;}

esercizio21.1.cpp

(10)

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.