Sorting algorithms/Cocktail sort

Sorting algorithms/Cocktail sort
You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm
This is a sorting algorithm.   It may be applied to a set of data in order to sort it.     For comparing various sorts, see compare sorts.   For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts

Heap sort | Merge sort | Patience sort | Quick sort

O(n log²n) sorts
Shell Sort

O(n²) sorts
Bubble sort | Cocktail sort | Cocktail sort with shifting bounds | Comb sort | Cycle sort | Gnome sort | Insertion sort | Selection sort | Strand sort

other sorts
Bead sort | Bogo sort | Common sorted list | Composite structures sort | Custom comparator sort | Counting sort | Disjoint sublist sort | External sort | Jort sort | Lexicographical sort | Natural sorting | Order by pair comparisons | Order disjoint list items | Order two numerical lists | Object identifier (OID) sort | Pancake sort | Quickselect | Permutation sort | Radix sort | Ranking methods | Remove duplicate elements | Sleep sort | Stooge sort | [Sort letters of a string] | Three variable sort | Topological sort | Tree sort

The cocktail sort is an improvement on the Bubble Sort. The improvement is basically that values "bubble" both directions through the array, because on each iteration the cocktail sort bubble sorts once forwards and once backwards. Pseudocode for the algorithm (from the wikipedia):

procedure cocktailSort( A : list of sortable items ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 2 do:
      if A[ i ] > A[ i + 1 ] then // test whether the two elements are in the wrong order
        swap( A[ i ], A[ i + 1 ] ) // let the two elements change places
        swapped := true
      end if
    end for
    if swapped = false then
      // we can exit the outer loop here if no swaps occurred.
      break do-while loop
    end if
    swapped := false
    for each i in length( A ) - 2 to 0 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped // if no elements have been swapped, then the list is sorted
end procedure

ALGOL 68

MODE DATA = CHAR;
PROC swap = (REF DATA a,b)VOID:(
  DATA tmp:=a; a:=b; b:=tmp
);

PROC cocktail sort = (REF[]DATA a)VOID: (
  WHILE
    BOOL swapped := FALSE;
    FOR i FROM LWB a TO UPB a - 1 DO
      IF a[ i ] > a[ i + 1 ] THEN # test whether the two elements are in the wrong order #
        swap( a[ i ], a[ i + 1 ] ); # let the two elements change places #
        swapped := TRUE
      FI
    OD;
    IF swapped = FALSE THEN
      # we can exit the outer loop here if no swaps occurred. #
      break do while loop
    FI;
    swapped := FALSE;
    FOR i FROM UPB a - 1 TO LWB a DO
      IF a[ i ] > a[ i + 1 ] THEN
        swap( a[ i ], a[ i + 1 ] );
        swapped := TRUE
      FI
    OD;
# WHILE # swapped # if no elements have been swapped, then the list is sorted #
  DO SKIP OD;
  break do while loop: SKIP
);

[32]CHAR data := "big fjords vex quick waltz nymph";
cocktail sort(data);
print(data)

Output:

     abcdefghiijklmnopqrstuvwxyz

Alternatively - when the data records are large - the data can be manipulated indirectly, thus removing the need to actually swap large chunks of memory as only addresses are swapped.

MODE DATA = REF CHAR;
PROC swap = (REF DATA a,b)VOID:(
  DATA tmp:=a; a:=b; b:=tmp
);

PROC (REF[]DATA a)VOID cocktail sort;

[32]CHAR data := "big fjords vex quick waltz nymph";
[UPB data]DATA ref data;  FOR i TO UPB data DO ref data[i] := data[i] OD;
cocktail sort(ref data);
FOR i TO UPB ref data DO print(ref data[i]) OD; print(new line);
print((data))

Output:

     abcdefghiijklmnopqrstuvwxyz
big fjords vex quick waltz nymph

The above two routines both scan the entire width of the array, in both directions, even though the first and last elements of each sweep had already reached their final destination during the previous pass. The solution is to zig-zag, but have the sweeps converge on the centre element. This reduces the number of comparisons required by about 50%.

PROC odd even sort = (REF []DATA a)VOID: (
  FOR offset FROM 0 DO
    BOOL swapped := FALSE;
    FOR i FROM LWB a + offset TO UPB a - 1 - offset DO
      IF a[ i ] > a[ i + 1 ] THEN # test whether the two elements are in the wrong order #
        swap( a[ i ], a[ i + 1 ] ); # let the two elements change places #
        swapped := TRUE
      FI
    OD;
  # we can exit the outer loop here if no swaps occurred. #
    IF swapped = FALSE THEN break do od loop FI;
    swapped := FALSE;
    FOR i FROM UPB a - 1 - offset - 1 BY - 1 TO LWB a + offset DO
      IF a[ i ] > a[ i + 1 ] THEN
        swap( a[ i ], a[ i + 1 ] );
        swapped := TRUE
      FI
    OD;
  # if no elements have been swapped, then the list is sorted #
    IF swapped = FALSE THEN break do od loop FI;
  OD;
  break do od loop: SKIP
);

Java

This algorithm sorts in place. Call it with a copy of the array to preserve the unsorted order. <java>public static void cocktailSort( int[] A ){ boolean swapped; do{ swapped = false; for (int i =0; i<= A.length - 2;i++){ if (A[ i ] > A[ i + 1 ]) { //test whether the two elements are in the wrong order int temp = A[i]; A[i] = A[i+1]; A[i+1]=temp; swapped = true; } } if (!swapped) { //we can exit the outer loop here if no swaps occurred. break; } swapped = false; for (int i= A.length - 2;i>=0;i--){ if (A[ i ] > A[ i + 1 ]){ int temp = A[i]; A[i] = A[i+1]; A[i+1]=temp; swapped = true; } } //if no elements have been swapped, then the list is sorted } while (swapped); }</java>

Python

<python>def cocktailSort(data):

   swapped = True
   while swapped:
       swapped = False
       for i in xrange(len(data)-1):
           if data[i] > data[i+1]:
               data[i], data[i+1] = data[i+1], data[i]
               swapped = True
       if not swapped:
           break
       for i in xrange(len(data)-1, 0):
           if data[i] > data[i+1]:
               data[i], data[i+1] = data[i+1], data[i]
               swapped = True
   return data</python>