Shaker sort: differenze tra le versioni

Versione delle 14:21, 25 gen 2021

Versione attuale delle 17:08, 23 gen 2024

(3 versioni intermedie di 2 utenti non mostrate)

Riga 1:

{{Algoritmo

|classe = [[Algoritmo di ordinamento]]

|immagine =Sorting shaker sort anim.gif

|struttura dati = [[Array]]

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

Riga 7:

|ottimale = No

|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]]: 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]].

Riga 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.

==ShakersortEtimologia==

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.

Riga 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}}