Sorting Algorithms: The Cocktail Sort
Welcome to the second post in my series on sorting algorithms. This time we're going to talk about a sort that most people haven't heard a great deal about: the Cocktail Sort.
This algorithm was the next logical choice in the series because it is very similar to the Bubble Sort in the way that it operates. If you're yet to read the first in the series, head over there now as it will make this algorithm easier to understand.
Fundamentally the algorithm is the same. The difference is that the Cocktail Sort iterates through a given data set in both directions when sorting. So let's break it down.
Common Terms
- Data set - the array or list of items that is to be sorted.
- n - the number of elements in the data set
The Algorithm
Each iteration of the algorithm is broken up into two stages.
The first stage loops through the data set from bottom to top, just like the Bubble Sort. During the loop, adjacent items are compared. If at any point the value on the left is greater than the value on the right, the items are swapped. At the end of the first iteration, the largest number will reside at the end of the set.
The second stage loops through the data set in the opposite direction - starting from the item just before the most recently sorted item, and moving back towards the start of the list. Again, adjacent items are swapped if required.
The Cocktail Sort also fits in the category of Exchange Sorts due to the manner in which elements are moved inside the data set during the sorting process.
The Example
We will use the same initial data set that we used for the Bubble Sort to aid in highlighting the differences.
The initial set looks like this:
33 98 74 13 55 20 77 45 64 83
The first iteration starts at the beginning of the list, comparing the first two items (marked in red):
33 98 74 13 55 20 77 45 64 83
Since 33 is less than 98, no swapping needs to be done as they're already in the correct order. So we move on to the next comparison:
33 98 74 13 55 20 77 45 64 83
This time a swap is required as 98 is greater than 74:
33 74 98 13 55 20 77 45 64 83
We do the same again, this time starting at the third item:
33 74 98 13 55 20 77 45 64 83
Again, we need to swap the items since they're not in order:
33 74 13 98 55 20 77 45 64 83
We repeat this process until we get to the end of the list (marked in green):
33 74 13 55 20 77 45 64 83 98
As was mentioned earlier, the result is that the largest number, 98 is placed at the end of the list. The next stage of the first iteration requires us to loop in the opposite direction. Since we know that 98 is in its rightful place, we start at the items immediately to the left:
33 74 13 55 20 77 45 64 83 98
We perform the same comparison as normal, and in this case we can see that we don't have to swap the items because 64 is less than 83. We move on to the next pair:
33 74 13 55 20 77 45 64 83 98
Again, we find that a swap is not necessary because 45 is less than 64. Moving down the list again we compare the previous pair:
33 74 13 55 20 77 45 64 83 98
This time we do want to swap the items, because 45 is less than 77, and hence the items are in the wrong order.
33 74 13 55 20 45 77 64 83 98
With the swap complete we again move to the previous pair:
33 74 13 55 20 45 77 64 83 98
Again, no swap needed, look at the previous pair:
33 74 13 55 20 45 77 64 83 98
These two are not in the right order, so swap them:
33 74 13 20 55 45 77 64 83 98
With the swap performed, we again move to the previous pair:
33 74 13 20 55 45 77 64 83 98
No swap needed, go to the previous pair:
33 74 13 20 55 45 77 64 83 98
These are out of order, so swap:
33 13 74 20 55 45 77 64 83 98
Finally we look at the last pair in this stage:
33 13 74 20 55 45 77 64 83 98
Again a swap is required:
13 33 74 20 55 45 77 64 83 98
We're now done with the second stage, and as we can see we have the highest and lowest values at the end and start of the set (respectively):
13 33 74 20 55 45 77 64 83 98
So at this point we're ready to iterate again, but we don't want to include the items that have already been sorted because we know they're in the right spot. Here's a short hand demo of both stages of the next iteration (remember, comparisons are in red, swaps are in blue, stores are in green):
13 33 74 20 55 45 77 64 83 98
13 33 74 20 55 45 77 64 83 98
13 33 20 74 55 45 77 64 83 98
13 33 20 74 55 45 77 64 83 98
13 33 20 55 74 45 77 64 83 98
13 33 20 55 74 45 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 64 77 83 98
13 33 20 55 45 74 64 77 83 98
13 33 20 55 45 64 74 77 83 98
13 33 20 55 45 64 74 77 83 98
13 33 20 55 45 64 74 77 83 98
13 33 20 45 55 64 74 77 83 98
13 33 20 45 55 64 74 77 83 98
13 33 20 45 55 64 74 77 83 98
13 20 33 45 55 64 74 77 83 98
13 20 33 45 55 64 74 77 83 98
The process repeats again. But this time as we iterate through, we can see that no swaps are required. The result after the next iterate is simple:
13 20 33 45 55 64 74 77 83 98
As we can see, using this algorithm to sort this particular data set results in less work than when using the Bubble Sort.
The Implementation
Here is a sample implementation written in C#. It is heavily commented in the hope that it will aid in understanding how the algorithm works:
/// <summary> /// Performs a cocktail sort on an array of integers. /// </summary> /// <param name="dataSet">An array of ints to be sorted.</param> static void CocktailSortBasic(int[] dataSet) { bool swapped = false; int start = 0; int end = dataSet.Length - 1; do { // make sure we reset the swapped flag on entering // the loop, because it might be true from a previous // iteration. swapped = false; // loop from bottom to top just like we do with // the bubble sort for (int i = start; i < end; ++i) { if (dataSet[i] > dataSet[i + 1]) { Swap(dataSet, i, i + 1); swapped = true; } } // if nothing moved, then we're sorted. if (!swapped) { break; } // otherwise, reset the swapped flag so that it // can be used in the next stage swapped = false; // move the end point back by one, because we know // that the item at the end is in its rightful spot --end; // this time we loop from top to bottom, doing the // same comparison as in the previous stage for (int i = end - 1; i >= start; --i) { if (dataSet[i] > dataSet[i + 1]) { Swap(dataSet, i, i + 1); swapped = true; } } // this time we increase the starting point, because // the last stage would have moved the next smallest // number to its rightful spot. ++start; } while (swapped); }
The Complexity
Both space and time complexity are the same as that of the Bubble Sort for exactly the same reasons. That is, time complexity is O(n2), and space complexity for in-place sorting is O(1).
A Note on Performance
The Cocktail Sort can actually prove to be faster than the Bubble Sort in a fair few cases. This is due to the fact that we sort in both directions each iteration instead of just one.
Here's an example data set which would require 9 iterations with a Bubble Sort, but only 1 iteration (of two stages) with a Cocktail Sort:
20 33 45 55 64 74 77 83 98 13
The second stage of the Cocktail Sort would simply move the number 13 all the way down to the start of the list, at which point the list is then sorted. The Bubble Sort would move the number 13 left one place for each iteration.
In general, the Cocktail Sort will perform, at worst, the same as the Bubble Sort.
Other Implementations
I'm slowly gathering a collection of implementations of all the sorting algorithms, including the ones listed above, that I'm covering in this series and posting them up on BitBucket. The Cocktail Sort implementations can be found here.
Note: You'll need Mercurial if you want to pull directly from the repository, otherwise you'll have to copy and paste from the web.
References and Other Information
Next up, we'll be looking at the Comb Sort.
Disclaimer
I'm no expert, nor an authority. The post above is based on my experience and a bit of research. If you find something wrong with anything I've said please let me know. Comments and feedback are greatly appreciated.
Note: For those reading this article in an RSS reader, you may find the colours do not appear in the examples properly. For some reason the feed is stripping out some of the formatting. I will do my best to fix this up soon.
-
OJ
-
OJ
