Cocktail Sort Algorithm or Shaker Sort Algorithm

In this tutorial we look at another sorting algorithm named cocktail sort. Cocktail sort is a slight variation of bubble sort.

Many Names of Cocktail Sort

People have given many different names to cocktail sort, but they all the same. The following names are used:

• Shaker sort
• Bi-directional sort
• Cocktail shaker sort
• Shuttle sort
• Happy hour sort
• Ripple sort

Difference with Bubble sort

The difference between cocktail sort and bubble sort is that instead of repeatedly passing through the list from bottom to top, it passes alternately from bottom to top and then from top to bottom. The result is that it has a slightly better performance than bubble sort, because it sorts in both directions. (Bubble sort can only move items backwards one step per iteration.)

Normally cocktail sort or shaker sort pass (one time in both directions) is counted as two bubble sort passes. In a typical implementation the cocktail sort is less than two times faster than a bubble sort implementation.

Because you have to implement a loop in both directions that is changing each pass it is slightly more difficult to implement.

A Cocktail Sort or Shaker Sort Code Example

I hope you’ve already looked at the bubble sort tutorial so that you can compare the two.

Let’s look at a cocktail sort code example:

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

void cocktail_sort_shaker_sort(char *member, int no_times)
{
	register int i;
	int ready;
	char a;

	do
	{
		ready = 0;
		for(i = no_times - 1; i > 0; --i)
		{
			if(member[i - 1] > member[ i ])
			{
				a = member[i - 1];
				member[i - 1] = member[ i ];
				member[ i ] = a;
				ready = 1;
			}
		}
		for(i = 1; i < no_times; ++i)
		{
			if(member[i - 1] > member[ i ])
			{
				a = member[i - 1];
				member[i - 1] = member[ i ];
				member[ i ] = a;
				ready = 1;
			}
		}
	} while(ready);
}

int main(void)
{
	char my_string[255];
	printf("Please enter a string: ");
	gets(my_string);
	cocktail_sort_shaker_sort(my_string, strlen(my_string));
	printf("The result of the sort is %s\n", my_string);
	return 0;
}

Note: consider using gets_s instead of gets in your own implementation, because gets may not be save! (Potential buffer overflow vulnerability.)

Output example:

Please enter a string: 1532467890
The result of the sort is 0123456789

As you can see the function cocktail_sort_shaker_sort has three loops. Two for loops one for each direction and one do-while loop that checks if the sort is ready.

The algorithm is not that difficult so I assume that you can depict it yourself by taking two values (for instance 2 and 1) and walk each number through the source code. This way you can easily see what will happen.

That’s all for this programming algorithm tutorial.