Shaker sort
Da Wikipedia, l'enciclopedia libera.
In informatica lo Shaker sort, noto anche come Bubble Sort Bidirezionale, Cocktail Sort, Cocktail Shaker Sort o Shuttle Sort è un algoritmo 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à, ovvero O(n²), lo shakersort riduce la probabilità che l'ordinamento abbia un costo corrispondente al caso peggiore.
Nota: la comprensione di quanto segue richiede di avere compreso il funzionamento generale del bubblesort.
Indice |
[modifica] Motivazione
Il bubble sort ha una asimmetria intrinseca: i valori dell'array vengono spostati velocemente in un verso (e precisamente quello in cui procede la scansione dell'array durante una iterazione) e lentamente nell'altro verso. Per esempio, se l'array viene scandito in avanti e i numeri vengono disposti in ordine crescente, i numeri grandi si sposteranno avanti velocemente, quelli piccoli si sposteranno indietro lentamente. Possiamo chiarire meglio questo concetto con questo esempio. Si consideri questo piccolo array:
15 4 10 11 2
Durante la prima iterazione, il 15 viene ripetutamente spostato (vedi bubblesort), con il seguente risultato finale:
4 10 11 2 15
Si può quindi notare che nell'arco di una sola iterazione, il "15" (numero massimo che si trovava in prima posizione) ha attraversato l'intero array. Il "2", che si trovava in una situazione simmetrica (numero minimo in ultima posizione), ha invece percorso un solo passo verso la sua collocazione definitiva.
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.
[modifica] 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é 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.
Tutte le ottimizzazioni e le varianti previste per il bubblesort sono applicabili, con i dovuti adattamenti, anche allo shakersort.
[modifica] Implementazioni
[modifica] Java
class BidirBubbleSortAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception {
int j;
int limit = a.length;
int st = -1;
while (st < limit) {
boolean flipped = false;
st++;
limit--;
for (j = st; j < limit; j++) {
if (stopRequested) {
return;
}
if (a[j] > a[j + 1]) {
int T = a[j];
a[j] = a[j + 1];
a[j + 1] = T;
flipped = true;
pause(st, limit);
}
}
if (!flipped) {
return;
}
for (j = limit; --j >= st;) {
if (stopRequested) {
return;
}
if (a[j] > a[j + 1]) {
int T = a[j];
a[j] = a[j + 1];
a[j + 1] = T;
flipped = true;
pause(st, limit);
}
}
if (!flipped) {
return;
}
}
pause(st, limit);
}
}
[modifica] C++
void cocktail_sort (int A[], int n)
{
int left = 0, right = n;
bool finished;
do
{
finished = true;
--right;
for (int i = left; i < right; i++)
if (A[i] > A[i+1]) {
std::swap(A[i], A[i+1]);
finished = false;
}
if (finished) return; finished = true;
for (int i = right; i > left; i--)
if (A[i] < A[i-1]) {
std::swap(A[i], A[i-1]);
finished = false;
}
++left;
} while (!finished);
}
[modifica] Perl
sub cocktail_sort(@)
{
my @a = @_;
my ($left,$right) = (0,$#_);
while ($left < $right) {
foreach $i ($left..$right-1) {
($a[$i],$a[$i+1]) = ($a[$i+1],$a[$i]) if ($a[$i] > $a[$i+1]);
}
$right--;
foreach $i (reverse $left+1..$right) {
($a[$i],$a[$i-1]) = ($a[$i-1],$a[$i]) if ($a[$i] < $a[$i-1]);
}
$left++;
}
return @a;
}
[modifica] FORTRAN 77
SUBROUTINE cocktail_sort (A,LEN)
INTEGER A, LEN, COUNTR, TEMP
LOGICAL FLIP
DIMENSION A(LEN)
FLIP = .TRUE.
WHILE (FLIP) DO
COUNTR = 1
FLIP = .FALSE.
DO 16 COUNTR = 1, LEN - 1, 1
IF (A(COUNTR) .GT. A(COUNTR+1)) THEN
TEMP = A(COUNTR)
A(COUNTR) = A(COUNTR+1)
A(COUNTR+1) = TEMP
FLIP = .TRUE.
END IF
16 CONTINUE
COUNTR = LEN
DO 25 COUNTR = LEN, 2, -1
IF(A(COUNTR) .LT. A(COUNTR-1)) THEN
TEMP = A(COUNTR)
A(COUNTR) = A(COUNTR-1)
A(COUNTR-1) = TEMP
FLIP = .TRUE.
END IF
25 CONTINUE
END WHILE
END
