Sorting Algorithms Redux 04: Cocktail Sort

36
13



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!

Full Playlist Link:

– Intro Theme Adapted From –
Mechanolith Kevin MacLeod (incompetech.com)
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!

If you’re interested in showing monetary support, consider making a recurring donation at:
Alternatively, you can send me a one-off payment via PayPal. Click on the “Business Enquiries” button to reveal the email address on this page:

0612 TV Official Writeup:
More about me:
Official Twitter:

= 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.

Watch this space, and keep your eyes peeled on this channel for more updates!

—–

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.

Nguồn: https://verbivoraciouspress.org/

Xem thêm bài viết khác: https://verbivoraciouspress.org/tong-hop/

36 COMMENTS

  1. First off, your stuff is great! I've looked at a lot of algorithms resources and your videos are by far my favorite! Keeps it concise without leaving out any essential information.

    Just want to be clear: in each run through, you're looking at two less terms right? Like if you had an array of size 10… it'd you'd look at elements 0-8 on the way up and 8-1 on the way down, then 1-7 on the way up and 7-2 on the way down, then 2-6 on the way up and 6-3 on the way down etc.

    Also, why is there so much focus on worst cases? To use cocktail sort as an example, it seems that it'd take a really odd arrangement of elements to lead to the worst case, and that it'd perform really good in the average case. Shouldn't an algorithm's efficacy be judged as an expected value? Like you'd take each possible arrangement of elements and the corresponding speeds of the algorithm, and multiply that by the likelihood that the elements start off arranged that way. I guess looking at worst-case would work well in practice though because using expected values is complicated. What do you think?

  2. +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!

  3. 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.

  4. 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.

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

  6. 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.

  7. 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".

  8. In this case, it just appears as if the cocktail sort is faster. In the bubble sort, 9 is fastest into position, followed by 8 (a little slower), and so forth. In the cocktail, 1 becomes the new "8", and so forth. So the order of "speed" is then 9,1,8,2,7,3,6,4,5. No speed advantages at all. It's all in appearances. Still n^2.

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

  10. 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 🙂

  11. 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.

  12. can you please help me with some advantages and disadvantages of the cocktail sort 🙂 Thanks in advance 🙂

  13. 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!

  14. 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)?

LEAVE A REPLY

Please enter your comment!
Please enter your name here