Shaker sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Altri progetti: Correggo il link |
Nessun oggetto della modifica |
||
Riga 6:
|space=
|optimal=No
|complete=
}}
In [[informatica]] lo '''Shaker sort''', noto anche come '''Bubble Sort Bidirezionale''', '''Cocktail Sort''', '''Cocktail Shaker Sort''' o '''Shuttle Sort''' è un [[algoritmo]] [[algoritmo di ordinamento|di ordinamento]] particolarmente indicato per l'ordinamento di [[array]], è stato sviluppato dalla [[Sun Microsystems]].
Lo shaker sort è sostanzialmente una variante del [[bubble sort]] in cui l'indice del ciclo più interno, anziché scorrere continuamente dall'inizio alla fine,
''Nota: la comprensione di quanto segue richiede di avere compreso il funzionamento generale del [[
==
La forma più semplice dello shacker sort scorre l'intera lista ad ogni passaggio:
'''procedure''' shackerSort( A ''':''' lista di elementi da ordinare ) '''defined as:'''
'''do'''
swapped := false
'''for each''' i '''in''' 0 '''to''' length( A ) - 2 '''do:'''
'''if''' A[ i ] > A[ i + 1 ] '''then''' <span style="color:green">// controlla se i 2 elementi sonon in ordine errato</span>
swap( A[ i ], A[ i + 1 ] ) <span style="color:green">// scambia di posto i 2 elementi</span>
swapped := true
'''end if'''
'''end for'''
'''if''' swapped = false '''then'''
<span style="color:green">// se non si eseguono scambi, si può uscire dal ciclo più esterno</span>
'''break do-while loop'''
'''end if'''
swapped := false
'''for each''' i '''in''' length( A ) - 2 '''to''' 0 '''do:'''
'''if''' A[ i ] > A[ i + 1 ] '''then'''
swap( A[ i ], A[ i + 1 ] )
swapped := true
'''end if'''
'''end for'''
'''while''' swapped <span style="color:green">// se non sono stati eseguiti scambi, allora la lista è ordinata</span>
'''end procedure'''
Il primo passaggio verso destra spostera l'elemento più grande nella sua posizione corretta alla fine della lista, mentre il successivo passaggio verso sinistra sposterà l'elemento più piccolo nella sua posizione corretta all'inizio della lista.
Il secondo passaggio completo sposterà il secondo elemento più grande ed il secondo più piccolo nelle loro posizioni corrette, e così via: dopo ''i'' passaggi i primi ''i'' elementi e gli ultimi ''i'' elementi della lista saranno posizionati correttamente, e non sarà necessario ricontrollarli. Il numero di operazioni può essere ridotto accorciando la parte della lista che viene ordinata ad ogni passaggio. <!-- (see [[Bubble_sort#Alternative_implementations|bubble sort]]).-->
'''procedure''' cocktailSort( A ''':''' lista degli elementi da ordinare ) '''defined as:'''
<span style="color:green">// `begin` ed `end` segnano il primo e l'ultimo indice da controllare</span>
begin := -1
end := length( A ) - 2
'''do'''
swapped := false
<span style="color:green">// incremeneta `begin` perché gli elementi prima di `begin` sono ordinati correttamente</span>
begin := begin + 1
'''for each''' i '''in''' begin '''to''' end '''do:'''
'''if''' A[ i ] > A[ i + 1 ] '''then'''
swap( A[ i ], A[ i + 1 ] )
swapped := true
'''end if'''
'''end for'''
'''if''' swapped = false '''then'''
'''break do-while loop'''
'''end if'''
swapped := false
<span style="color:green">// decrementa `end` perché gli elementi dopo `end` sono ordinati correttamente</span>
end := end - 1
'''for each''' i '''in''' end '''to''' begin '''do:'''
'''if''' A[ i ] > A[ i + 1 ] '''then'''
swap( A[ i ], A[ i + 1 ] )
swapped := true
'''end if'''
'''end for'''
'''while''' swapped
'''end procedure'''
==Spiegazione==
Il bubble sort ha una asimmetria intrinseca: i valori dell'array vengono spostati ''velocemente'' in un verso (e precisamente quello in cui procede la scansione dell'array durante una iterazione) e ''lentamente'' nell'altro verso. Per esempio, se l'array viene scandito in avanti e i numeri vengono disposti in ordine crescente, i numeri grandi si sposteranno avanti velocemente, quelli piccoli si sposteranno indietro lentamente. Possiamo chiarire meglio questo concetto con questo esempio. Si consideri questo piccolo array:
| |||