Cocktail Sort

Cocktail Sort

Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuffle sort,[1] shuttle sort or happy hour sort, is a variation of bubble sort that is both a stable sorting algorithm and a comparison sort. The algorithm differs from a bubble sort in that it sorts in both directions on each pass through the list. This sorting algorithm is only marginally more difficult to implement than a bubble sort, and solves the problem of turtles in bubble sorts. It provides only marginal performance improvements, and does not improve asymptotic performance; like the bubble sort, it is not of practical interest (insertion sort is preferred for simple sorts), though it finds some use in education.

                         

Worst case performance	O (n^2)
Best case performance	O (n)
Average case performance	O (n^2)
Worst case space complexity	O (1)

   

Example

Sorting the list 6, 7, 1, 3, 2, 4:

671324

• Iteration 1                                                         

613247

612347

612347

162347

• Iteration 2

671324

617324

613724

613274

613247

• Iteration 3

126347

123647

123467

• Iteration 4

123467

123467

Algorithm

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