Capire Insertion Sort

Oggi vediamo più in dettaglio l’algoritmo di ordinamento per inserimento.

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

Questo ci da un risultato dell’ordine di

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.