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.

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");
}
[/crayon]

Ref:

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