Shaker sort: differenze tra le versioni

Versione delle 20:31, 3 feb 2006

Versione delle 18:51, 2 ago 2006

Riga 1:

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

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