FOR FREE CONTENT

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