Come richiesto da l’Algor method ,eseguiro 4 passi.
1.Il Problema
Ordinare dei dati omogenei (dello stesso tipo) o in ordine crescente o decrescente dipendendo dell’applicazione specifica.
2.Struttura dati usata
Di solito si usa un array di interi. Ma questo può variare nelle applicazioni specifiche.
3.Pseudo codice
Praticamente l’algoritmo si comporta come un umane che vuole ordinare una mano di carta. Al ’inizio , tutte le carte sono sul tavolo,con la mono destra prendo una a una le carte e le metto sulla mano sinistra nel posto giusto. Per mettere la carta nel posto giusto ogni volta ,faccio un paragono con le carte della mano sinistra. Ora che sappiamo come fa l’algoritmo ,ecco lo pseudo codice :
INSERTION-SORT(A)
1. for j <– 2 to length[A]
2. do key <– A[J]
3. // inserire A[j] nella sequenza ordinata A[1..j -1]
4. i <– j – 1
5. while i>0 and A[i]>key
6. do A[i + 1] <– A[i]
7. i <– i – 1
8. A[i + 1] <– key
Notiamo che l’ordinamento usa un solo array per questo si parla di ordinamento in place.
Key rappresenta la nuova carta da inserire ogni volta nella mano sinistra.
A[1..j-1] rappresenta la mano sinistra cioè la parte de l’array già ordinata.
J serve ad indicizzare la variabile da inserire in A[1..j-1]
I permette di scorrere A[1..j-1] cioè da j-1 a 1.
il primo ciclo While è quello che fa prendere ogni volta una variabile key da inserire dentro A[1..j-1].
il secondo ciclo invece è quello che fa trovare il posto giusto a key paragonandolo ogni volta ad un elemento di A[1..j-1].
Ora che abbiamo capito come funziona l’algoritmo attraverso questo pseudo codice calcoliamo la complessità
4.Complessità
Per calcolare la complessità ,dobbiamo calcolare quante volte viene eseguita una istruzione. un istruzione presente in un ciclo viene eseguita un numero di volte pari a quanti indici il ciclo coinvolge con il contatore. Se associamo una costante cj ad ogni istruzione ,otteniamo qualcosa di questo tipo:
Istruzioni Costo occorrenza
1. for j <– 2 to length[A]
2. do key <– A[J]
3. // inserire A[j] nella sequenza ordinata A[1..j -1]
4. i <– j – 1
5. while i>0 and A[i]>key
6. do A[i + 1] <– A[i]
7. i <– i – 1
8. A[i + 1] <– key
c1 c2
c4 c5 c6 c7 c8
n= length[A]n-1
n-1
£
£-1
£-1
n-1
La somma è quindi c1*n+c2*(n – 1) + c4*(n – 1) + c5*£ + c6*(£ – 1) + c7*(£ – 1) + c8*(n – 1)
Ora vediamo di calcolare £. Il ciclo dalla riga 5 alla 7 va dell’indice 1 a j – 1, quindi il costo di ogni riga di questo ciclo diventa cj*(j – 1). Ma ognuna di queste righe si trovano nel grande ciclo che va dalla prima all’ultima riga (indice coinvolti sono di n – 1); quindi
Conclusione La somma totale è circa
La complessità nel caso peggiore è quindi una forma quadratica.
Spero che hai imparato qualcosa leggendo questo articolo. Se hai dei dubbi o suggerimenti,lasca un commento qui sotto.