Implementazioni di algoritmi/Shaker sort

Wikibooks, manuali e libri di testo liberi.

Sommario
Categoria · Copertina · Sviluppo · modifica il template

Copertina Implementazioni di algoritmi/Copertina


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.

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.

Indice

[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

[modifica] Altri progetti

Ricavato da "http://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Shaker_sort"
Strumenti personali