/*
  Cocktail sort
  Sort a list whose first element has index 0.
  Public domain.
  Not tested.
*/

void swap(int *a, int *b)
{
   int temp = *a;
   *a = *b;
   *b = temp;	
}

function cocktailSort(int list[], int list_length) 
{
    int bottom = 0;
    int top = list_length - 1;
    bool swapped = true; 
    int i;

    while(swapped == true) // if no elements have been swapped, then the list is sorted
    {
        swapped = false; 
        for(i = bottom; i < top; i = i + 1)
        {
            if(list[i] > list[i + 1])  // test whether the two elements are in the correct order
            {
                swap(& list[i], & list[i + 1]); // let the two elements change places
                swapped = true;
            }
        }
        // decreases top the because the element with the largest value is now on the position top
        top = top - 1; 
        for(i = top; i > bottom; i = i - 1)
        {
            if(list[i] < list[i - 1]) 
            {
                swap(& list[i], & list[i - 1]);
                swapped = true;
            }
        }
        // increases bottom because the element with the smallest value is now on the position bottom
        bottom = bottom + 1;  
    }
}