L'università è facile…

studia finché non lo diventa…

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:

image

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

clip_image002[6]

Questo ci da un risultato dell’ordine di

clip_image002

Conclusione  La somma totale è circa

clip_image002[8]

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.

avatar firma

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Informazione

Questa voce è stata pubblicata il 13/06/2010 da in Algoritmi e strutture dati con tag , , , .
%d blogger hanno fatto clic su Mi Piace per questo: