If I have to sort an array, and I must choose between Bubble Sort and Cocktail Sort, is it always better to use Cocktail Sort, since it alternatively favors smaller and larger elements? If not, how should I decide which algorithm to use?

CodePudding user response：

is it always better to use Cocktail Sort

No. A counter example is [9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8]

Bubble Sort will need two passes to move the 10 and 9 to their final positions, and on the third pass it will see the array is sorted and quit (if this optimisation was implemented).

Cocktail Sort will move 10 to its final position in the first forward pass, will then perform the backward pass where 0 gets moved to its final position. In the next forward pass 9 is moved (further) to its final position, and then a backward pass follows that does nothing and so the algorithm can quit.

So Bubble sort made 3 passes and Cocktail 4 passes (2 forward 2 backward).

A more extreme example is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]

Bubble sort will need 10 or 11 passes to sort the array, while Cocktail sort will only need 3.

For a random array, Cocktail is expected to be a bit faster (or better: less slow). As noted at Wikipedia:

While it improves on bubble sort by more quickly moving items to the beginning of the list, it provides only marginal performance improvements.

...and:

It can achieve slightly better performance than a standard bubble sort. The reason for this is that bubble sort only passes through the list in one direction and therefore can only move items backward one step each iteration.

You asked:

If not, how should I decide which algorithm to use?

The difference is not significant. There are some categories of inputs for which it performs well. For instance, the above Wikipedia article mentions:

if every element is at a position that differs by at most