Cocktail sort is a sorting algorithm, like comb sort, that attempts to improve the performance of bubble sort by eliminating turtles. Turtles are small numbers at the end of the unsorted list that slowly move to the front of the list one position at a time using bubble sort. Turtles greatly reduce the performance of bubble sort by increasing the number of passes bubble sort must make through the list. Although cocktail sort, comb sort, and bubble sort are considered impractical for use in real-world applications, there is a lot to gain from understanding them algorithmically in a computer science classroom.

Cocktail Sort and Bi-Directional Sorting

Bubble sort typically passes through the unsorted list unidirectionally from left-to-right, bubbling the next highest item to the end of the list. Any turtles in the list move 1 position to the left as they slowly migrate to their rightful position at the beginning of the list.

Cocktail sort eliminates turtles by sorting bidirectionally. The first pass in cocktail sort moves from left-to-right like bubble sort and moves the next highest item to the end of the list. The second pass moves in the opposite direction, from right-to-left, and moves the next lowest item (turtle) to the front of the list. By moving the turtles quickly to the front of the list on every other pass, cocktail sort hopes to improve the performance of bubble sort by reducing the overall number of passes.

Let's illustrate this using the same unsorted list as comb sort:

6 0 9 3 7 5 4 1 8 2

On the first pass, cocktail sort will move from left-to-right and move the largest value, 9, to the end of the list like bubble sort.

6 0 9 3 7 5 4 1 8 2 -> 0 6 3 7 5 4 1 8 2 9

On the second pass, cocktail sort will move from right-to-left and move the smallest value, 1, to the front of the list.

0 6 3 7 5 4 1 8 2 9 -> 0 1 6 3 7 5 4 2 8 9

This bidirectional (cocktail shaker) movement will continue until no swaps occur in either direction. At this point the list is sorted.

Cocktail Sort in Python

Below is an implementation of cocktail sort in Python. Notice the bidirectional movement of the algorithm as it moves large values to the end of the list and small values to the beginning of the list in a repeated fashion until no swap occurs in either direction.

def cocktail_sort(lst):
    """
    Performs in-place Cocktail Sort.

    :param lst: lst of integers.
    :return: None

    >>> lst = [6, 0, 9, 3, 7, 5, 4, 1, 8, 2]
    >>> cocktail_sort(lst)
    >>> assert(lst == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
    """
    if lst is None or len(lst) < 2:
        return

    length = len(lst)
    j = 0

    swap_occurred = True

    while swap_occurred:
        swap_occurred = False

        # Move Left-to-Right
        for i in range(length - 1 - j):
            if lst[i] > lst[i+1]:
                lst[i], lst[i+1] = lst[i+1], lst[i]
                swap_occurred = True

        if not swap_occurred:
            return

        swap_occurred = False

        # Move Right-to-Left
        for i in range(length - 1 - j, 0, -1):
            if lst[i] < lst[i-1]:
                lst[i], lst[i-1] = lst[i-1], lst[i]
                swap_occurred = True

        j += 1

Conclusion

By understanding cocktail sort you better understand bubble sort. From a computer science and algorithm perspective you can better understand how and why computer scientists have tried to improve the bubble sort algorithm. In reality, one wouldn't use cocktail sort for performance reasons, but cocktail sort, comb sort, and bubble sort have uses in the computer science classroom to help students think algorithmically.

Posted by David Hayden

David Hayden enjoys writing and teaching computer science. Many of the tutorials on KoderDojo involve data structures and algorithms in a variety of languages, including C#, Java, JavaScript, and Python. In addition to computer science, David is learning statistics and data science using Python and R. You can visit David on twitter at @KoderDojo.

Related Posts: