Algoritmi di Ordinamento - Prof. Claudio Maccherani – ITC “V.Emanuele II” - Perugia – a.s. 2006/07 Pag. 1
Ordinamenti / SORT
Prof.Claudio Maccherani
1-Insertion 2-Bubble 3-Shell 4-Quick
1) INSERTION Sort
L’insertion sort (ordinamento a inserimento), è un semplice algoritmo che ordina un array senza doverne creare un altro di appoggio. L'algoritmo utilizza due cicli nidificati e quindi due indici: , il primo indice inizia dal primo elemento dell’array; il secondo punta all’elemento successivo di quello puntato dal primo indice, inizialmente al secondo. Se il primo elemento è maggiore del secondo, i due valori vengono scambiati. Poi il secondo indice avanza di una posizione e il primo indice riparte dall'elemento precedente quello puntato dal secondo. Se l'elemento puntato dal primo indice non è maggiore di quello a cui punta il secondo indice, il primo indice avanza; e così fa, finché si trova nel punto in cui il valore del primo indice deve essere inserito.
For i = 1 To n - 1
For j = i + 1 To n
I f v( j ) < v( i) Then k = v( j ) v( j ) = v( i) v( i) = k End I f
N ext j N ext I
2) BUBBLE Sort
Il bubble sort (ordinamento a bollicine) è un semplice algoritmo che ordina un array senza doverne creare un altro di appoggio. Il nome dell'algoritmo è dovuto al fatto che, durante l'applicazione del procedimento, i valori vengono spostati all'interno dell'array con una dinamica che ricorda il movimento delle bollicine in un bicchiere di spumante. In particolare, alcuni elementi attraversano l'array velocemente (come bollicine che emergono dal fondo del bicchiere), altri più lentamente (a differenza di quanto avviene nel caso del bicchiere di spumante, tuttavia, alcuni elementi salgono ma altri scendono). L’algoritmo prevede che gli elementi dell'array siano confrontati a due a due, ciascun elemento con quello successivo e se questi non risultano in ordine vengono scambiati. Il procedimento verrà ripetuto finché, durante una scansione dell’array, non sarà fatto alcuno scambio.
Do
scam bio = 0 For i = 1 To n - 1
I f v( i) > v( i + 1 ) Then
k = v( i) : v( i) = v( i + 1 ) v( i + 1 ) = k: scam bio = 1 End I f
N ext i
Loop W hile scam bio = 1
Algoritmi di Ordinamento - Prof. Claudio Maccherani – ITC “V.Emanuele II” - Perugia – a.s. 2006/07 Pag. 2 3) SHELL Sort
Lo Shell sort (da D.L.Shell che lo ideò) o Shell-Metzner sort (da Marlene Metzner che lo implementò in Fortran) è uno dei più vecchi algoritmi di ordinamento, veloce e semplice, che ordina un array senza doverne creare un altro di appoggio. È un’estensione dell’Insertion sort che funziona funziona spostando i valori di più posizioni per volta man mano che risistema i valori, diminuendo gradualmente la dimensione del passo sino ad arrivare ad uno.
i1 = 1 : Do: i1 = 3 * i1 + 1 : Loop Until i1 > n Do i1 = i1 / 3
For i = i1 + LBound( v) To UBound( v) Tem p = v( i)
Hold = i
Do W hile v( Hold - i1 ) > Tem p v( Hold) = v( Hold - i1 ) Hold = Hold - i1
I f Hold < i1 Then Exit Do Loop
v( Hold) = Tem p N ext i
Loop Until i1 = LBound( v)
4) QUICK Sort
Il Quick sort (ordinamento rapido) è un ottimo algoritmo di ordinamento ricorsivo basato sul paradigma "divide et impera" che ordina un array senza doverne creare un altro di appoggio. Alla base del suo funzionamento vi è l'utilizzazione ricorsiva della procedura di partizione (che, preso un elemento dell’array, pone gli elementi più piccoli prima e quelli più grandi dopo). Ad ogni fase si effettua un ordinamento parziale di una sequenza di oggetti da ordinare. Assunto un elemento come perno della fase, si confrontano con esso gli altri elementi e si posizionano prima i più piccoli e dopo i più grandi, senza tener conto del loro ordine. Dopo questa fase il perno è nella sua posizione definitiva.
Successivamente si organizzano nuovi fasi simili nelle quali si procede all'ordinamento parziale delle sottosequenze di elementi rimasti non ordinati, fino al loro esaurimento.
Sub Quick_ Sort( I nizio, Fine) I f Fine > I nizio Then
Pivot = v( I nizio) : i1 = I nizio + 1 : i2 = Fine + 1 Do W hile i1 < i2
I f v( i1 ) < Pivot Then i1 = i1 + 1 Else
i2 = i2 – 1 : k = v( i1 ) : v( i1 ) = v( i2 ) : v( i2 ) = k End I f
Loop
i1 = i1 – 1 : k = v( i1 ) : v( i1 ) = v( I nizio) : v( I nizio) = k Call Quick_ Sort( I nizio, i1 )
Call Quick_ Sort( i2 , Fine) End I f
Algoritmi di Ordinamento - Prof. Claudio Maccherani – ITC “V.Emanuele II” - Perugia – a.s. 2006/07 Pag. 3 Algoritmi di ordinamento a CONFRONTO
Per avere un’idea dell’efficienza e velocità dei diversi algoritmi di ordinamento, vediamo quanti scam bi vengono effettuati ordinando un vettore di 1000 elem enti contenente dei num eri interi generati in m aniera casuale. I risultati sono indicativi in quanto possono variare in funzione della disposizione iniziale dei dati.
L’algoritmo più lento risulta essere il Bubble sort (260.319 scambi), che comunque è paragonabile all’Insertion sort (251.700 scambi). Molto più veloce lo Shell sort (15.222 scambi), ma l’algoritmo più efficiente e veloce in assoluto risulta essere, naturalmente, il Q uick sort (7.451 scam bi).
