what is Cocktail Sort?

Cocktail Sort

Cocktail sort is the variation of Bubble Sort which traverses the list in both directions alternatively. It is different from bubble sort in the sense that, bubble sort traverses the list in forward direction only, while this algorithm traverses in forward as well as backward direction in one iteration.

Algorithm

In cocktail sort, one iteration consists of two stages:

1. The first stage loop through the array like bubble sort from left to right. The adjacent elements are compared and if left element is greater than the right element, then we swap those elements. The largest element of the list is placed at the end of the array in the forward pass.
2. The second stage loop through the array from the right most unsorted element to the left. The adjacent elements are compared and if right element is smaller than the left element then, we swap those elements. The smallest element of the list is placed at the beginning of the array in backward pass.

The process continues until the list becomes unsorted.

Example

Consider the array A : {8, 2, 3, 1, 9}. Sort the elements of the array using Cocktail sort.

Iteration 1:

Forward pass :

1.  compare 8 with 2; 8>2 → swap(8,2)  
2.   
3. A={2,8,3,1,9}  
4.   
5. Compare 8 with 3; 8>3 → swap(8,3)   
6.   
7. A={2,3,8,1,9}  
8.   
9. Compare 8 with 1; 8 > 1 → swap(8,1)   
10.   
11. A = {2,3,1,8,9}   
12.   
13. Compare 8 with 9; 8<9 → do not swap   

At the end of first forward pass: the largest element of the list is placed at the end.

1. A={2, 3, 1, 8, 9 }  

Backward pass:

1. compare 8 with 1; 8> 1 → do not swap  
2.   
3. A={2, 3, 1, 8, 9 }  
4. compare 1 with 3 ; 3>1 → swap(1,3)   
5.    
6. A={2, 1, 3, 8, 9 }  
7.   
8. compare 1 with 2 ; 2> 1 → swap(1,2)  
9.   
10. A={1, 2, 3, 8, 9}   

At the end of first backward pass; the smallest element has been placed at the first index of the array.

If we have a look at the list produced in the first step; we can find that the list has already been sorted in ascending order but the algorithm will process itself completely.

Complexity

Complexity	Best Case	Average Case	Worst Case
Time Complexity	O(n2)	O(n2)	O(n2)
Space Complexity			O(1)

C Program

1. #include <stdio.h>  
2. int temp;   
3. void Cocktail(int a[], int n)  
4. {  
5.     int is_swapped = 1;  
6.     int begin = 0,i;  
7.     int end = n - 1;  
8.    
9.     while (is_swapped) {  
10.         is_swapped = 0;  
11.      for (i = begin; i < end; ++i) {  
12.             if (a[i] > a[i + 1]) {  
13.             temp = a[i];  
14.         a[i]=a[i+1];  
15.         a[i+1]=temp;                  
16.         is_swapped = 1;  
17.             }  
18.         }  
19.  if (!is_swapped)  
20.             break;  
21.  is_swapped = 0;  
22.  for (i = end - 1; i >= begin; --i) {  
23.      if (a[i] > a[i + 1])   
24.     {  
25.           temp = a[i];  
26.       a[i]=a[i+1];  
27.       a[i+1]=temp;  
28.       is_swapped = 1;  
29.          }  
30.       }  
31.         ++begin;  
32.     }  
33. }  
34.    
35. int main()  
36. {  
37.     int arr[] = {0, 10, 2, 8, 23, 1, 3, 45},i;  
38.     int n = sizeof(arr) / sizeof(arr[0]);  
39.     Cocktail(arr, n);  
40.     printf("printing sorted array :\n");  
41.      for (i = 0; i < n; i++)  
42.         printf("%d ", arr[i]);  
43.     printf("\n");  
44.     return 0;  
45. }  

Output:

printing sorted array :
0 1 2 3 8 10 23 45 

---

C++ Program

1. #include <iostream>  
2. using namespace std;   
3. int temp;   
4. void Cocktail(int a[], int n)  
5. {  
6.     int is_swapped = 1;  
7.     int begin = 0,i;  
8.     int end = n - 1;  
9.    
10.     while (is_swapped) {  
11.         is_swapped = 0;  
12.      for (i = begin; i < end; ++i) {  
13.             if (a[i] > a[i + 1]) {  
14.             temp = a[i];  
15.         a[i]=a[i+1];  
16.         a[i+1]=temp;                  
17.         is_swapped = 1;  
18.             }  
19.         }  
20.  if (!is_swapped)  
21.             break;  
22.  is_swapped = 0;  
23.  for (i = end - 1; i >= begin; --i) {  
24.      if (a[i] > a[i + 1])   
25.     {  
26.           temp = a[i];  
27.       a[i]=a[i+1];  
28.       a[i+1]=temp;  
29.       is_swapped = 1;  
30.          }  
31.       }  
32.         ++begin;  
33.     }  
34. }  
35.    
36. int main()  
37. {  
38.     int arr[] = {0, 10, 2, 8, 23, 1, 3, 45},i;  
39.     int n = sizeof(arr) / sizeof(arr[0]);  
40.     Cocktail(arr, n);  
41.     cout <<"printing sorted array :\n";  
42.      for (i = 0; i < n; i++)  
43.         cout<<arr[i]<<" ";  
44.     cout<<"\n";  
45.     return 0;  
46. }  

Output:

printing sorted array :
0 1 2 3 8 10 23 45

---

Java Program

1. public class CocktailSort   
2. {  
3. static int temp;   
4. static void Cocktail(int a[], int n)  
5. {  
6.     boolean is_swapped = true;  
7.     int begin = 0,i;  
8.     int end = n - 1;  
9.    
10.     while (is_swapped) {  
11.         is_swapped = false;  
12.      for (i = begin; i < end; ++i) {  
13.             if (a[i] > a[i + 1]) {  
14.             temp = a[i];  
15.         a[i]=a[i+1];  
16.         a[i+1]=temp;                  
17.         is_swapped = true;  
18.             }  
19.         }  
20.  if (!is_swapped)  
21.             break;  
22.  is_swapped = false;  
23.  for (i = end - 1; i >= begin; --i) {  
24.      if (a[i] > a[i + 1])   
25.     {  
26.           temp = a[i];  
27.       a[i]=a[i+1];  
28.       a[i+1]=temp;  
29.       is_swapped = true;  
30.          }  
31.       }  
32.         ++begin;  
33.     }  
34. }  
35. public static void main(String[] args) {  
36.       
37.     int arr[] = {0, 10, 2, 8, 23, 1, 3, 45},i;  
38.     int n = arr.length;  
39.     Cocktail(arr, n);  
40.     System.out.println("printing sorted array :\n");  
41.      for (i = 0; i < n; i++)  
42.         System.out.print(arr[i]+" ");  
43.     System.out.println();  
44.     }  
45. }  

Output:

printing sorted array :

0 1 2 3 8 10 23 45

---

C# Program

1. using System;  
2. public class CocktailSort   
3. {  
4. static int temp;   
5. static void Cocktail(int[] a, int n)  
6. {  
7.     Boolean is_swapped = true;  
8.     int begin = 0,i;  
9.     int end = n - 1;  
10.    
11.     while (is_swapped) {  
12.         is_swapped = false;  
13.      for (i = begin; i < end; ++i) {  
14.             if (a[i] > a[i + 1]) {  
15.             temp = a[i];  
16.         a[i]=a[i+1];  
17.         a[i+1]=temp;                  
18.         is_swapped = true;  
19.             }  
20.         }  
21.  if (!is_swapped)  
22.             break;  
23.  is_swapped = false;  
24.  for (i = end - 1; i >= begin; --i) {  
25.      if (a[i] > a[i + 1])   
26.     {  
27.           temp = a[i];  
28.       a[i]=a[i+1];  
29.       a[i+1]=temp;  
30.       is_swapped = true;  
31.          }  
32.       }  
33.         ++begin;  
34.     }  
35. }  
36. public void Main() {  
37.       
38.     int[] arr = {0, 10, 2, 8, 23, 1, 3, 45};  
39.     int n = arr.Length,i;  
40.     Cocktail(arr, n);  
41.     Console.WriteLine("printing sorted array :\n");  
42.      for (i = 0; i < n; i++)  
43.         Console.Write(arr[i]+" ");  
44.   
45.     }  

Output:

printing sorted array :

0 1 2 3 8 10 23 45

---

Python Program

1. def Cocktail(a,n):  
2.     is_swapped = True;  
3.     begin = 0  
4.     end = n - 1;  
5.     while is_swapped:  
6.         is_swapped = False;  
7.         for i in range(begin,end):  
8.             if a[i] > a[i + 1]:  
9.                 temp = a[i];  
10.                 a[i]=a[i+1];  
11.                 a[i+1]=temp;  
12.                 is_swapped = True;  
13.         if not(is_swapped):  
14.             break;  
15.         is_swapped = False;  
16.         for i in range(end-1,begin-1,-1):  
17.             if a[i] > a[i + 1]:  
18.                 temp = a[i];  
19.                 a[i]=a[i+1];  
20.                 a[i+1]=temp;  
21.                 is_swapped = True;  
22.         ++begin;  
23. arr = [0, 10, 2, 8, 23, 1, 3, 45];  
24. n = len(arr);  
25. Cocktail(arr, n);  
26. print("printing sorted array :\n");  
27. for i in range(0,n):  
28.     print(arr[i]),  

Output:

printing sorted array :

0 1 2 3 8 10 23 45

---

Rust Program

1. fn main()  
2. {  
3.     let mut a :[i32;8] = [0, 10, 2, 8, 23, 1, 3, 45];  
4.    let mut is_swapped = true;  
5.     let mut  begin = 0;  
6.     let end = 7;  
7.    
8.     while is_swapped {  
9.         is_swapped = false;  
10.      for i in begin..end {  
11.             if a[i] > a[i + 1] {  
12.             let mut temp = a[i];  
13.             a[i]=a[i+1];  
14.             a[i+1]=temp;                  
15.             is_swapped = true;  
16.             }  
17.         }  
18.     if !is_swapped  
19.     {  
20.             break;  
21.     }  
22.     is_swapped = false;  
23.     for i in (begin..(end-1)).rev()  
24.     {  
25.         if a[i] > a[i + 1]  
26.         {  
27.           let mut temp = a[i];  
28.           a[i]=a[i+1];  
29.           a[i+1]=temp;  
30.           is_swapped =true;  
31.          }  
32.       }  
33.       begin=begin+1;  
34.     }  
35.     print!("printing sorted array :\n");  
36.     for i in 0..7  
37.     {  
38.         print!("{}",a[i]);      
39.     }  
40. }  

Output:

printing sorted array :
0 1 2 3 8 10 23 45

---

JavaScript Program

1. <html>  
2. <head>  
3.     <title>Cocktail Sort</title>  
4.     </head>  
5.         <body>  
6.             <script>  
7.                   
8. function Cocktail( a, n)  
9. {  
10.     var temp=0;   
11.     var is_swapped = 1;  
12.     var begin = 0;  
13.     var end = n - 1;  
14.    
15.     while (is_swapped) {  
16.         is_swapped = 0;  
17.      for (i = begin; i < end; ++i) {  
18.             if (a[i] > a[i + 1]) {  
19.             temp = a[i];  
20.         a[i]=a[i+1];  
21.         a[i+1]=temp;                  
22.         is_swapped = 1;  
23.             }  
24.         }  
25.     if (!is_swapped)  
26.             break;  
27.     is_swapped = 0;  
28.     for (i = end - 1; i >= begin; --i) {  
29.         if (a[i] > a[i + 1])   
30.     {  
31.           temp = a[i];  
32.       a[i]=a[i+1];  
33.       a[i+1]=temp;  
34.       is_swapped = 1;  
35.          }  
36.       }  
37.       beginbegin=begin+1;  
38.     }  
39. }  
40.   
41.     var txt = "<br>";  
42.     var arr = [0, 10, 2, 8, 23, 1, 3, 45];  
43.     var n = arr.length;  
44.     Cocktail(arr, n);  
45.     document.writeln("printing sorted array :\n"+txt);  
46.      for (i = 0; i < n; i++)  
47.      {  
48.          document.writeln(arr[i]+"/xa0");  
49.      }  
50. </script>  
51. </body>  
52. </html>  

Output:

printing sorted array :
0
1 2 3 8 10 23 45