Skip to content
Related Articles

Related Articles

Cocktail Sort

View Discussion
Improve Article
Save Article
  • Difficulty Level : Easy
  • Last Updated : 19 Jul, 2022
View Discussion
Improve Article
Save Article

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 the first iteration and second-largest in the second iteration and so on. Cocktail Sort traverses through a given array in both directions alternatively. Cocktail sort does not go through the unnecessary iteration making it efficient for large arrays.

Cocktail sorts break down barriers that limit bubble sorts from being efficient enough on large arrays by not allowing them to go through unnecessary iterations on one specific region (or cluster) before moving onto another section of an array.
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 the value on the left is greater than the value on the right, then values are swapped. At the end of the first iteration, the 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 (5 1 4 2 8 0 2)

First Forward Pass: 
(5 1 4 2 8 0 2) ? (1 5 4 2 8 0 2), Swap since 5 > 1 
(1 5 4 2 8 0 2) ? (1 4 5 2 8 0 2), Swap since 5 > 4 
(1 4 5 2 8 0 2) ? (1 4 2 5 8 0 2), Swap since 5 > 2 
(1 4 2 5 8 0 2) ? (1 4 2 5 8 0 2) 
(1 4 2 5 8 0 2) ? (1 4 2 5 0 8 2), Swap since 8 > 0 
(1 4 2 5 0 8 2) ? (1 4 2 5 0 2 8), Swap since 8 > 2
After the first forward pass, the greatest element of the array will be present at the last index of the array.
First Backward Pass: 
(1 4 2 5 0 2 8) ? (1 4 2 5 0 2 8) 
(1 4 2 5 0 2 8) ? (1 4 2 0 5 2 8), Swap since 5 > 0 
(1 4 2 0 5 2 8) ? (1 4 0 2 5 2 8), Swap since 2 > 0 
(1 4 0 2 5 2 8) ? (1 0 4 2 5 2 8), Swap since 4 > 0 
(1 0 4 2 5 2 8) ? (0 1 4 2 5 2 8), Swap since 1 > 0
After the first backward pass, the smallest element of the array will be present at the first index of the array.
Second Forward Pass: 
(0 1 4 2 5 2 8) ? (0 1 4 2 5 2 8) 
(0 1 4 2 5 2 8) ? (0 1 2 4 5 2 8), Swap since 4 > 2 
(0 1 2 4 5 2 8) ? (0 1 2 4 5 2 8) 
(0 1 2 4 5 2 8) ? (0 1 2 4 2 5 8), Swap since 5 > 2
Second Backward Pass: 
(0 1 2 4 2 5 8) ? (0 1 2 2 4 5 8), Swap since 4 > 2
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. 
(0 1 2 2 4 5 8) ? (0 1 2 2 4 5 8) 
(0 1 2 2 4 5 8) ? (0 1 2 2 4 5 8)
Below is the implementation of the above algorithm :

C++




// C++ implementation of Cocktail Sort
#include <bits/stdc++.h>
using namespace std;
 
// Sorts array 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 a[] = { 5, 1, 4, 2, 8, 0, 2 };
    int n = sizeof(a) / sizeof(a[0]);
    CocktailSort(a, n);
    printf("Sorted array :\n");
    printArray(a, n);
    return 0;
}

Java




// Java program for implementation of Cocktail Sort
public class CocktailSort
{
    void cocktailSort(int a[])
    {
        boolean swapped = true;
        int start = 0;
        int end = a.length;
 
        while (swapped == true)
        {
            // reset the swapped flag on entering the
            // loop, because it might be true from a
            // previous iteration.
            swapped = false;
 
            // loop from bottom to top same as
            // the bubble sort
            for (int i = start; i < end - 1; ++i)
            {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    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 top to bottom, doing the
            // same comparison as in the previous stage
            for (int i = end - 1; i >= start; i--)
            {
                if (a[i] > a[i + 1])
                {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
 
            // increase the starting point, because
            // the last stage would have moved the next
            // smallest number to its rightful spot.
            start = start + 1;
        }
    }
 
    /* Prints the array */
    void printArray(int a[])
    {
        int n = a.length;
        for (int i = 0; i < n; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
 
    // Driver code
    public static void main(String[] args)
    {
        CocktailSort ob = new CocktailSort();
        int a[] = { 5, 1, 4, 2, 8, 0, 2 };
        ob.cocktailSort(a);
        System.out.println("Sorted array");
        ob.printArray(a);
    }
}

Python




# Python program for implementation of Cocktail Sort
 
 
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
a = [5, 1, 4, 2, 8, 0, 2]
cocktailSort(a)
print("Sorted array is:")
for i in range(len(a)):
    print("% d" % a[i])

C#




// C# program for implementation of Cocktail Sort
using System;
 
class GFG {
 
    static void cocktailSort(int[] a)
    {
        bool swapped = true;
        int start = 0;
        int end = a.Length;
 
        while (swapped == true) {
 
            // reset the swapped flag on entering the
            // loop, because it might be true from a
            // previous iteration.
            swapped = false;
 
            // loop from bottom to top same as
            // the bubble sort
            for (int i = start; i < end - 1; ++i) {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    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 top to bottom, doing the
            // same comparison as in the previous stage
            for (int i = end - 1; i >= start; i--) {
                if (a[i] > a[i + 1]) {
                    int temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
 
            // increase the starting point, because
            // the last stage would have moved the next
            // smallest number to its rightful spot.
            start = start + 1;
        }
    }
 
    /* Prints the array */
    static void printArray(int[] a)
    {
        int n = a.Length;
        for (int i = 0; i < n; i++)
            Console.Write(a[i] + " ");
        Console.WriteLine();
    }
 
    // Driver code
    public static void Main()
    {
        int[] a = { 5, 1, 4, 2, 8, 0, 2 };
        cocktailSort(a);
        Console.WriteLine("Sorted array ");
        printArray(a);
    }
}
 
// This code is contributed by Sam007

Javascript




<script>
    // Javascript program for implementation of Cocktail Sort
     
    function cocktailSort(a)
    {
        let swapped = true;
        let start = 0;
        let end = a.length;
  
        while (swapped == true) {
  
            // reset the swapped flag on entering the
            // loop, because it might be true from a
            // previous iteration.
            swapped = false;
  
            // loop from bottom to top same as
            // the bubble sort
            for (let i = start; i < end - 1; ++i) {
                if (a[i] > a[i + 1]) {
                    let temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    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 top to bottom, doing the
            // same comparison as in the previous stage
            for (let i = end - 1; i >= start; i--) {
                if (a[i] > a[i + 1]) {
                    let temp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = temp;
                    swapped = true;
                }
            }
  
            // increase the starting point, because
            // the last stage would have moved the next
            // smallest number to its rightful spot.
            start = start + 1;
        }
    }
  
    /* Prints the array */
    function printArray(a)
    {
        let n = a.length;
        for (let i = 0; i < n; i++)
            document.write(a[i] + " ");
        document.write("</br>");
    }
     
    let a = [ 5, 1, 4, 2, 8, 0, 2 ];
    cocktailSort(a);
    document.write("Sorted array :" + "</br>");
    printArray(a);
     
    // This code is contributed by decode2207.
</script>

Output

Sorted array :
0 1 2 2 4 5 8 

People have given many different names to cocktail sort:

  • Shaker Sort. 
  • Bi-Directional Sort.
  • Cocktail Shaker Sort.
  • Shuttle Sort.
  • Happy Hour Sort.
  • Ripple Sort.
CaseComplexity
Best CaseO(n)
Average CaseO(n2)
Worst CaseO(n2)
SpaceO(1) Auxiliary Space
Maximum number of ComparisonO(n2)

Sorting In Place: Yes
Stable: Yes
Comparison with Bubble Sort: 
Time complexities are the same, but Cocktail performs better than Bubble Sort. Typically cocktail sort is less than two times faster than bubble sort. Consider the example (2, 3, 4, 5, 1). Bubble sort requires four traversals of an array for this example, while Cocktail sort requires only two traversals. (Source Wiki)

Number of ElementsUnoptimized Bubble SortOptimized Bubble sortCocktail sort
1002ms1ms1ms
10008ms6ms1ms
10000402ms383ms1ms

References: 

This article is contributed by Rahul Agrawal. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above. 


My Personal Notes arrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!