Shaker sort

Questo algoritmo è noto anche come Bubble Sort Bidirezionale, Cocktail Sort, Cocktail Shaker Sort o Shuttle Sort. È stato sviluppato dalla Sun Microsystems.

Altro non è che una variazione del bubble sort, in cui l'indice del ciclo più interno, anzichè scorrere continuamente dall'inizio alla fine, si cambia direzione ad ogni ciclo.

Implementazioni

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);
    }
}

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;
}