Hello YouTube, and welcome back to Sorting Algorithms
If you haven't already, please watch the first episode in this series
which will give you a clearer picture of the contents of this episode
As promised, we'll cover the cocktail sort today.
Also known as the Shaker sort, this sorting algorithm is actually an improvement of the bubble sort
which we covered in Episode 3, if you'd like to watch that first please click the link onscreen.
The principle in which the Cocktail sort works is exactly the same as Bubble sort does
It runs through the list and compares items in pairs.
In the case of an ascending-ordered list, the larger item within the pair should come after the smaller item.
If that is not so within a pair, they are swapped.
As we discussed in Episode Three, this poses a problem
While larger items, the rabbits, are quickly bubbled to the end of the list
smaller items, the turtles, usually only move one position in each pass.
The cocktail sort solves this problem by turning all items into rabbits.
You see, the only difference between Bubble sort and Cocktail sort, is that Bubble sort only moves in one direction down a list.
When it reaches the end, it goes to the top and sorts downwards again.
The cocktail sort, on the other hand, moves in both directions.
When it's done sorting from left to right, it sorts from right to left.
This causes the smallest values to be bubbled quickly towards the left
The same way the rabbits do in Bubble sorts!
Yes, that's right! In the forward pass, the small values are the turtles, while the large values are the rabbits.
However, in the backwards pass, the small values become the rabbits instead.
In each backward pass, a small value is also put in place at the start of the list
the same way a large value is put in place at the end of the list in Bubble sorts.
Since we've already covered most of the details in Episode 3, let's jump straight into the demonstration.
Notice that the algorithm is now going backwards in the list instead of forwards.
See? After the backwards pass is complete, the number "1" is put in its correct place.
The algorithm repeats itself from this point on, moving repeatedly forwards and backwards through the list
hence the name - It looks like a cocktail shaker in use!
And that's it!
Now, while the shaker sort does indeed make the bubble sort slightly more efficent
Now, while the shaker sort does indeed make the bubble sort slightly more efficent
unfortunately its time complexity according to the Big O Notation, is still n².
It does fare slightly better than Bubble sorts
but is still rather inefficent.
That's all there is for the cocktail sort - Hang around!
In the next episode, we'll cover one last inefficent sorting algorithm
and then finally move to the better ones!
Thank you for your continued support and don't go away just yet.
You're watching 0612 TV.
