@@bubaighosh8500 Nope, the person teaching is pretty much alive and is working at Google. (Animesh Nayan). However, another co-founder kinda guy (Harsha aka Humblefool) died in an accident. Those circumstances led to the closure of the channel.
I saw a lot of comments below asking for new videos from this guy, This is 2020 and it has been 7 years since this video was posted and the content is top-notch. However the author is no more and suffered a loss of life by a speeding car while crossing a road. May he rest in peace.
We are always comparing with A[iMin] i.e the current minimum,, so, its against 7, then against 4 and then against 2. Its not always against 7 because iMin is getting updated.
These videos are really awesome.Please post more videos on C programming and if possible on java,python,c++ or any other language you want or on data structures and algorithms because you are doing a great job. Your videos helped me a lot.You make things simple and concise.
Great lesson, I think the final code can be optimized... void selectionSort(int* A, int n){ int temp; // temporary variable for (int i=0; i < n-1; i++){ // n-2 passes (last element comparisons are not necessary) for (int j=i+1; j < n; j++){ if (A[j] < A[i]){ // there's a smaller value ahead temp = A[i]; // interchange positions A[i] = A[j]; A[j] = temp; } } }
@@saajankumarjha244 yes that's optimization swapping elements only when needed, that implies fewer instructions per pass and less execution time even with the same time complexity
@@saajankumarjha244 mine because in the worst case scenario (like the one you propose) swapping occurs through all the array and time execution is almost the same, but when it's not the case (like the vast majority of cases) the lines that swap positions in my code execute only when is necessary because they are inside the "if" condition.
dear sir, we are following ur entire content please update this course with more algorithms , please bros who like this series give thumbs . (from india)
it probably would make sense to add another "if" statement, to check if the min is different from i (then swap is needed). Right now, we are swapping every time, even when it is not needed
Hi Anton, We are building a huge video tutorial of solutions which are asked in the interview. and we need your feedback on our video content. We believe that we can achieve that if you are around with us. So please come to our RUclips channel. The playlist link is as given below. ruclips.net/p/PLqqPVCi6glKYJ3RK_LrlljjnAk5QdcroX Please subscribe the channel for any upload notification.
Selection sort. In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.
His definition of in-place for this algorithm that you showed makes sense but from other examples i see swaps and not copying values to a new array. In place means there is NOT a use of extra data structures that will be created then deleted. Selection sort is said to be an in place but you are saying it is not? is this explanation wrong or am I confused?
I think for selection sort, time complexity for best case should be O(n) because if one traverses through the already sorted list, then one can always come out of it after finding that it is already sorted instead of traversing again. Here is my code : int temp, min = 0, index = 0; bool swap = true; for(int i = 0; i < num && swap; i++) { min = arr[i]; swap = false; for(int j = i; j < num - 1; j++) { if(min > arr[j+1]) { min = arr[j+1]; index = j+1; swap = true; } } if(swap == true) { temp = arr[i]; arr[i] = min; min = temp; arr[index] = min; } }
You mentioned that this algorithm is slow, but technically, it is not if n (size of the array) is small. As n gets bigger, it can begin to get slower yes.
I found it complicated than other explanations..Why can t you have variable to hold the index of minimum value from each pass. Then swap the first element and the minimum element. So in next pass start from 2nd element to find second element and so on...
There is a mistake at 2:37, it is supposed to be the second smallest element and not second-largest. Thank you for the videos, they are absolutely amazing :)
Hi, I recently found out about your channel and why did you stop making videos you are so good at it. Its a request if you could upload more videos about cs if possible. Love your work
please do the lecture for file pointers i.e, lecture on streams..... we are having a lot of trouble in learning that....... thank you for all the lectures till now.....
nth term in arithmetic series is calculated by a (sub n) = n ( (a1 + a (sub n) )/ 2 ) , if last term is 1, and first is (n-1), how do you get n(n-1) / 2
7:46 acc to j loop for an array 472135, the element replaced with 4 will be 2, not 1, which is contrary to the fact that the lowest element is compared with the element at index 0. So what exactly it is?
Nilashish Chakraborty That's because you forgot (like me, at first) that the "j" loop loops all the way to the end of the array on each "i" iteration. 2,1,4,8 is the result you would get if the "j" loop would run only over one element (j=i+1).
Hello, Thanks! for the Explanation. It's good to start for learning. I have a small doubt. At present we have shortcuts are available like Arrays.sort(), Arrays.parallelSort(); Comparable and Comparator etc., We need to learn this sorting Algorithm._ (I don't know that's the reason I am asking.) _.*It anyone knows please provide the answer. * Please provide any links. I need to learn more about this. Thanks and Regards, Sarat.
There is an issue with this algorithm. If u take inputs as 4,2,1,8 it gives back 2,1,4,8 as output. And it is not an issue of the code because the sorting algorithm itself specifies this sort of output it. Please check it :) P.S: I might be wrong ;)
Hello Sir. Here I have a doubt. When you are in element 7 and then we check for each element which is lesser than 7 from 2 to 5 indices. In each index suppose index 2 (4 lesser 7) => True so imin is 2. Again it goes to index 3 (2 lesser 7) True = > imin is 3 then index 4(5 lesser 7)= > imin is 4 and last index 5(3 lesser 7) = > imin is 5. So at the end imin is 5. Now A[5] and A[1] will be swapped right that is 7 AND 3 ?
Why use iMin at all? Why not simply use i instead of iMin? We can do the comparison A[j] < A[i] and it will give the same result. void SelectionSort(int A[], int n) { for (int i=0; i
Your videos are the best of data structures and algorithms and more! Do have a question about this video here. @7:56, the comment says "we need to do n-2 passes", but even though we do not have to do the last loop, that should still mean n-1? From the loop condition, it was n-1 passes, and also in practice, it's n-1 passes as well. Does anyone also have this concern? Thanks
Hi Venkata, We are building a huge video tutorial of solutions which are asked in the interview. and we need your feedback on our video content. We believe that we can achieve that if you are around with us. So please come to our RUclips channel. The playlist link is as given below. ruclips.net/p/PLqqPVCi6glKYJ3RK_LrlljjnAk5QdcroX Please subscribe the channel for any upload notification.
when entering the inner for loop and checking the if (condition) which if true updates the value of iMin to j, does the result of iMin changing its value to j correspond to entering the inner for loop again?
I found the answer to my question...after reading the code a few times I was able to see what the inner for loop was doing with each j index....Your videos are great!
Wouldn't the part with the cost "c1" be executed "n - 2" times? Since you are starting with the index 0 till n-2 which makes (n - 2) - 0 + 1 = n - 1 for the loop header of the outer loop. Then n - 2 for the statements inside the loop.
Great video! This was a much clearer explanation than when i took this class in college. Quick question, why would you want/need to pass in the length of the array. Are you assuming that this is being implemented in languages without built in arrays with a find/return length function? It seems like it would be unnecessary for a user to input the length.
Hi Miscritz, We are building a huge video tutorial of solutions which are asked in the interview. and we need your feedback on our video content. We believe that we can achieve that if you are around with us. So please come to our RUclips channel. The playlist link is as given below. ruclips.net/p/PLqqPVCi6glKYJ3RK_LrlljjnAk5QdcroX Please subscribe the channel for any upload notification.
this has probably been asked already, but why pass function argument "int n", when you can simply assign this variable inside function definition like so: int n = A.Length;
+Cesar Omiste because in some low level languages like C an array is not an object but just a chunk of memory and it's up to you to save the length or if you want to be fancy measure a the memory size and divide by the size of the type :)
In Selection sort algorithm, why you are iterating the i loop till n-2 and j loop till n-1, should not they be n-1 and n, respectively. In program they are correct.
mycodeschool hmm, just confused how they both are same. as per the pseudo code if last last value in the array is the smallest value, pseudo code won't work?
mycodeschool Yes, the punit jain is right. In pseudo code last array element won't be checked in any iteration. If you will have array 5, 3, 2, 1, 0 after sorting it will look like 1, 2, 3, 5, 0. P.S Please make some annotation on video to prevent confusions to another watchers. Thank you
+Spark Shift We actually assume that the first element is the minimum , and then we check it with with all the upcoming elements in the array here:- iMin
mycodeschool You guys do an awesome job.Thanks! I have a query.The two loops are nested.So,to calculate the time complexity,shouldn't their individual complexities be multiplied?Why are they being added?
because we are trying to find the index of minimum value so that we can swap it with the i'th value. If we use i instead we will mess up the first loop which uses i'th index to iterate
This is almost like online tuition. You can ask questions and even request videos. We can try to get them. :)
My god . How could you know that ? Even I thought why this guy is not uploading videos.
@@bubaighosh8500 Nope, the person teaching is pretty much alive and is working at Google. (Animesh Nayan). However, another co-founder kinda guy (Harsha aka Humblefool) died in an accident. Those circumstances led to the closure of the channel.
@@oreoshake6287 no
@@shamanthakrishnakg1978 uff
❤❤❤
Did you see our merge sort video? Its quite simplified. You may start loving recursion once it settles well in your head.
Cant we write
if(arr[j]
I saw a lot of comments below asking for new videos from this guy, This is 2020 and it has been 7 years since this video was posted and the content is top-notch. However the author is no more and suffered a loss of life by a speeding car while crossing a road. May he rest in peace.
hope that's not true
He is Animesh Nayan and he's alive
We are always comparing with A[iMin] i.e the current minimum,, so, its against 7, then against 4 and then against 2. Its not always against 7 because iMin is getting updated.
These videos are really awesome.Please post more videos on C programming and if possible on java,python,c++ or any other language you want or on data structures and algorithms because you are doing a great job. Your videos helped me a lot.You make things simple and concise.
Rest in Peace Harsha. You will be remembered through your amazing work.
He died?
@@riyazbajishaik1596 car accident 🙏🙏
Rest in peace. :,(
Sad news. R.I.P😢😢
Rest in peace 😢
Rest in peace Harsha. I feel honored to be learning from you even after you're gone from this earth.
One of the greatest lecture of all time on algorithm!
Great lesson, I think the final code can be optimized...
void selectionSort(int* A, int n){
int temp; // temporary variable
for (int i=0; i < n-1; i++){ // n-2 passes (last element comparisons are not necessary)
for (int j=i+1; j < n; j++){
if (A[j] < A[i]){ // there's a smaller value ahead
temp = A[i]; // interchange positions
A[i] = A[j];
A[j] = temp;
}
}
}
how's this optimized ? what you've done is nothing but bubble sort with swapping of min elements. Time complexity for both is O(n^2)
@@saajankumarjha244 yes that's optimization swapping elements only when needed, that implies fewer instructions per pass and less execution time even with the same time complexity
@@davidgmos here's a scenario for you consider an array {5,4,3,2,1}, let me know which one is optimized in terms of swapping.
@@saajankumarjha244 mine because in the worst case scenario (like the one you propose) swapping occurs through all the array and time execution is almost the same, but when it's not the case (like the vast majority of cases) the lines that swap positions in my code execute only when is necessary because they are inside the "if" condition.
Thank you so much, will probably binge watch your videos for my upcoming DSA exam
It was difficult for me to understand but you made me understand in 10 minutes.
Thanks
dear sir, we are following ur entire content please update this course with more algorithms , please bros who like this series give thumbs .
(from india)
brother, this guy is no more
@@sarfaraz6582 what happened to him
@@shubhampanwar6879 passed away years ago by car accident
@@sarfaraz6582 bro its not this guy its the other cofounder of the channel his friend who died..the guy who speaks in the video works for google now
it probably would make sense to add another "if" statement, to check if the min is different from i (then swap is needed). Right now, we are swapping every time, even when it is not needed
Hi Anton,
We are building a huge video tutorial of solutions which are asked in the interview. and we need your feedback on our video content. We believe that we can achieve that if you are around with us. So please come to our RUclips channel. The playlist link is as given below.
ruclips.net/p/PLqqPVCi6glKYJ3RK_LrlljjnAk5QdcroX
Please subscribe the channel for any upload notification.
Actually,I also think about “if”,if it is added,the program is more efficient .
@@chouliwen4173 no.
*_This guy sounds the same as the one on neso academy_*
yes , noticed
he also owns neso academy.
HIRAK MONDAL your comment is in bold. How you do that...
@@usama57926 *use "*" at start and end of comment*
@@RajKumar-qv7ci thank u very much
Selection sort. In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.
His definition of in-place for this algorithm that you showed makes sense but from other examples i see swaps and not copying values to a new array. In place means there is NOT a use of extra data structures that will be created then deleted. Selection sort is said to be an in place but you are saying it is not? is this explanation wrong or am I confused?
@@blake1835 well it can be both in-place and not-in-place. Generally, not-in-place are used to make explanation easier. But in-place is much better.
some of the best material online period
Such a masterpiece! It is still no.1 in 2023
I really appreciate your work...one of the best channel for DS & Algo...Please make more videos
Love his voice
I think for selection sort, time complexity for best case should be O(n) because if one traverses through the already sorted list, then one can always come out of it after finding that it is already sorted instead of traversing again. Here is my code :
int temp, min = 0, index = 0;
bool swap = true;
for(int i = 0; i < num && swap; i++)
{
min = arr[i];
swap = false;
for(int j = i; j < num - 1; j++)
{
if(min > arr[j+1])
{
min = arr[j+1];
index = j+1;
swap = true;
}
}
if(swap == true)
{
temp = arr[i];
arr[i] = min;
min = temp;
arr[index] = min;
}
}
It's O(n^2) because of the nested for loop I think
amazing explanation, hats off to you sir, keep it up 👍👍
You mentioned that this algorithm is slow, but technically, it is not if n (size of the array) is small. As n gets bigger, it can begin to get slower yes.
at 7:45, shouldnt j be from i+1 to n? otherwise we keep missing the last element of the array and dont compare it to anything
The way you explain your selection sort and how you code your selection sort function is actually different in my opinion.
I also agree with this
U saved my life
I just love you. You teach the way I learn !
I LOVE YOU! Thanks for these clips!
I found it complicated than other explanations..Why can t you have variable to hold the index of minimum value from each pass. Then swap the first element and the minimum element. So in next pass start from 2nd element to find second element and so on...
It's too good👍👍 i understood very easily bro
Your language accent is so good and sweet
There is a mistake at 2:37, it is supposed to be the second smallest element and not second-largest.
Thank you for the videos, they are absolutely amazing :)
he probably meant to say 2nd largest within the sorted portion of the array.
Dude, please keep making videos...we need you, even in 2021...please
in 2022 too
But he died
Hi, I recently found out about your channel and why did you stop making videos you are so good at it. Its a request if you could upload more videos about cs if possible. Love your work
he died
@@swastiksharma6926 no Animesh nayan is alive
@@womanwhocode3032 the brain behind the channel that is Harish died and as a result Animesh is depressed and can not make more videos
Sir hats off to you the best lectures on sorts i have ever heard thankyou so much
This helps me a lot in my exam..thnkzzzzzz a lot
very gratuful for you man , this really gave an overview of sorting algorithms
teacher: lets talk about simple sorting scenerio. teacher: *takes out adult uno cards*
lmao
Best explanation I ever found for sorting.
Thanks alot sir for the easiest approaches you shared with us .😊😊
please do the lecture for file pointers i.e, lecture on streams.....
we are having a lot of trouble in learning that.......
thank you for all the lectures till now.....
thanks bro. your teaching way is impressive.....
nth term in arithmetic series is calculated by a (sub n) = n ( (a1 + a (sub n) )/ 2 ) , if last term is 1, and first is (n-1), how do you get n(n-1) / 2
this vid also taught me time complexity calculation wow! hats off....
7:46 acc to j loop for an array 472135, the element replaced with 4 will be 2, not 1, which is contrary to the fact that the lowest element is compared with the element at index 0. So what exactly it is?
This is my question too :/
For e.g., 4,2,1,8
It would give back 2,1,4,8 :/
Nilashish Chakraborty
That's because you forgot (like me, at first) that the "j" loop loops all the way to the end of the array on each "i" iteration. 2,1,4,8 is the result you would get if the "j" loop would run only over one element (j=i+1).
it's a faulty algorithm man he should have stored the position of min not the value to swap at the end
Hello,
Thanks! for the Explanation. It's good to start for learning. I have a small doubt. At present we have shortcuts are available like Arrays.sort(), Arrays.parallelSort(); Comparable and Comparator etc., We need to learn this sorting Algorithm._ (I don't know that's the reason I am asking.) _.*It anyone knows please provide the answer. * Please provide any links. I need to learn more about this.
Thanks and Regards,
Sarat.
There are predefined sorting methods . These sorting algorithms are just choices in case we need to implement algorithms based on input size.
You are good at teaching and creating panel
Thank you
Why i
There is an issue with this algorithm. If u take inputs as 4,2,1,8 it gives back 2,1,4,8 as output. And it is not an issue of the code because the sorting algorithm itself specifies this sort of output it. Please check it :)
P.S: I might be wrong ;)
it gives 1248 for me
8:03 Shouldn't the outermost loop be running n-1 times? The logic is correct but the comment is not correct
You're correct, just a small mistake there
Nice explanation..
but can you please upload video for Heap Sort and Radix sort?
Hello Sir. Here I have a doubt. When you are in element 7 and then we check for each element which is lesser than 7 from 2 to 5 indices. In each index suppose index 2 (4 lesser 7) => True so imin is 2. Again it goes to index 3 (2 lesser 7) True = > imin is 3 then index 4(5 lesser 7)= > imin is 4 and last index 5(3 lesser 7) = > imin is 5. So at the end imin is 5. Now A[5] and A[1] will be swapped right that is 7 AND 3 ?
I too have this same doubt.. can anyone clarify ?
Thank you sir for that video it's very helpful for me
Why use iMin at all?
Why not simply use i instead of iMin?
We can do the comparison A[j] < A[i] and it will give the same result.
void SelectionSort(int A[], int n)
{
for (int i=0; i
Just for sake of better understanding
all da videos r just mind blowing
Your videos are the best of data structures and algorithms and more!
Do have a question about this video here. @7:56, the comment says "we need to do n-2 passes", but even though we do not have to do the last loop, that should still mean n-1? From the loop condition, it was n-1 passes, and also in practice, it's n-1 passes as well.
Does anyone also have this concern? Thanks
he did not put = sign
i
It is less than n-1 which means less than or equal to n-2. So actually only n-2 passes
Totally worth that horrendous zomato ad
Amazing vids. Thanks for making them.
There's an error in the pseudocode. It's:
for i
*nicely explained..loved it*
thank u soo much for these good tutorials.
please upload a lecture on linkedlist
Normally I am not into correcting grammar mistakes but since you say it in every video: first not 1th
great videos btw!!
First number will actually be the zeroth index . So 1th is said to avoid confusion .
instead of n could replace by array.length or return new arr[] will be more efficient
great work..it really very helpful
Could you make the data structures and algorithms videos using java
Hi Venkata,
We are building a huge video tutorial of solutions which are asked in the interview. and we need your feedback on our video content. We believe that we can achieve that if you are around with us. So please come to our RUclips channel. The playlist link is as given below.
ruclips.net/p/PLqqPVCi6glKYJ3RK_LrlljjnAk5QdcroX
Please subscribe the channel for any upload notification.
You help me so much
Thanks for your brilliant tutorial!!!
how to stop looping by using selectionsort if array is already sorted?
Please provide videos on heap sort also
*best lecture*
Great tutorials! Keep it up i appreciate it!
can we just not perform a simple swap in selection sort for every length of array
Can we improve algo by running c3 only if iMin is changed in c2?
please update your content if possible!
in 2021 also best series to learn Ds
excellent explanation
loving your videos!!
when entering the inner for loop and checking the if (condition) which if true updates the value of iMin to j, does the result of iMin changing its value to j correspond to entering the inner for loop again?
I found the answer to my question...after reading the code a few times I was able to see what the inner for loop was doing with each j index....Your videos are great!
M. Ma awesome :)
Wouldn't the part with the cost "c1" be executed "n - 2" times? Since you are starting with the index 0 till n-2
which makes
(n - 2) - 0 + 1 = n - 1
for the loop header of the outer loop. Then n - 2 for the statements inside the loop.
How did you get n(n-1)2 pls explain
what about an array like this {3,2,1} will it still work?
Great video! This was a much clearer explanation than when i took this class in college. Quick question, why would you want/need to pass in the length of the array. Are you assuming that this is being implemented in languages without built in arrays with a find/return length function? It seems like it would be unnecessary for a user to input the length.
Just a suggestion!!!!!!!!!!!!!!!!!!!!WE dont need to swap even if the chosen i element is already minimum in global array
Array bhai bhai bhai bhai
List behen behen behen behen
Hi Miscritz,
We are building a huge video tutorial of solutions which are asked in the interview. and we need your feedback on our video content. We believe that we can achieve that if you are around with us. So please come to our RUclips channel. The playlist link is as given below.
ruclips.net/p/PLqqPVCi6glKYJ3RK_LrlljjnAk5QdcroX
Please subscribe the channel for any upload notification.
@@aryamaangoswamy179 😂
😂😂😂😂😂😂
Bro😂😂
please give me the time complexity analysis link
Time complexity explanation was pretty vague. I felt the second expression should be (n-2)(n-2)C2/2
Great Explanation !!!
Btw which software do u use for writing things like this?
I think: paint.
Thank you!!!
Awesome teaching...
Good work👍🏻👍🏻👍🏻
You're so good!!!! Indian tutorials forever!
2:37 When you are good at coding but you say 1th instead of 1st xD
dude, we are discussing the index so, the first index of array is not so cool as a programmer as the 1th , huhh!
Explanation is very congested and hastened. Go over the points a bit more patiently
this has probably been asked already, but why pass function argument "int n", when you can simply assign this variable inside function definition like so: int n = A.Length;
+Cesar Omiste because in some low level languages like C an array is not an object but just a chunk of memory and it's up to you to save the length or if you want to be fancy measure a the memory size and divide by the size of the type :)
Kilian Ciuffolo Thanks. Too long working in C# :)
In Selection sort algorithm, why you are iterating the i loop till n-2 and j loop till n-1, should not they be n-1 and n, respectively. In program they are correct.
punit jain It's because in the program, I am running the loop for less than n-1. In Pseudo code, I am saying till n-2. They mean the same.
mycodeschool hmm, just confused how they both are same. as per the pseudo code if last last value in the array is the smallest value, pseudo code won't work?
mycodeschool Yes, the punit jain is right. In pseudo code last array element won't be checked in any iteration. If you will have array 5, 3, 2, 1, 0 after sorting it will look like 1, 2, 3, 5, 0.
P.S Please make some annotation on video to prevent confusions to another watchers. Thank you
Answering to a really old comment here, but to clear up confusion: the difference is the pseudo code is "
@@LarryAszune thanks
Excellent explanation...we should make videos... excellent...
Great explanation
can u plz upload video Radix sort... I am not getting it through other videos available till now..
is it safe to say that any algorithm with a nested loop would have a time complexity of at least (n^2)?
no
what if we have duplicate number in the list like two same numbers. How that one number will be arranged?
how will we find the minimum no. in an array? like what will be the code?
+Spark Shift We actually assume that the first element is the minimum , and then we check it with with all the upcoming elements in the array here:-
iMin
mycodeschool You guys do an awesome job.Thanks!
I have a query.The two loops are nested.So,to calculate the time complexity,shouldn't their individual complexities be multiplied?Why are they being added?
Multiplication is nothing but repeated addition. He did the same
Can anyone explain to me why did we use the iMin variable instead i variable in the if statement?
because we are trying to find the index of minimum value so that we can swap it with the i'th value. If we use i instead we will mess up the first loop which uses i'th index to iterate
@@spacesuitred3839Ohh thanks for the explanation!
amazing video, you make it so simple..