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:
- 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.
- 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 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 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# 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
<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>
OutputSorted 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.
| Case | Complexity |
| Best Case | O(n) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
| Space | O(1) Auxiliary Space |
| Maximum number of Comparison | O(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 Elements | Unoptimized Bubble Sort | Optimized Bubble sort | Cocktail sort |
| 100 | 2ms | 1ms | 1ms |
| 1000 | 8ms | 6ms | 1ms |
| 10000 | 402ms | 383ms | 1ms |
Cocktail sort, also known as cocktail shaker sort or bidirectional bubble sort, is a variation of the bubble sort algorithm. Like the bubble sort algorithm, cocktail sort sorts an array of elements by repeatedly swapping adjacent elements if they are in the wrong order. However, cocktail sort also moves in the opposite direction after each pass through the array, making it more efficient in certain cases.
The basic idea of cocktail sort is as follows:
- Start from the beginning of the array and compare each adjacent pair of elements. If they are in the wrong order, swap them.
- Continue iterating through the array in this manner until you reach the end of the array.
- Then, move in the opposite direction from the end of the array to the beginning, comparing each adjacent pair of elements and swapping them if necessary.
- Continue iterating through the array in this manner until you reach the beginning of the array.
- Repeat steps 1-4 until the array is fully sorted.
Here's an example of cocktail sort in action, sorting an array of integers in ascending order:
Sure, here are some potential advantages and disadvantages of using the cocktail sort algorithm:
Advantages:
- Cocktail sort can be more efficient than bubble sort in certain cases, especially when the array being sorted has a small number of unsorted elements near the end.
- Cocktail sort is a simple algorithm to understand and implement, making it a good choice for educational purposes or for sorting small datasets.
Disadvantages:
- Cocktail sort has a worst-case time complexity of O(n^2), which means that it can be slow for large datasets or datasets that are already partially sorted.
- Cocktail sort requires additional bookkeeping to keep track of the starting and ending indices of the subarrays being sorted in each pass, which can make the
- algorithm less efficient in terms of memory usage than other sorting algorithms.
- There are more efficient sorting algorithms available, such as merge sort and quicksort, that have better average-case and worst-case time complexity than cocktail sort.
One example :
C++
#include <bits/stdc++.h>
using namespace std;
void cocktail_sort(vector<int>& arr) {
int n = arr.size();
bool swapped = true;
int start = 0;
int end = n - 1;
while (swapped) {
// Move from left to right
swapped = false;
for (int i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}
if (!swapped) {
break;
}
end--;
// Move from right to left
swapped = false;
for (int i = end - 1; i >= start; i--) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
swapped = true;
}
}
start++;
}
}
int main() {
vector<int> arr = {5, 2, 9, 3, 7, 6};
cocktail_sort(arr);
for (auto x : arr) {
cout << x << " ";
}
cout << endl;
return 0;
}
import java.util.Arrays;
public class CocktailSort {
public static void cocktailSort(int[] arr) {
int n = arr.length;
boolean swapped = true;
int start = 0;
int end = n - 1;
while (swapped) {
// Move from left to right
swapped = false;
for (int i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
end--;
// Move from right to left
swapped = false;
for (int i = end - 1; i >= start; i--) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
swapped = true;
}
}
start++;
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 7, 6};
cocktailSort(arr);
System.out.println(Arrays.toString(arr));
}
}
def cocktail_sort(arr):
n = len(arr)
swapped = True
start = 0
end = n - 1
while swapped:
# Move from left to right
swapped = False
for i in range(start, end):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
if not swapped:
break
end -= 1
# Move from right to left
swapped = False
for i in range(end - 1, start - 1, -1):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
swapped = True
start += 1
# Example usage
arr = [5, 2, 9, 3, 7, 6]
cocktail_sort(arr)
print(arr)
using System;
using System.Collections.Generic;
class CocktailSort {
static void Main(string[] args) {
List<int> arr = new List<int> {5, 2, 9, 3, 7, 6};
cocktailSort(arr);
foreach (var x in arr) {
Console.Write(x + " ");
}
Console.WriteLine();
}
static void cocktailSort(List<int> arr) {
int n = arr.Count;
bool swapped = true;
int start = 0;
int end = n - 1;
while (swapped) {
// Move from left to right
swapped = false;
for (int i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
Swap(arr, i, i + 1);
swapped = true;
}
}
if (!swapped) {
break;
}
end--;
// Move from right to left
swapped = false;
for (int i = end - 1; i >= start; i--) {
if (arr[i] > arr[i + 1]) {
Swap(arr, i, i + 1);
swapped = true;
}
}
start++;
}
}
static void Swap(List<int> arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
function cocktail_sort(arr) {
let n = arr.length;
let swapped = true;
let start = 0;
let end = n - 1;
while (swapped)
{
// Move from left to right
swapped = false;
for (let i = start; i < end; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
if (!swapped) break;
end -= 1;
// Move from right to left
swapped = false;
for (let i = end - 1; i >= start; i--) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
start += 1;
}
return arr;
}
// Example usage
let arr = [5, 2, 9, 3, 7, 6];
cocktail_sort(arr);
console.log(arr);
Complexity Analysis :
The time complexity of Cocktail Sort is O(n^2) in the worst and average cases, where n is the number of elements in the array. This is because the algorithm iterates through the array multiple times, and in the worst case, each iteration involves comparing every element to its neighbor and possibly swapping them.
The best case time complexity is O(n) when the array is already sorted, but this is a rare case.
The space complexity of Cocktail Sort is O(1), which is constant. This is because the algorithm sorts the array in place, without using any extra memory.
References:
Similar Reads
Sorting Algorithms
A Sorting Algorithm is used to rearrange a given array or list of elements in an order. For example, a given array [10, 20, 5, 2] becomes [2, 5, 10, 20] after sorting in increasing order and becomes [20, 10, 5, 2] after sorting in decreasing order. There exist different sorting algorithms for differ
3 min read
Introduction to Sorting Techniques – Data Structure and Algorithm Tutorials
Sorting refers to rearrangement of a given array or list of elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of elements in the respective data structure. Why Sorting Algorithms are ImportantThe sorting algorithm is important in Com
3 min read
Most Common Sorting Algorithms
Selection Sort
Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly selecting the smallest (or largest) element from the unsorted portion and swapping it with the first unsorted element. This process continues until the entire array is sorted. First we find the smallest element a
8 min read
Bubble Sort Algorithm
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high. We sort the array using multiple passes. After the fi
8 min read
Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is like sorting playing cards in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. T
9 min read
Merge Sort - Data Structure and Algorithms Tutorials
Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the divide-and-conquer approach. It works by recursively dividing the input array into two halves, recursively sorting the two halves and finally merging them back together to obtain the sorted array. How do
14 min read
Quick Sort
QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array. It works on the principle of divide and conquer, breaking down the problem into s
13 min read
Heap Sort - Data Structures and Algorithms Tutorials
Heap sort is a comparison-based sorting technique based on Binary Heap Data Structure. It can be seen as an optimization over selection sort where we first find the max (or min) element and swap it with the last (or first). We repeat the same process for the remaining elements. In Heap Sort, we use
14 min read
Counting Sort - Data Structures and Algorithms Tutorials
Counting Sort is a non-comparison-based sorting algorithm. It is particularly efficient when the range of input values is small compared to the number of elements to be sorted. The basic idea behind Counting Sort is to count the frequency of each distinct element in the input array and use that info
9 min read