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;
Rating (4): 5

See also

Comments





farzana akterJan 31, 2014
Hello i need insertion best case program in java . please some one helps me to do the program