Hello and thank you for your comment! While there are rigorous ways to evaluate time complexity, I use the "intuitive" method for all my sorting algorithm videos. Notice how that, when selection sort runs, it iterates n times over n items. This makes for a total of n*n, or n² comparisons.
Hello and thank you very much for your comment! I'm glad the whole thing worked out for you then! As far as I'm aware though, I think in the grand scheme of things, the one-array method is probably more "correct" in the sense that it is the more space-efficient way of doing selection sort. That's why I was keen to correct my previous mistake in this video.
Hello again, and thank you for your comment! In general, comparisons are the issue, since the act of swapping takes constant time, which is ignored when we look at time complexity.
While you're looping through the list looking for the smallest number, you could make it look for the biggest number at the same time. You would then make it put the smallest number at the beginning, as you would normally, but also put the biggest number at the end. The result of this is that it would only need to loop through half of the list of numbers, thus increasing the performance of selection sort.
Hello and thank you for your comment! You are indeed correct to say this will increase performance, though unfortunately, the optimization is only marginal and the worst-case time complexity remains at O(n²).
Hello and thank you very much for your comment and support! To be fair, in an academic context they probably cover a lot more of the nitty gritty details that you DO need to know... What I'm doing here is just the first step - Helping you picture the algorithm!
Hello, can you discuss about Asymptotic Notations? Also, how to prove the lower bound, upper bound and the Theta(g(n)) by Trial and Error or something that could prove them ?
Jovan Mabilin Hello and thank you for your comment! I would normally give a more detailed answer than this, but it's pretty late here and I'm about to head to bed, so for now, I'll point you to a series on Asymptotic Notations that I've recently created: th-cam.com/play/PLJse9iV6Reqh5B_w9koGyT7nlYm92iITk.html I put a lot of emphasis on the Big O Notation (in fact I spend all of episode 2 doing that), but I do cover the theta notation a bit in episode 3. I use Selection Sort as an example a lot of the time, so hopefully you can gain some insight. Sorry for the short reply for now, if you need any further clarification, please don't hesitate to shoot me another comment. I'll reply to you as soon as I can!
Hi and thank you for the video. I "liked" it. Can you please tell me if you have a video or code that shows how to calculate the timing for selection sort? Thank you.
Ivory Gilyard Thank you for your comment and support! I'm glad you liked the video. I happened to have used Selection Sort as an example for a more recent series that looks at Asymptotic Notations in depth. I have set the video to start at the point in which I begin discussing Selection Sort, but I would advise you to check out the whole series for a better understanding of at least the Big O Notation in general: th-cam.com/video/y1XUTNrYUoc/w-d-xo.htmlm12s
u know wen u say big O(n to the power of 2.) For an array list of 8 elements, is that gonna be 64 comparisons? and if that's not correct then how many comparisons are being made in the example you've shown in the video?
Hello and thank you for your comment! The Big O Notation is unable to tell you _exactly_ how many comparisons there are. Instead, it tells you how much the speed grows as the number of inputs grow. For more information, you may want to watch this mini-series: th-cam.com/play/PLJse9iV6Reqh5B_w9koGyT7nlYm92iITk.html The reason why the _exact_ number of comparisons are not important is because that can be different based on the input data. For the case of the example in the video, try and trace it and you'll count exactly how many comparisons there are. Then, change up the order of the numbers a bit, and you may find that this number has changed. In algorithms analysis, we tend to only be interested in how fast it *grows*.
Hello, and thank you for your comment! That is correct! Since every pass puts one item in the correct position, you'll need as many passes as there are items, to sort the entire array.
Hello and thank you very much for your comment! I think it's really a hybrid! We use a hunt-and-peck style selection sort when there are too many cards so we can get some ordering to start off with. Then we use insertion sort to put things that are "close by" in order. At least that seems to be how it's done everytime I do this activity in class!
Stormy Adams Hello and thank you very much for your comment! I deliberately leave out the coding aspect on many of my tutorials since they are aimed at beginners. My intent is to help learners picture the operation better, and give an intuitive understanding!
lcc0612 well great work sir! i have watched all of them know and i am doing so in prep for an interview for a quick relook at them :) thank you for these videos
Hello and thank you so much for your comment! Glad you found my work useful =)
Hello and thank you so much for your comment, I'm very happy to be of help =)
Hello and thank you very much for your comment! Glad to be of help =)
Hello and thank you for your comment! Happy to be of help =)
Hello and thank you for your comment! Not very sure if I can hear any similarities, but I wrote this short piece myself, probably 3-4 years ago!
Hello and thank you for your comment!
I don't take any responsibility for any consequences that may arise out of that =P
Hello and thank you for your comment!
While there are rigorous ways to evaluate time complexity, I use the "intuitive" method for all my sorting algorithm videos.
Notice how that, when selection sort runs, it iterates n times over n items. This makes for a total of n*n, or n² comparisons.
Hello and thank you very much for your comment! I'm glad the whole thing worked out for you then!
As far as I'm aware though, I think in the grand scheme of things, the one-array method is probably more "correct" in the sense that it is the more space-efficient way of doing selection sort. That's why I was keen to correct my previous mistake in this video.
You're welcome =) Happy learning!
Hello and thank you for your comment!
I'm considering eventually doing this, but this wouldn't be for at least another couple of months.
Hello again, and thank you for your comment!
In general, comparisons are the issue, since the act of swapping takes constant time, which is ignored when we look at time complexity.
I need to present this today in office for the training. I love you bro, you saved my life
+Samay Soni Cheers! Glad to be of help, hope the presentation went smoothly =)
+lcc0612 smooth as silk :P people were impressed XD
+Samay Soni That's great, congrats =)
our life becomes too much easier if u were here as our teacher in the university!
great work
too much helpful :)
Hello and thank you very much for your comment! Very happy to be of help =)
You explain sorting algorithms, so much better than my lecturer :D Thank you Icc0612!!! :)
Wow!! I love the way you explain. It is simple and concise.
Great video. In the course I'm taking selection sort is described as using 2 arrays like your original video, so thanks for explaining both.
consice video with all the information required.
great work.
Bitesh Tiwari Hello and thank you so much for all your comments on my sorting videos! I'm very happy you found my work helpful!
While you're looping through the list looking for the smallest number, you could make it look for the biggest number at the same time. You would then make it put the smallest number at the beginning, as you would normally, but also put the biggest number at the end. The result of this is that it would only need to loop through half of the list of numbers, thus increasing the performance of selection sort.
Hello and thank you for your comment! You are indeed correct to say this will increase performance, though unfortunately, the optimization is only marginal and the worst-case time complexity remains at O(n²).
i got interseting for ma individual assignment.... reallly ur hero!!!!
Thank you for this simple and easy to understand video. Could you please upload videos regarding implementation of all these algorithms in programs?
Hi ... could you explain how you came up with the time complexity?
Thanks!
Why does my tutor spend half an hour explaining this algorithm when it can evidently be taught within 5minutes!?
subbed!
Hello and thank you very much for your comment and support! To be fair, in an academic context they probably cover a lot more of the nitty gritty details that you DO need to know... What I'm doing here is just the first step - Helping you picture the algorithm!
Hello, can you discuss about Asymptotic Notations? Also, how to prove the lower bound, upper bound and the Theta(g(n)) by Trial and Error or something that could prove them ?
Jovan Mabilin Hello and thank you for your comment! I would normally give a more detailed answer than this, but it's pretty late here and I'm about to head to bed, so for now, I'll point you to a series on Asymptotic Notations that I've recently created: th-cam.com/play/PLJse9iV6Reqh5B_w9koGyT7nlYm92iITk.html
I put a lot of emphasis on the Big O Notation (in fact I spend all of episode 2 doing that), but I do cover the theta notation a bit in episode 3. I use Selection Sort as an example a lot of the time, so hopefully you can gain some insight.
Sorry for the short reply for now, if you need any further clarification, please don't hesitate to shoot me another comment. I'll reply to you as soon as I can!
Thank you very much lcc0612 .
Jovan Mabilin You're welcome! Happy to be of help =)
Thank you. You helped a lot to increase speed of my messy code. :)
이동석 Great to hear! Glad I was of help, and thank you for your comment =)
Hi and thank you for the video. I "liked" it. Can you please tell me if you have a video or code that shows how to calculate the timing for selection sort? Thank you.
Ivory Gilyard Thank you for your comment and support! I'm glad you liked the video. I happened to have used Selection Sort as an example for a more recent series that looks at Asymptotic Notations in depth.
I have set the video to start at the point in which I begin discussing Selection Sort, but I would advise you to check out the whole series for a better understanding of at least the Big O Notation in general: th-cam.com/video/y1XUTNrYUoc/w-d-xo.htmlm12s
Good job. You really helped me.
u know wen u say big O(n to the power of 2.) For an array list of 8 elements, is that gonna be 64 comparisons? and if that's not correct then how many comparisons are being made in the example you've shown in the video?
Hello and thank you for your comment! The Big O Notation is unable to tell you _exactly_ how many comparisons there are. Instead, it tells you how much the speed grows as the number of inputs grow. For more information, you may want to watch this mini-series: th-cam.com/play/PLJse9iV6Reqh5B_w9koGyT7nlYm92iITk.html
The reason why the _exact_ number of comparisons are not important is because that can be different based on the input data. For the case of the example in the video, try and trace it and you'll count exactly how many comparisons there are. Then, change up the order of the numbers a bit, and you may find that this number has changed. In algorithms analysis, we tend to only be interested in how fast it *grows*.
So if there are 7 items in an array, it will take 7 passes through the array to have it sorted?
Hello, and thank you for your comment!
That is correct! Since every pass puts one item in the correct position, you'll need as many passes as there are items, to sort the entire array.
Really clear! Thanks!
You're welcome! Very happy to be of help =)
Thank you for your comment!
Actually we use insertion sort while sorting our playing cards.
But your videos are nice and informative.
Hello and thank you very much for your comment! I think it's really a hybrid! We use a hunt-and-peck style selection sort when there are too many cards so we can get some ordering to start off with. Then we use insertion sort to put things that are "close by" in order. At least that seems to be how it's done everytime I do this activity in class!
great explanation! Thank you ^)
+Anastasia Peacefull You're welcome! Very happy to be of help =)
BTW, is your ending music really similar to XDA developers TV?
no point going to class, I'll just watch your videos haha
Hero!
Good video, thanks
Cheers! Glad to be of help =)
Thank you for your comment!
It literally saved my exam haha
Projectlightstyle4
Great to hear! Hope you'd ace the test =)
Thank you again for your comment =)
Heya John, all coming soon! =D
great
thanks bro...........
You're welcome! Happy to be of help. Thank you for your comment! =)
To the point no coding though ... Coding would be nice
Good presentation skills
Stormy Adams Hello and thank you very much for your comment! I deliberately leave out
the coding aspect on many of my tutorials since they are aimed at
beginners. My intent is to help learners picture the operation better,
and give an intuitive understanding!
lcc0612 well great work sir! i have watched all of them know and i am doing so in prep for an interview for a quick relook at them :) thank you for these videos
Stormy Adams You're welcome! Very happy to know you like my videos. All the best for your interview =)
Thanks man !
Hello and thank you very much for your comment! Glad you found my work helpful =)
Hello and thank you for your comment! I'm very happy to be of help =)