Implementazioni di algoritmi/Shaker sort
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, cambia 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 caso peggiore.
Il nome dell'algoritmo (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 Shaker sort semplicemente alterna una scansione in avanti e una all'indietro.
Tutte le ottimizzazioni e le varianti previste per il Bubble sort sono implementabili, con i dovuti adattamenti, anche allo Shaker sort.
Implementazioni
[modifica | modifica sorgente] 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);
}
}
Implementazione, sempre in Java, di una variante ottimizzata dello Shaker sort basata sulle ottimizzazioni previste per il Bubble sort:
void shakerSort(int[] a) {
boolean swapped = true;
int n = a.length - 1;
int infLimit = 0;
int supLimit = 0;
int temp = 0;
int j = 0;
while (j < n && swapped) {
swapped = false;
for (int i = j; i < n; i++) {
if (a[i] > a[i + 1]) {
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
swapped = true;
supLimit = i;
}
}
if (swapped) {
swapped = false;
n = supLimit;
for (int i = n; i > j; i--) {
if (a[i] < a[i - 1]) {
temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
swapped = true;
infLimit = i;
}
}
j = infLimit;
}
}
}
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);
}
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;
}
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
Altri progetti
[modifica | modifica sorgente]
Wikipedia contiene una voce su questo algoritmo
