Implementazioni di algoritmi/Shaker sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m ha spostato Shaker sort a Algoritmi/Shaker sort: convenzioni di nomenclatura |
link a pedia, template indice e interprogetto |
||
Riga 1:
{{algoritmi}}
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]].▼
▲In [[w:informatica|informatica]] lo '''Shaker sort''', noto anche come '''Bubble Sort Bidirezionale''', '''Cocktail Sort''', '''Cocktail Shaker Sort''' o '''Shuttle Sort''' è un [[w:algoritmo|algoritmo]] [[w:algoritmo di ordinamento|di ordinamento]] particolarmente indicato per l'ordinamento di [[w:array|array]], è stato sviluppato dalla [[w:Sun Microsystems|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, si cambia direzione ad ogni ciclo. Pur mantenendo la stessa [[complessità|complessità]], ovvero ''O(n²)'', lo shakersort riduce la probabilità che l'ordinamento abbia un costo corrispondente al [[analisi del caso peggiore|caso peggiore]].▼
▲Lo shaker sort è sostanzialmente una variante del [[w:bubble sort|bubble sort]] in cui l'indice del ciclo più interno, anziché scorrere continuamente dall'inizio alla fine, si cambia direzione ad ogni ciclo. Pur mantenendo la stessa [[w:complessità|complessità]], ovvero ''O(n²)'', lo shakersort riduce la probabilità che l'ordinamento abbia un costo corrispondente al [[analisi del caso peggiore|caso peggiore]].
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.
Line 26 ⟶ 10:
== Implementazioni ==
===[[w:Linguaggio di programmazione Java|Java]]===
<source lang="java">
class BidirBubbleSortAlgorithm extends SortAlgorithm {
Line 75 ⟶ 58:
</source>
===[[w:C++|C++]]===
<source lang="Cpp">
void cocktail_sort (int A[], int n)
Line 101 ⟶ 84:
</source>
===[[w:Perl|Perl]]===
<source lang="perl">
sub cocktail_sort(@)
Line 121 ⟶ 104:
</source>
===[[w:Fortran|FORTRAN 77]]===
<source lang="fortran">
SUBROUTINE cocktail_sort (A,LEN)
Line 152 ⟶ 135:
</source>
== Altri progetti ==
{{interprogetto|w=Shaker sort|w_etichetta=questo algoritmo}}
[[
{{Avanzamento|100%|4 marzo 2008}}
|