Shaker sort

Shaker sort (cocktail sort, shake sort) is a stable sorting algorithm with quadratic asymptotic complexity $O(n^{2})$ . Shakersort is a bidirectional version of bubble sort.

Description

Shaker sort unlike bubble sort orders the array in both directions. Hence every iteration of the algorithm consists of two phases. In the first one the lightest bubble ascends to the end of the array, in the second phase the heaviest bubble descends to the beginning of the array.

This way an imperfection of bubble sort – the problem of rabbits and turtles – is mitigated. The problem of rabbits and turtles is a situation in bubble sort, when a heavy bubble is placed at the end of the array. While the light bubbles (rabbits) are ascending rapidly, the heavy bubble (turtle) descends only one position per each iteration.

Visualization

Code

/**
 * Shaker sort (bidirectional bubble sort)
 * Orders in descending order
 * @param array array to be sorted
 */
public static void shakerSort(int[] array) {
    for (int i = 0; i < array.length/2; i++) {
        boolean swapped = false;
        for (int j = i; j < array.length - i - 1; j++) {
            if (array[j] < array[j+1]) {
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                swapped = true;
            }
        }
        for (int j = array.length - 2 - i; j > i; j--) {
            if (array[j] > array[j-1]) {
                int tmp = array[j];
                array[j] = array[j-1];
                array[j-1] = tmp;
                swapped = true;
            }
        }
        if(!swapped) break;
    }
}

/**
 * Shaker sort (bidirectional bubble sort)
 * Orders in descending order
 * @param array array to be sorted
 * @param size length of the array
 */
void shakerSort(int array[], int size) {
    for (int i = 0; i < size/2; i++) {
        bool swapped = false;
        for (int j = i; j < size - i - 1; j++) { //one way
            if (array[j] < array[j+1]) {
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                swapped = true;
            }
        }
        for (int j = size - 2 - i; j > i; j--) { //and back
            if (array[j] > array[j-1]) {
                int tmp = array[j];
                array[j] = array[j-1];
                array[j-1] = tmp;
                swapped = true;
            }
        }
        if(!swapped) break; //block (break if no element was swapped - the array is sorted)
    }
}

/**
 * Shaker sort (bidirectional bubble sort)
 * Orders in descending order
 * @param array array to be sorted
 */
public static void ShakerSort(int[] array)
{
    for (int i = 0; i < array.Length / 2; i++)
    {
        bool swapped = false;
        for (int j = i; j < array.Length - i - 1; j++)
        {
            if (array[j] < array[j + 1])
            {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
                swapped = true;
            }
        }
        for (int j = array.Length - 2 - i; j > i; j--)
        {
            if (array[j] > array[j - 1])
            {
                int tmp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

procedure ShakeSort(var X : ArrayType; N : integer);
var
  L,
  R,
  K,
  J : integer;
begin
  L := 2;
  R := N;
  K := N;
  repeat
    for J := R downto L do
      if (X[J] < X[J - 1]) then
        begin
          Swap(X[J], X[J - 1]);
          K := J
        end;
    L := K + 1;
    for J := L to R do
      if (X[J] < X[J - 1]) then
        begin
          Swap(X[J], X[J - 1]);
          K := J
        end;
    R := K - 1;
  until L >= R
end;
 
procedure Swap(var X, Y : integer);
var
  Temp : integer;
begin
  Temp := X;
  X := Y;
  Y := Temp
end;

Description

Visualization

Code

Doporučujeme