Differences From Bubble Sort
Cocktail sort is a slight variation of bubble sort. It differs in that instead of repeatedly passing through the list from bottom to top, it passes alternately from bottom to top and then from top to bottom. 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.
An example of a list that proves this point is the list (2,3,4,5,1), which would only need to go through one pass of cocktail sort to become sorted, but if using an ascending bubble sort would take four passes. However one cocktail sort pass should be counted as two bubble sort passes. Typically 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. As the 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.
Read more about this topic: Cocktail Sort
Famous quotes containing the words differences, bubble and/or sort:
“The mother must teach her son how to respect and follow the rules. She must teach him how to compete successfully with the other boys. And she must teach him how to find a woman to take care of him and finish the job she began of training him how to live in a family. But no matter how good a job a woman does in teaching a boy how to be a man, he knows that she is not the real thing, and so he tends to exaggerate the differences between men and women that she embodies.”
—Frank Pittman (20th century)
“Then a soldier,
Full of strange oaths, and bearded like the pard,
Jealous in honor, sudden, and quick in quarrel,
Seeking the bubble reputation
Even in the cannon’s mouth.”
—William Shakespeare (1564–1616)
“English people apparently queue up as a sort of hobby. A family man might pass a mild autumn evening by taking the wife and kids to stand in the cinema queue for a while and then leading them over for a few minutes in the sweetshop queue and then, as a special treat for the kids, saying “Perhaps we’ve time to have a look at the Number Thirty-One bus queue before we turn in.””
—Calvin Trillin (b. 1940)