Shaker sort: differenze tra le versioni

Versione delle 20:02, 19 mar 2008

Versione delle 20:11, 30 ago 2008

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é 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]].''