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:
“Generally there is no consistent evidence of significant differences in school achievement between children of working and nonworking mothers, but differences that do appear are often related to maternal satisfaction with her chosen role, and the quality of substitute care.”
—Ruth E. Zambrana, U.S. researcher, M. Hurst, and R.L. Hite. “The Working Mother in Contemporary Perspectives: A Review of Literature,” Pediatrics (December 1979)
“While this America settles in the mould of its vulgarity, heavily
thickening to empire,
And protest, only a bubble in the molten mass, pops and sighs out,
and the mass hardens,”
—Robinson Jeffers (1887–1962)
“There are a sort of men whose visages
Do cream and mantle like a standing pond,
And do a willful stillness entertain,
With purpose to be dressed in an opinion
Of wisdom, gravity, profound conceit,
As who should say, “I am Sir Oracle,
And when I ope my lips let no dog bark!””
—William Shakespeare (1564–1616)