Sorting Algorithms Redux 04: Cocktail Sort

We've seen bubble sort in action, but how can we make it even more efficient? Today, we look at a way to make bubble sort slightly faster!

- Intro Theme Adapted From -
Licensed under Creative Commons: By Attribution 3.0
ISRC: USUAN1100879

= 0612 TV =
0612 TV is your one stop for general geekery! Learn about a variety of technology-related subjects, including Photography, General Computing, Audio/Video Production and Image Manipulation! Enjoy your stay, and don't hesitate to drop me a comment or a personal message to my inbox =) If you like my work, don't forget to subscribe!

= NERDfirst =
NERDfirst is a project allowing me to go above and beyond YouTube videos into areas like app and game development. It will also contain the official 0612 TV blog and other resources.

-----

Disclaimer: Please note that any information is provided on this channel in good faith, but I cannot guarantee 100% accuracy / correctness on all content. Contributors to this channel are not to be held responsible for any possible outcomes from your use of the information.

[squirrelbrains]

i like precise and concise explanations, thanks for the video.

[NERDfirst]

Hello again!

The expression of time complexity is done in what's called the "Big O Notation", and one characteristic of such expression is that in general, coefficients and constant factors are discarded.

The reason why we do this is we want to consider how the algorithm performs on a large set (ie n approaches infinity).

So even if the time taken for something is 6n³ + 2n² + 3, under the Big O Notation we simply say it takes O(n³) time, since as n approaches infinity, only the "³" matters!

[NERDfirst]

You're very welcome! Glad you found my stuff useful =)

[NERDfirst]

Hello and thank you for your comment!

Cocktail sort is slightly faster than bubble sort, because it eliminates the "turtles" in bubble sort (large elements that take a long time to move towards the left, in an ascending sort). This does not change the Big O time complexity though - It's still an O(n²) algorithm.

Not sure if there are any disadvantages compared to bubble sort, but in general, it is of course still inefficient compared to say QuickSort which has O(n log n) time.

[NERDfirst]

Hello and thank you for your comment!

In general, best time refers to the least time for a sorting algorithm to finish its work. The naive implementation of cocktail sort will not have a difference between the two (both O(n²)), but if it was able to identify that no swaps have been made and to terminate, then the best case time is O(n), with a sorted list as input.

[NERDfirst]

+D Haugabook Thank you very much for your comment! I personally leave out the pseudocode to keep these episodes simple. After all, they are targetted at the absolute beginner, and it's more important for beginners to be able to picture the algorithms first, before anything else!

[NERDfirst]

Hello and thank you for your comment!

Indeed, as mentioned in the video, rigourously speaking, cocktail sort does not provide a better performance in comparison to bubblesort, as they are both O(n²) algorithms.

It's just that in some cases (eg sorting {2, 3, 4, 5, 1} in ascending order), cocktail sort requires far less comparisons to complete the job.

That of course, doesn't make it more efficient than O(n²), but there is indeed less computation, and hence is "faster".

[surajsajjala]

Too good, explained very easily, understandable

[Mytreya-maan]

wow, the explanations are truly precise!

[NERDfirst]

Hello again and many thanks for your comment! Glad you enjoyed =)

[NERDfirst]

Hello and thank you for your comment!

In the event that you need to write a program that needs to sort some data (whether directly for output, at the user's command, or as an intermediate step for another algorithm), the techniques shared here can be applied.

[skaniver]

Thank you :) :) that is perfect! wow what a interactive channel, definitely got my subscription, busy doing a semester project on all the sorts :) studying a BSC computer science :)

[ninav]

You´ve helped me a lot!
That´s what I was looking for

[NERDfirst]

Hello and thank you for your comment! Glad you enjoyed the video =)

[NERDfirst]

Hello again and thank you so much! Actually same here, I'm doing a degree program in computer science as well =P

[kyuchanao]

One case is 2n, then completing the whole thing is (2n)^2, which should be 4n^2, do we ignore the 4 in front of 4n^2 (so that the time complexity becomes n^2)?

[yaraalshahrani]

hello can you tellm me what the advantage and disadvantage for the cocktail sort

[enditend]

what's the differenece between best time and average?

[preciouswocha]

Thanks for the explanaton. Very precise as always. But I have a question. How do these algorithms, relate to coding?

[surgegraphicnovel]

This was very helpful. It would be great to also include pseudocode and flowchart examples. (I'm studying this in school.) Your explanation where great. I look forward to watching more videos from you.