## Cocktail Sort

Back to Programming

### Description

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 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:

### Algorithm

``````INPUT: An unsorted array [98,34,12,.........,n]
OUTPUT: A sorted array[12,34,...............,n]

PROCESS:
Step 1: [Take the inputs from the user]

For i=0 to n repeat

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
``````

### Code

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.

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.