Cocktail Sort

Cocktail sort is a minor modification of bubble sort. It differs in that instead of repeatedly running through the list from bottom to top, it passes alternately from bottom to top and then from top to bottom. It can carry out slightly better performance than a standard bubble sort.
Cocktail sort is less than two times faster than bubble sort. Another optimization can be that the algorithm remembers where the last actual swap has been done. In the next iteration, there will be no swaps beyond this limit and the algorithm has shorter passes. Cocktail sort goes bidirectionally, the range of possible swaps, which is the range to be tested, will reduce per pass, thus reducing the overall running time slightly.

##
# Python's algorithm of Cocktail sort


def cocktail(a):
    for i in range(len(a)//2):
        swap = False
        for j in range(1+i, len(a)-i):
            # test whether the two elements are in the wrong order
            if a[j] < a[j-1]:
                # let the two elements change places
                a[j], a[j-1] = a[j-1], a[j]
                swap = True
        # we can exit the outer loop here if no swaps occurred.
        if not swap:
            break
        swap = False
        for j in range(len(a)-i-1, i, -1):
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
                swap = True
        if not swap:
            break

num_list = [75, 16, 55, 19, 48, 14, 2, 61, 22, 100]
print("Before: ", num_list)
cocktail(num_list)
print("After:  ", num_list)

Sample output of above program.

C:\programs\algorithms>pep8 --first example.py

C:\programs\algorithms>python example.py
Before: [75, 16, 55, 19, 48, 14, 2, 61, 22, 100]
After: [2, 14, 16, 19, 22, 48, 55, 61, 75, 100]

C:\programs\algorithms>

Python Programming

Cocktail Sort

Sample output of above program.