Shaker sort: differenze tra le versioni

Versione delle 09:39, 12 gen 2012

Versione attuale delle 17:08, 23 gen 2024

(14 versioni intermedie di 12 utenti non mostrate)

Riga 1:

{{Infobox Algoritmo

|classclasse = [[Algoritmo di ordinamento]]

|immagine =Sorting shaker sort anim.gif

|image=

|datastruttura dati = [[Array]]

|timetempo = ''О(n²)''

|spazio =

|space=

|optimalottimale = No

|completo =

|complete=

|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]] [[algoritmo di ordinamento|di ordinamento]] dei dati sviluppato dalla [[Sun Microsystems]]. Lo shaker sort è sostanzialmente una variante del [[bubble sort]]: si differenzia da quest'ultimo per l'indice del ciclo più interno che, anziché scorrere dall'inizio alla fine, inverte la sua direzione ad ogni ciclo. Pur mantenendo la stessa [[complessità]], ovvero ''O(n²)'', lo shaker sort riduce la probabilità che l'ordinamento abbia un costo corrispondente al [[analisi del caso peggiore|caso peggiore]].

''Nota: la comprensione di quanto segue richiede di avere compreso il funzionamento generale del [[bubble sort]].''

Riga 16:

La forma più semplice dello shaker sort scorre l'intera lista ad ogni passaggio (di seguito viene riportato il caso di ordinamento discendente):

'''procedure''' shackerSortshakerSort( 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 sononsono in ordine errato</span>

swap( A[ i ], A[ i + 1 ] ) <span style="color:green">// scambia di posto i 2 elementi</span>

swapped := true

Riga 42:

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:'''

'''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

Line 48 ⟶ 50:

'''do'''

swapped := false

<span style="color:green">// incremenetaincrementa `begin` perché gli elementi prima di `begin` sono ordinati correttamente</span>

begin := begin + 1

'''for each''' i '''in''' begin '''to''' end '''do:'''

Line 84 ⟶ 86:

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.

==Etimologia==

==Shakersort==

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é scorrere l'array sempre nello stesso verso (privilegiando quindi gli spostamenti di valori in quel verso), lo shaker sort semplicemente ''alterna'' una scansione in avanti e una all'indietro.

Line 91 ⟶ 92:

== Altri progetti ==

{{interprogetto|b=Implementazioni_di_algoritmi/Shaker_sort|b_oggetto=implementazioni|b_preposizione=didello}}

== Collegamenti esterni ==

* {{FOLDOC|cocktail shaker sort|cocktail shaker sort}}

{{ordinamento}}

{{portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]

[[cs:Koktejlové řazení]]

[[de:Shakersort]]

[[en:Cocktail sort]]

[[es:Ordenamiento de burbuja bidireccional]]

[[hu:Koktélrendezés]]

[[hy:Կոկտեյլային տեսակավորում]]

[[ja:シェーカーソート]]

[[ko:칵테일 정렬]]

[[pl:Sortowanie koktajlowe]]

[[pt:Cocktail sort]]

[[ru:Сортировка перемешиванием]]

[[tr:Kokteyl sıralaması]]

[[uk:Сортування змішуванням]]