Sorting algorithm 8: Cocktail Sort

In this chapter we shall learn about below topics:

Cocktail sort can be considered as an extension to Bubble Sort Algorithm. As we know that in a bubble sort algorithm the larger number will move towards the right of the list. Then will again move towards the left of the list and again get the second largest element then move towards the right.

This bubble sort algorithm can be further optimized with the help of Cocktail Sort. Here instead of moving in one direction from left to right we move in the opposite direction right to left. Hence, once we move the largest element towards the right, while returning back to the initial position, we take the smallest element to the left.

Cocktail sort will be faster than bubble sort, but it will not change the complexity. The complexity will be still O(n^2).

Left to right:
{2, 6, 7, 4, 1, 8, 5, 3} 2 > 6? False
{2, 6, 4, 7, 1, 8, 5, 3} 6 > 4? True, swap
{2, 4, 6, 1, 7, 8, 5, 3} 6 > 1? True, swap
{2, 4, 1, 6, 7, 8, 5, 3} 6 > 7? False
{2, 4, 1, 6, 7, 5, 8, 3} 7 > 5? True, swap
{2, 4, 1, 6, 5, 7, 8, 3} 7 > 8? False
{2, 4, 1, 6, 5, 7, 8, 3} 8 > 3? True, swap
{2, 4, 1, 6, 5, 7, 3, 8} 

Now from right to left:
{2, 4, 1, 6, 5, 7, 3, 8}  3 < 7? True, swap
{2, 4, 1, 6, 5, 3, 7, 8}  3 < 5? True, swap
{2, 4, 1, 6, 3, 5, 7, 8}  3 < 6? True, swap
{2, 4, 1, 3, 6, 5, 7, 8}  3 < 1? False
{2, 1, 4, 3, 6, 5, 7, 8}  1 < 2? True, swap
{1, 2, 4, 3, 6, 5, 7, 8}  

Hence in the first pass, lowest element is at the left and highest element is at the right.

Left to Right
{1, 2, 4, 3, 6, 5, 7, 8} 1 > 2? False 
{1, 2, 4, 3, 6, 5, 7, 8} 2 > 4? False 
{1, 2, 4, 3, 6, 5, 7, 8} 4 > 3? True, swap 
{1, 2, 3, 4, 6, 5, 7, 8} 4 > 6? False
{1, 2, 3, 4, 6, 5, 7, 8} 6 > 5? True, swap
{1, 2, 3, 4, 5, 6, 7, 8} 6 > 7? False

Right to Left
{1, 2, 3, 4, 5, 6, 7, 8} 6 < 5? False 
{1, 2, 3, 4, 5, 6, 7, 8} 5 < 4? False 
{1, 2, 3, 4, 5, 6, 7, 8} 4 < 3? False 
{1, 2, 3, 4, 5, 6, 7, 8} 3 < 2? False 
{1, 2, 3, 4, 5, 6, 7, 8} 2 < 1? False 

Hence the array is sorted.

Our algorithm uses “is_swapped” variable to know if the array is sorted or not. A sorted array need not do any swapping. Hence taking that as a basis we terminate the main loop.

#include<stdio.h>
#include <stdbool.h> // for bool datatype in c


void swap(int *num_1, int *num_2)
{
	int temp;
	temp = *num_1;
	*num_1 = *num_2;
	*num_2 =  temp;
}

void CocktailSort(int arr[], int length)
{
	int min_index = 0;
	int max_index = length - 1;
	bool is_swapped = true; // initially we know the array is unsorted, hence set it to true
	int itr = 0;

	while(is_swapped)
	{
		// we set it to false, because in the previous iteration it might be true
		is_swapped = false;

		// sorting from left to right. At the end heigher element will be at the right
		for(itr = min_index; itr < max_index; itr++)
		{
			if (arr[itr] > arr[itr + 1])
			{
				swap(&arr[itr], &arr[itr +1 ]);
				is_swapped = true; // we have swapped, hence changing the flag
			}
		}

		if(!is_swapped)
		{
			break; // if we did not swap the elements, then it is known that the array is sorted.
		}

		// we decrement "max_index" as we know that the highest element is at the right of the array
		max_index --; 

		// sorting from right to left. At the end lowest element will be at the left
		for(itr = max_index - 1 ; itr >= min_index; itr--)
		{
			if (arr[itr] > arr[itr + 1])
			{
				swap(&arr[itr], &arr[itr +1 ]);
				is_swapped = true; // we have swapped, hence changing the flag
			}
		}

		// increment the min_index, as lowest element will be at the left of the array.
		min_index ++;
	}

}

void print_array(int arr[], int length)
{

	int itr = 0;

	printf("Sorted array is\n");

	for (itr = 0; itr < length; itr++)
	{
		printf("%d ", arr[itr]);
	}
	printf("\n");
}


int main()
{

	int arr [100] = {0};
	int length = 0;
	int itr = 0;

	printf("Enter the length of the array");
	scanf("%d", &length);

	for(itr = 0; itr < length; itr ++)
	{
		scanf("%d", &arr[itr]);
	}

	CocktailSort( arr, length);

	print_array(arr, length);


}

Enter the length of the array 4
4
3
2
1
Sorted array is
1 2 3 4

Time complexity is O(  n^2 ).