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!
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.
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".
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.
+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!
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.
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 :)
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)?
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.
Hello and thank you for your comment! I'm very happy to be of help =) I deliberately left out pseudocode in this entire series because one of the most common pitfalls for beginners is attempting to go through pseudocode before being able to picture an algorithm. I'm only focusing on the latter for this course. As for flowcharts, I'm not very sure what sort of flow we're showing here. I feel nothing really beats showing how a sort works better than simply tracing it! =P
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?
Adam Zerner Hello and thank you very much for your comment, and doubly thanks for your kind words! Yes you are correct - Every pass puts two terms in place, and as such for every pass, we look at two less terms. This is an interesting train of thought. I do acknowledge that most of the time, algorithms terminate before their worst case time complexity. In fact, average-case analysis is also something that is done, but like you mentioned, it is a considerably harder task to perform. This is especially true when the input data set starts to get massive, or when we are working with more complex algorithms that perform more actions to the data. Also, there is a value to worst case analysis, both of time and space complexity - Knowing the worst case performance gives us a guarantee of how much time and resources we need, and practically, this is pretty important information since this allows us to determine system requirements.
+yara alshahrani Trouble with school work? Let's see... Advantages: Reasonably easy to implement. Just a bit tougher than Bubble sort, but requires significantly less passes in the general case. Disadvantages: Still a slow algorithm with an O(n²) worst case.
+Dontsaythat Hello and thank you for your comment! No worries about the repetition, as long as I have the time to help people out, I'll try to do so in whatever way works best for them :)
Hello and thank you for your comment! Let's take that every pass of cocktail sort is just in one direction. Meaning: First pass (left to right): Looks at n items Second pass (right to left): Looks at n-1 items Third pass (left to right): Looks at n-2 items ... .... ... Second last pass: Looks at 2 items Last pass: Looks at 1 item Add up all the total comparisons: n + (n-1) + (n-2) + ... + 2 + 1 This is an arithmetic progression, and hence we can perform the following substitution: dl.dropboxusercontent.com/u/27029501/formula.jpg O( (1/2)(n)(n+1) ) = O( (1/2)(n² + n) ) Since the Big O Notation discards coefficients and all terms except that of the highest degree, we get O(n²).
You're welcome! It's never too late because I get notified of new comments all the time and I'll do my best to engage =) Either way, very happy to be of help =)
Hello and thank you for your comment! Yes, indeed, there's no improvement in terms of worst case Big O time complexity. The advantage of this technique is that it increases the likelihood of an early termination. Consider the following data set: 2, 3, 4, 5, 6, 7, 8, 1 If you're using regular old bubble sort, it moves the "1" by one position with each pass, necessitating a full _n_ passes to get everything in place. Cocktail sort on the other hand, gets the job done by the second pass, so assuming that we have mechanisms in place to detect a sorted list, three full passes is all it takes before the algorithm terminates. So cocktail sort is more about allowing more combinations of input to achieve early termination, and less about changing the worst case.
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.
i like precise and concise explanations, thanks for the video.
You're welcome! Very happy to be of help =)
yes
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!
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.
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".
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.
Hello again and many thanks for your comment! Glad you enjoyed =)
+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!
You're very welcome! Glad you found my stuff useful =)
Hello and thank you for your comment! Glad you enjoyed the video =)
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.
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 :)
Too good, explained very easily, understandable
Hello and thank you for your comment! Glad you liked the video =)
wow, the explanations are truly precise!
Hello and thank you for your comment! Glad you liked the video =)
You´ve helped me a lot!
That´s what I was looking for
Hello and thank you for your comment! Very happy to be of help =)
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)?
Hello again and thank you so much! Actually same here, I'm doing a degree program in computer science as well =P
Pretty Helpful. Thanks!
+Sumyat Noepwint You're welcome! Very happy to be of help =)
Thanks for the explanaton. Very precise as always. But I have a question. How do these algorithms, relate to coding?
what's the differenece between best time and average?
Fun as always.
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.
Hello and thank you for your comment! I'm very happy to be of help =)
I deliberately left out pseudocode in this entire series because one of the most common pitfalls for beginners is attempting to go through pseudocode before being able to picture an algorithm. I'm only focusing on the latter for this course.
As for flowcharts, I'm not very sure what sort of flow we're showing here. I feel nothing really beats showing how a sort works better than simply tracing it! =P
can you please help me with some advantages and disadvantages of the cocktail sort :) Thanks in advance :)
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?
Adam Zerner Hello and thank you very much for your comment, and doubly thanks for your kind words! Yes you are correct - Every pass puts two terms in place, and as such for every pass, we look at two less terms. This is an interesting train of thought. I do acknowledge that most of the time, algorithms terminate before their worst case time complexity. In fact, average-case analysis is also something that is done, but like you mentioned, it is a considerably harder task to perform. This is especially true when the input data set starts to get massive, or when we are working with more complex algorithms that perform more actions to the data. Also, there is a value to worst case analysis, both of time and space complexity - Knowing the worst case performance gives us a guarantee of how much time and resources we need, and practically, this is pretty important information since this allows us to determine system requirements.
thank you!!! excellent explanation!
You're welcome! Very happy to be of help =)
hello can you tellm me what the advantage and disadvantage for the cocktail sort
+yara alshahrani Trouble with school work? Let's see...
Advantages: Reasonably easy to implement. Just a bit tougher than Bubble sort, but requires significantly less passes in the general case.
Disadvantages: Still a slow algorithm with an O(n²) worst case.
you arlready said it in the video m8 => no need to repeat yourself . ! I rate this AA++ content by the way nearly perfect !
+Dontsaythat Hello and thank you for your comment! No worries about the repetition, as long as I have the time to help people out, I'll try to do so in whatever way works best for them :)
Amazing thanks!
You're welcome! Very happy to be of help =)
0612 Tv rocks!
Thank you very much! Glad you've been liking my work =)
Thanks for the video!
You're welcome! Very happy to be of help!
This was soooo helpful thank you
hanaleblanc1995 You're welcome! Very happy to be of help =)
very very good explanation thanks :)
You're welcome! Thank you very much for you comment and I'm happy to be of help =)
that was great ! thank you :)
Hello and thank you very much for your comment! Glad you liked the video =)
Hello Urjente need that you develop step by step as you get O n ^ 2 thank you
O(n²)
Hello and thank you for your comment!
Let's take that every pass of cocktail sort is just in one direction. Meaning:
First pass (left to right): Looks at n items
Second pass (right to left): Looks at n-1 items
Third pass (left to right): Looks at n-2 items
... .... ...
Second last pass: Looks at 2 items
Last pass: Looks at 1 item
Add up all the total comparisons:
n + (n-1) + (n-2) + ... + 2 + 1
This is an arithmetic progression, and hence we can perform the following substitution:
dl.dropboxusercontent.com/u/27029501/formula.jpg
O( (1/2)(n)(n+1) ) = O( (1/2)(n² + n) )
Since the Big O Notation discards coefficients and all terms except that of the highest degree, we get O(n²).
lcc0612 OHHHH you are a genius thank a lot :)
You're welcome! I'm very happy to be of help =)
A little late to say it, but thanks so much for this!
You're welcome! It's never too late because I get notified of new comments all the time and I'll do my best to engage =) Either way, very happy to be of help =)
great keeping on ,,, :)
insane, man.
help a lot.
thanks
hold this like!
+GAMEPLAY NORTE Thank you very much! Glad you found the video helpful =)
This doesn't seem like it should be faster. Each pass is still only putting 1 item in the correct position.
Hello and thank you for your comment! Yes, indeed, there's no improvement in terms of worst case Big O time complexity. The advantage of this technique is that it increases the likelihood of an early termination. Consider the following data set:
2, 3, 4, 5, 6, 7, 8, 1
If you're using regular old bubble sort, it moves the "1" by one position with each pass, necessitating a full _n_ passes to get everything in place. Cocktail sort on the other hand, gets the job done by the second pass, so assuming that we have mechanisms in place to detect a sorted list, three full passes is all it takes before the algorithm terminates.
So cocktail sort is more about allowing more combinations of input to achieve early termination, and less about changing the worst case.
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.