The **cocktail sort** can be defined as the **variation of bubble sort**. In the case of bubble sort, the adjacent elements are compared from the beginning of the array and the maximum element will be stored at the proper sorted position after the first iteration. The 2nd largest element will be stored in its sorted position after the 2nd iteration and so on and we will get the sorted array. In the case of cocktail sort each iteration has two parts:

**1. **In the **first part**, the forward **comparison is taken place between the adjacent pairs of elements** which is exactly similar to the bubble sort and if the left item is greater than the right one, it will be swapped.

**2. **In the **2nd part**, the **backward comparison will be taken place from the right side to the left**. The comparison will start from the element just before the sorted element of the forward iteration. After this backward iteration, the minimum element will be sorted and positioned in the proper position.

After the first **backward comparison**,** the minimum element will be stored in the sorted position**, after 2nd time of backward comparison the 2nd smallest element will be stored in its sorted position, and so on.

Here, **in **the **case of **the **cocktail sort** one **flag variable is taken which is used to check whether there is any swapping in either the forward pass or in the backward pass**. If there is any swapping in any pass then it will go for the next iteration, otherwise, the iteration will be stopped.

It takes a half number of iterations than the bubble sort to sort the array elements.

**PROCEDURE WITH EXAMPLE:**

Suppose there is an array of **5 elements** as:

Now the array should be sorted in **ascending order**. The **flag will be set as false before starting the first iteration**.

__Iteration 1__:

__(Forward Pass) :__

In the first iteration, the **forward pass**** will be similar to the ****bubble sort**. And the comparisons will be as follows:

First **-5** and **7** are **compared**, as **7 ****(right element)** is **greater than** **-5** so there will be **no swapping**.

Now, **7** and **-8** is **compared **and as **-8** is **lesser than** **7** it will be **swapped** and the array will be:

And the **flag is set to true** as there is **swapping between the elements**.

After that **7** and **2 **will be **compared **and will be **swapped** so we get the array:

Lastly, **7** and **3** will be **compared** and will be **swapped** and the **1st forward pass will be completed**. After the 1st forward pass the array will be:

After the **1st forward pass**, the **maximum element**** of the array** is stored at its **right position** i.e. at the **last of the array**.

__(Backward Pass):__

Now the **1st backward pass** will be **started from the** **last index except the maximum element** **index** (one short from the last index) i.e.** 3. **

So, first **in the backward direction** **2** and** 3** will be **compared**. As the **left element **(**2**) is **smaller than** the **right element (****3****)** so there will be **no swapping**. And the array will remain the same:

Again **2**** will be compared with ****-8**, they are also in **ascending order** so there will be **no swapping**.

Now **-5**** and ****-8**** will be compared** and as they are **not in proper order** so they will be **swapped **and the **flag will be set to true**. The array after swapping will be:

As the **flag is true** then it will **go for the** **next iteration**.

In the **next iteration**,** the forward pass will be compared as similar to the bubble sort** as shown above but as there will be no swapping as the array is already sorted so it will come out from the loop without performing the backward pass.

**Sorted Array:**

```
INPUT: An unsorted array [98,34,12,.........,n]
OUTPUT: A sorted array[12,34,...............,n]
PROCESS:
Step 1: [Take the inputs from the user]
Read n
For i=0 to n repeat
Read a[i]
Step 2: [Sort the array elements]
Set st<-0
Set e<-n-1
Set flag<-true
while (flag=true) repeat
Set flag <- false
for i = st to e repeat
if a[i] > a[i + 1] then
Set tmp<-a[i]
Set a[i]<-a[i+1]
Set a[i+1]<-tmp
Set flag<- true
[End of ‘if’]
[End of ‘for’]
if (flag=false)
break
Set flag <- false
Set e<-e-1
` for i = e - 1 to st repeat
if a[i] > a[i + 1] then
Set tmp<-a[i]
Set a[i]<-a[i+1]
Set a[i+1]<-tmp
Set flag<- true
[End of ‘if’]
[End of ‘for’]
Set st=st+1
[End of ‘while’ loop]
Step 3: [Display the sorted array]
for i= 0 to n repeat
Print a[i]
Step 4: Stop
```

__CHARACTERISTICS:__

**1. **It is a comparison-based sorting algorithm.

**2. **It is an in-place sorting algorithm.

**3. **It is a variation of the bubble sort algorithm.

**4. **It traverses the array from left to right as well as from right to left which makes this sorting different from the bubble sort.

__TIME COMPLEXITY:__

The best-case complexity for **cocktail sort is ****O(n)**. If the array is already sorted only the forward pass for the 1st iteration takes place so there are** ****n - 1**** comparisons **to sort the n number of data.

Hence, **T(n) = n - 1**

The number of comparisons for the **worst case** when the array is in totally reversed order the maximum number of comparisons:

In the average case also the total number of comparisons will be more than n times and will be terminated in between or after the iteration where there will be no swapping.

__SPACE COMPLEXITY:__

The space complexity of this algorithm is **O(1)** as it **does not require any extra space **to sort the elements of the array.

__ADVANTAGES:__

**1.** The **cocktail sort **is **faster** than the bubble sort algorithm.

**2. **The best case complexity of cocktail sort is **O(n)** which is lesser than bubble sort.

**3. **It is an** in-place sorting** algorithm as it does not require any extra space to sort the data.

__DISADVANTAGES:__

**2. **It is less efficient than merge sort or quick sort algorithm

__APPLICATION:__

**1. **It can be used **instead of**** bubble sort** to reduce the time to sort the data.

Related

- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort using recursion
- Quicksort Iterative
- Merge Sort using recursion
- Merge Sort Iterative
- 3 way Merge Sort
- Heap Sort using recursion
- Heap Sort Iterative
- Radix Sort for positive integer
- Bucket Sort
- Counting Sort
- Intro Sort
- Minmax Sort
- List Sort
- Tree Sort
- Shell Sort
- Gnome sort
- Comb Sort
- Bitonic Sort
- Tim Sort