Shaker sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
mNessun oggetto della modifica |
→Collegamenti esterni: Creato la sezione e aggiunto il template "FOLDOC" |
||
| (21 versioni intermedie di 16 utenti non mostrate) | |||
Riga 1:
{{
|
|immagine =Sorting shaker sort anim.gif
|
|
|spazio =
|
|completo =
|didascalia=Esecuzione dell'algoritmo}}
In [[informatica]] lo '''Shaker sort''', noto anche come '''Bubble sort bidirezionale''', '''Cocktail sort''', '''Cocktail shaker sort''', '''Ripple sort''', '''Happy hour sort''' o '''Shuttle sort''' è un [[algoritmo di ordinamento]] dei dati sviluppato dalla [[Sun Microsystems]]. Lo shaker sort è sostanzialmente una variante del [[bubble sort]]:
''Nota: la comprensione di quanto segue richiede di avere compreso il funzionamento generale del [[
==
La forma più semplice dello shaker sort scorre l'intera lista ad ogni passaggio (di seguito viene riportato il caso di ordinamento discendente):
'''procedure''' shakerSort( A ''':''' lista di elementi da ordinare ) '''defined as:'''
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:▼
'''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 sono 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]]).-->
<!-- (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">// incrementa `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
15 4 10 11 2
Durante la prima iterazione
4 10 11 2 15
Line 25 ⟶ 84:
Si può quindi notare che nell'arco di ''una sola'' iterazione, il "15" (numero massimo che si trovava in prima posizione) ha attraversato l'intero array. Il "2", che si trovava in una situazione simmetrica (numero minimo in ultima posizione), ha invece percorso un solo passo verso la sua collocazione definitiva.
In generale, un numero destinato alla posizione ''N'' e inizialmente collocato alla posizione ''M'', dove ''N''<''M'', richiederà ''M''-''N'' iterazioni per giungere alla sua cella di destinazione. Se invece ''M''<''N'', il suo spostamento sarà mediamente più rapido. Il caso particolare in cui il numero destinato alla prima posizione dell'array si trovi nell'ultima corrisponde a una situazione di "caso peggiore" del bubblesort, in cui saranno necessarie tutte le ''N''-1 iterazioni dell'algoritmo per ottenere l'array ordinato.
==
Il nome shaker sort (ordinamento "a shaker", con riferimento allo strumento per preparare i [[cocktail]]) suggerisce abbastanza chiaramente in cosa lo shaker sort modifichi il bubble sort. Anziché
Tutte le ottimizzazioni e le varianti previste per il
▲Il nome shaker sort (ordinamento "a shaker", con riferimento allo strumento per preparare i [[cocktail]]) suggerisce abbastanza chiaramente in cosa lo shaker sort modifichi il bubble sort. Anziché scandire l'array sempre nello stesso verso (privilegiando quindi gli spostamenti di valori in quel verso), lo shakersort semplicemente ''alterna'' una scansione in avanti e una all'indietro.
▲Tutte le ottimizzazioni e le varianti previste per il bubblesort sono applicabili, con i dovuti adattamenti, anche allo shakersort.
== Altri progetti ==
{{interprogetto|b=
== Collegamenti esterni ==
* {{FOLDOC|cocktail shaker sort|cocktail shaker sort}}
{{ordinamento}}
{{portale|informatica}}
[[Categoria:Algoritmi di ordinamento]]
| |||