Cocktail Shaker Sort / Bidirectional bubble sort

Cocktail Sort is a variation of Bubble sort. The Bubble sort algorithm always traverses elements from left and moves the largest element to its correct position in first iteration and second largest in second iteration and so on. Cocktail Sort traverses through a given array in both directions alternatively.

Algorithm

Each iteration of the algorithm is broken up into 2 stages:

1)The first stage loops through the array from left to right, just like the Bubble Sort. During the loop, adjacent items are compared and if value on the left is greater than the value on the right, then values are swapped. At the end of first iteration, largest number will reside at the end of the array.

2)The second stage loops through the array in opposite direction- starting from the item just before the most recently sorted item, and moving back to the start of the array. Here also, adjacent items are compared and are swapped if required.

Example

Let us consider an example array (6 2 5 3 9 1 3)

First Forward Pass :

(6 2 5 3 9 1 3) ? (2 6 5 3 9 1 3), Swap since 6 > 2
(2 6 5 3 9 1 3) ? (2 5 6 3 9 1 3), Swap since 6 > 5
(2 5 6 3 9 1 3) ? (2 5 3 6 9 1 3), Swap since 6 > 3
(2 5 3 6 9 1 3) ? (2 5 3 6 9 1 3)
(2 5 3 6 9 1 3) ? (2 5 3 6 1 9 3), Swap since 9 > 1
(2 5 3 6 1 9 3) ? (2 5 3 6 1 3 9), Swap since 9 > 3

After first forward pass, greatest element of the array will be present at the last index of array.

First Backward Pass :

(2 5 3 6 1 3 9) ? (2 5 3 6 1 3 9)
(2 5 3 6 1 3 9) ? (2 5 3 1 6 3 9), Swap since 6 > 1
(2 5 3 1 6 3 9) ? (2 5 1 3 6 3 9), Swap since 3 > 1
(2 5 1 3 6 3 9) ? (2 1 4 3 6 3 9), Swap since 5 > 1
(2 1 5 3 6 3 9) ? (1 2 5 3 6 3 9), Swap since 2 > 1

After first backward pass, smallest element of the array will be present at the first index of the array.

Second Forward Pass :

(1 2 5 3 6 3 9) ? (1 2 5 3 6 3 9)
(1 2 5 3 6 3 9) ? (1 2 3 5 6 3 9), Swap since 5 > 3
(1 2 3 5 6 3 9) ? (1 2 3 5 6 3 9)
(1 2 3 5 6 3 9) ? (1 2 3 5 3 6 9), Swap since 6 > 3

Second Backward Pass :

(1 2 3 5 3 6 9) ? (1 2 3 3 5 6 9), Swap since 5 > 3

Now, the array is already sorted, but our algorithm doesn’t know if it is completed. The algorithm needs to complete this whole pass without any swap to know it is sorted.

(1 2 3 3 5 6 9) ? (1 2 3 3 5 6 9)
(1 2 3 3 5 6 9) ? (1 2 3 3 5 6 9)

Pseudo Code

procedure cocktailShakerSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 2 do:
     if A[ i ] > A[ i + 1 ] then // test whether the two elements are in the wrong order
        swap( A[ i ], A[ i + 1 ] ) // let the two elements change places
        swapped := true
      end if
    end for
    if not swapped then
      // we can exit the outer loop here if no swaps occurred.
      break do-while loop
    end if
    swapped := false
    for each i in length( A ) - 2 to 0 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped // if no elements have been swapped, then the list is sorted
end procedure

Implementation

C++


// C++ implementation of Cocktail Sort 
#include <bits/stdc++.h> 
using namespace std; 
// Sorts arrar a[0..n-1] using Cocktail sort 
void CocktailSort(int a[], int n) 
{ 
    bool swapped = true; 
    int start = 0; 
    int end = n - 1; 
    while (swapped) { 
        // reset the swapped flag on entering 
        // the loop, because it might be true from 
        // a previous iteration. 
        swapped = false; 
        // loop from left to right same as 
        // the bubble sort 
        for (int i = start; i < end; ++i) { 
            if (a[i] > a[i + 1]) { 
                swap(a[i], a[i + 1]); 
                swapped = true; 
            } 
        } 
        // if nothing moved, then array is sorted. 
        if (!swapped) 
            break; 
        // otherwise, reset the swapped flag so that it 
        // can be used in the next stage 
        swapped = false; 
        // move the end point back by one, because 
        // item at the end is in its rightful spot 
        --end; 
        // from right to left, doing the 
        // same comparison as in the previous stage 
        for (int i = end - 1; i >= start; --i) { 
            if (a[i] > a[i + 1]) { 
                swap(a[i], a[i + 1]); 
                swapped = true; 
            } 
        } 
        // increase the starting point, because 
        // the last stage would have moved the next 
        // smallest number to its rightful spot. 
        ++start; 
    } 
} 
/* Prints the array */
void printArray(int a[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        printf("%d ", a[i]); 
    printf("\n"); 
} 
// Driver code 
int main() 
{ 
    int arr[] = {6 ,2 ,5 ,3 ,9 ,1, 3 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    CocktailSort(a, n); 
    printf("Sorted array :\n"); 
    printArray(a, n); 
    return 0; 
}

Python


def cocktailSort(a): 
    n = len(a) 
    swapped = True
    start = 0
    end = n-1
    while (swapped == True): 
        # reset the swapped flag on entering the loop, 
        # because it might be true from a previous 
        # iteration. 
        swapped = False
        # loop from left to right same as the bubble 
        # sort 
        for i in range (start, end): 
            if (a[i] > a[i + 1]) : 
                a[i], a[i + 1]= a[i + 1], a[i] 
                swapped = True
        # if nothing moved, then array is sorted. 
        if (swapped == False): 
            break
        # otherwise, reset the swapped flag so that it 
        # can be used in the next stage 
        swapped = False
        # move the end point back by one, because 
        # item at the end is in its rightful spot 
        end = end-1
        # from right to left, doing the same 
        # comparison as in the previous stage 
        for i in range(end-1, start-1, -1): 
            if (a[i] > a[i + 1]): 
                a[i], a[i + 1] = a[i + 1], a[i] 
                swapped = True
        # increase the starting point, because 
        # the last stage would have moved the next 
        # smallest number to its rightful spot. 
        start = start + 1
# Driver code to test above 
a = [6 ,2 ,5 ,3 ,9 ,1, 3 ] 
cocktailSort(a) 
print("Sorted array is:") 
for i in range(len(a)): 
    print ("% d" % a[i])

Complexity

  • Worst case time complexity: Θ(n*n)
  • Average case time complexity: Θ(n*n)
  • Best case time complexity: Θ(n)
  • Space complexity: Θ(1)

Comparison with bubble sort

  1. Time complexities are same, but Cocktail performs better than Bubble Sort. Typically cocktail sort is less than two times faster than bubble sort.

  2. As the cocktail shaker sort goes bidirectionally, the range of possible swaps, which is the range to be tested, will reduce per pass, thus reducing the overall running time slightly.

Question

Is this a sorting in place algorithm? Yes No

It is definitely an "in-place" sorting algorithm as it doesn't uses any additional space which is as big as the original array.


This is a companion discussion topic for the original entry at http://iq.opengenus.org/cocktail-shaker-sort/