Cocktail sort is a comparison and exchange based sorting algorithm. It is also known as bidirectional sort algorithm. The Cocktail sort algorithm works same as bubble sort , it only differs from bubble sort that it sorts in both directions on each pass through the list. After sorting from beginning to end , the cocktail sort start sorting from end to beginning quickly. Here is pictorial representation that will help to understand.

Cocktail sort algorithm

 cock1

C implementation of cocktail sort.

#include<stdio.h>
#include<stdbool.h>

void print (int *list, int size);
void
cocktailSort (int *A, int size)
{
  // begin and end marks the first and last index to check
  int begin = -1;
  int end = size - 1;
  int i = 0;
  int tmp = 0;

  bool swapped = false;
  do
    {
      swapped = false;
      // increases begin because the elements before begin are in correct order
      begin = begin + 1;
      for (i = 0; i < end; i++)
	{
	  if (A[i] > A[i + 1])
	    {
	      tmp = A[i];
	      A[i] = A[i + 1];
	      A[i + 1] = tmp;
	      swapped = true;
	    }
	}
      if (swapped == false)
	break;

      swapped = false;
      // decreases end because the elements after end are in correct order
      end = end - 1;
      for (i = end; i >= 0; i--)
	{
	  if (A[i] > A[i + 1])
	    {
	      tmp = A[i];
	      A[i] = A[i + 1];
	      A[i + 1] = tmp;
	      swapped = true;
	    }
	}
    }while (swapped);

}

int main ()
{
	int list[] = { 6, 7, 3, 2, 4, 1 };
	int size = sizeof (list) / sizeof (list[0]);
       // print input list
        printf("the list is: ");
        print(list,size);
        // call cocktailSort
	cocktailSort (list, size);
       // print output
        printf("the sorted list is: ");
        print(list,size);
	return 0;
}
void
print (int *list, int size)
{
  int i = 0;
  for (i; i < size; i++)
    printf ("%d ", list[i]);

  printf ("\n");
}

Ref:

http://en.wikipedia.org/wiki/Cocktail_sort



Related Contents to follow