C++ Program to Perform the Shaker Sort

Shaker sort is a variation of bubble sort and is both a stable and comparison based sorting algorithm. The shaker sort is also known as cocktail sort or bidirectional bubble sort as it sorts the array in both directions.

In this article, we have an unsorted array. Our task is to implement the shaker sort in C++ to sort the given array.

Example

The following example sorts the unsorted array using the shaker sort:

Input:
array = {5, 1, 4, 2, 8, 0, 2}

Output:
Sorted array = {0, 1, 2, 2, 4, 5, 8}

The explanation of the above example to sort the given array using shaker sort is as follows:

array = {5, 1, 4, 2, 8, 0, 2}

ROUND 1: Forward Pass
Pass 1: {1, 5, 4, 2, 8, 0, 2} (Since, 5 > 1)
Pass 2: {1, 4, 5, 2, 8, 0, 2} (Since, 5 > 4)
Pass 3: {1, 4, 2, 5, 8, 0, 2} (Since, 5 > 2)
Pass 4: {1, 4, 2, 5, 8, 0, 2} (No change, 5 < 8)
Pass 5: {1, 4, 2, 5, 0, 8, 2} (Since, 8 > 0)
Pass 6: {1, 4, 2, 5, 0, 2, 8} (Since, 8 > 2)
After round 1 forward pass: {1, 4, 2, 5, 0, 2, 8}

ROUND 1: Backward Pass
Pass 1: {1, 4, 2, 5, 0, 2, 8} (No change, 2 < 8)
Pass 2: {1, 4, 2, 5, 0, 2, 8} (No change, 0 < 2)
Pass 3: {1, 4, 2, 0, 5, 2, 8} (Since, 5 > 0)
Pass 4: {1, 4, 0, 2, 5, 2, 8} (Since, 2 > 0)
Pass 5: {1, 0, 4, 2, 5, 2, 8} (Since, 4 > 0)
Pass 6: {0, 1, 4, 2, 5, 2, 8} (Since, 1 > 0)
After round 1 backward pass: {0, 1, 4, 2, 5, 2, 8}

Round 2:

array after ROUND 1: {0, 1, 4, 2, 5, 2, 8}
Forward Pass: 
Pass 1: {0, 1, 4, 2, 5, 2, 8} (No change, 0 < 1)
Pass 2: {0, 1, 4, 2, 5, 2, 8} (No change, 1 < 4)
Pass 3: {0, 1, 2, 4, 5, 2, 8} (Since, 4 > 2)
Pass 4: {0, 1, 2, 4, 5, 2, 8} (No change, 4 < 5)
Pass 5: {0, 1, 2, 4, 2, 5, 8} (Since, 5 > 2)
Pass 6: {0, 1, 2, 4, 2, 5, 8} (No change, 2 < 8)

After round 2 forward pass: {0, 1, 2, 4, 2, 5, 8}
Backward Pass:
Pass 1: {0, 1, 2, 4, 2, 5, 8} (No change, 5 < 8)
Pass 2: {0, 1, 2, 4, 2, 5, 8} (No change, 2 < 5)
Pass 3: {0, 1, 2, 2, 4, 5, 8} (Since, 4 > 2)
Pass 4: {0, 1, 2, 2, 4, 5, 8} (No change, 2 = 2)
Pass 5: {0, 1, 2, 2, 4, 5, 8} (No change, 1 < 2)
Pass 6: {0, 1, 2, 2, 4, 5, 8} (No change, 0 < 1)

After round 2 backward pass: {0, 1, 2, 2, 4, 5, 8}

Sorted array: {0, 1, 2, 2, 4, 5, 8}

Steps to Implement Shaker Sort in C++

The following steps implements the shaker sort to sort the given array.

• We have used the shakerSort() function to perform the sorting. It accepts an array and number of elements as arguments.
• We have defined the lowest and highest bound i.e. j = i+1 and k = m-1 respectively. The lowest bound j is used in forward pass and the highest bound for the backward pass.
• We compare the adjacent elements and check the condition if the left element is > the right element.
• If the left element is greater than the right element, we swap the elements using the swap() function.
• We check the above condition in both forward and backward passes. Each forward pass fixes the highest element at the end of the array, so we decrease the range with m--.
• Each backward pass fixes the smallest element from the beginning of the array, so we increase the starting pointer.
• Repeat the above steps until complete array is sorted.

C++ Implementation of Shaker Sort

Here is the C++ implementation of the above steps to implement the shaker sort:

#include<iostream>
using namespace std;

void swap(int *a, int *b) {
   int temp = *a;
   *a = *b;
   *b = temp;
}

void shakerSort(int a[], int m) {
   int i, j, k;
   for(i = 0; i < m;) {
      for(j = i+1; j < m; j++) {
         if(a[j] < a[j-1])
            swap(&a[j], &a[j-1]);
      }
      m--;
      for(k = m-1; k > i; k--) {
         if(a[k] < a[k-1])
            swap(&a[k], &a[k-1]);
      }
      i++;
   }
}

int main() {
   int a[] = {5, 1, 4, 2, 8, 0, 2};
   int n = sizeof(a)/sizeof(a[0]);
   
   cout << "Original Array: ";
   for (int i = 0; i < n; i++)
      cout << a[i] << " ";

   shakerSort(a, n);

   cout << "\nSorted Data: ";
   for (int i = 0; i < n; i++)
      cout << a[i] << " ";
   return 0;
}

The output of the above code is as follows:

Original Array: 5 1 4 2 8 0 2 
Sorted Data: 0 1 2 2 4 5 8