Example of implementing the selection sort algorithm in C. Source code: github.com/por.... Check out www.portfolioc... to build a portfolio that will impress employers!
Everything was going on well until (length - 1). Shouldn't it just be (i < length) since the loop will run from i = 0 to i = 9. I think if it runs to (i < length - 1) its literally running till (i = 8) and not (i = 9). Somebody please help me
Question im having trouble wrapping my head around the use of temp variable and reassigning a[min_pos] = temp, when does that get placed , or swapped back into the array
So the temp variable is really just there to perform a swap between the element at index i and the "minimum element" found at index min_pos. The entire swap happens in 3 steps right here: if (min_pos != i) { int temp = a[i]; // step 1 a[i] = a[min_pos]; // step 2 a[min_pos] = temp; // step 3 } The goal is to swap the values at a[i] and a[min_pos]. So let's say: a[i] = 9 a[min_pos] = 3 In step 1 we take what is in the current index i and store it into temp, so we would then have: a[i] = 9 a[min_pos] = 3 temp = 9 ...then we are safe to overwrite a[i] with a[min_pos] in step 2, because we have a copy of a[i] in temp, so after step 2 we have: a[i] = 3 a[min_post] = 3 temp = 9 and then in step 3 we store into a[min_pos] what is in temp (the now previous value of a[i]), and we get: a[i] = 9 a[min_pos] = 3 temp = 9 And then we've completed the swap of the values of a[i] and a[min_pos]. Does that help? :-)
i always have a hard time understanding this kinds of things cause i always forget which loop is executing and when it stops executing and muck it up by thinking once it finds a less than the previous number i is incremented leaving hence making it worthless and leaving me with the worst headache of today. gotta remember the nested loops man. but i gotta say my brain was not meant to follow through loops like this without quickly getting disoriented. thanks anyways
The original code is posted here, it will work if you run it exactly like this code: github.com/portfoliocourses/c-example-code/blob/main/selection_sort.c. :-)
I want to help you Sarah, but I'm not sure what I can say that's not already in the video. :-) I assume by last step you mean the swap that takes place in the if-statement. Basically, in the inner loop above that if-statement we search for the "smallest element in the remaining unsorted portion of the array, from index i to to length. We start off with the assumption that the smallest element is at index i, and if we find a smaller one we keep track of the index of this smallest element using min_pos. Now if the element at index i IS the smallest element, we don't need to do anything, because the "next smallest element" is already at index i, by "coincidence" let's say it just happens to be there. But if the next smallest element is not at index i, and instead min_pos is a different index between i + 1 and length, THEN we swap the element at min_pos with the element at index i. When we keep doing this for each index (the work done by the outer loop), we end up with a sorted array, but continually finding and putting the smallest element at that 'next index'. There is also more comments in the code explaining things here: github.com/portfoliocourses/c-example-code/blob/main/selection_sort.c. Hopefully this helps! :-)
sir, appreciate your time and teaching style, just had a question, after the first for loop, you write int min_pos =i; i dont't get it, is this i the same i as in the loop ? how do we tell the program that asuume the first position in the unsorted area is the minimum one...
Yes, that is the same i as in the outer loop. And when we set min_pos = i, that is exactly when we are "telling the program" to assume the first position in the unsorted array is the minimum one. Because from there the inner loop with the counter variable j will check the rest of the values in the unsorted portion of the array and it will keep updating min_pos when it finds one the is smaller than whatever is at min_pos. Hopefully this helps... selection sort is tricky to wrap our heads around. :-) One thing that might be worth trying is writing another for loop with a counter variable k, and have it output ALL the values of the array at the start of the outer loop with the counter variable i, as this can help us to visualize each step of the algorithm and see what it's doing: for (int i = 0; i < length - 1; i++) { for (int k = 0; k < length; k++) printf("%d,", array[k]); printf(" ); int min_pos = i; for (int j = i + 1; j < length; j++) if (a[j] < a[min_pos]) min_pos = j; if (min_pos != i) { int temp = a[i]; a[i] = a[min_pos]; a[min_pos] = temp; } }
@@PortfolioCourses i don't know to appreciate you for taking this time to answer my question, just one more, in my outer loop, when i change ""i < length - 1"" to i < length, i simply get the same answer, why is that ?
@@kasra4187 If i goes up until length instead of length -1 it will essentially be looking at the last element in the array, but that element is sorted by default and so we don't need to actually look at it. When the inner loop starts j off at i + 1, the loop will do nothing in that case, because i + 1 is not less than length. The last element is sorted by default because after continually picking off the next smallest element again and again, the only thing that can possibly remain is an element >= those elements, which will be sorted already then.
Great question! 🙂 The algorithm works by continually finding the smallest element in the unsorted portion of the array, on the right-hand side toward the end of the array. By the time we reach the last element in the array as the only remaining unsorted element, we KNOW it must be larger than (or at least equal to) the other elements, because all the other elements in the sorted portion must have been smaller than this final element for them to be selected already.
@@PortfolioCourses my degree is computer science (first year) and your c algorithms are the best...thank you a lot,You saved me and probably a lot of students too
@@jonjones6218 Thank you for the kind words, I'm very glad to hear that these videos have been helpful to you. I was hoping that these videos would be helpful to students in particular. I just want to make sure that you saw this too: th-cam.com/video/8HWeT_2XC4U/w-d-xo.html. I could very likely do something like create a discount code for your fellow students, if you think they would be interested... in general helping to spread the word about this channel is the most helpful thing right now. :-)
Because on the 10th iteration of the outer loop, there would only be a single element in the "unsorted portion" of the array. And one element is always sorted, by default. If we have two elements left, say 2,1, then yes we might need to re-arrange them. But if we only have one element, say 9 or something, there is no way to "sort" it. And we ALSO know that the left-portion of the array is sorted, and that all of these numbers in the left-portion are *smaller* than (or equal to) the last element in that last index of the array. And so we don't need to do anymore work at this point, we can correctly infer that the array must now be sorted when only one element remains in the unsorted portion of the array.
It *might* sort the list, but it doesn't look like the selection sort algorithm as multiple swaps could be happening in that inner loop. The selection sort algorithm works in a 'very specific way' and so if we deviate from it, though it might work, it won't be a proper implementation of selection sort. The code in the video is found here: github.com/portfoliocourses/c-example-code/blob/main/selection_sort.c
@@PortfolioCourses Yes, I'm having hard time trying to undertand the merge sort algorithm, I didn't get the recursion on you implementation, I will rewatch the video again, hopefully I will get it😔, and thank u for the reply.
i have a problem ,in selection sort code : I do it from my own it do compiler .but when compiler it .not arrange in wright answer .wrong arrange alwas in "index 4" .could you check pls .and tell me the answer if you do not mind ,thanks a lot , #include #include #include #include #include #include void selction_sort(int arry[],int len); void swap_funcation(int*x ,int*y); void print(int arry[],int len); int main(void) { int arry[]={6,4,9,7,50,8,11,15,30,80}; int len = sizeof(arry) / sizeof(arry[0]); selction_sort(arry,len); print(arry,len); } void selction_sort(int arry[],int len) { for(int i=0 ; i
Great question Bapun! Strictly speaking, we don't *need* to do this check. We start off with the assumption that min_pos = i; at the top of the outter loop. That is, we assume that the minimum element is at position i in the array. And then the inner loop tries to find a position at which there is an even smaller element, and we update min_pos when we do (min_pos is set to the position of the *smallest* element in the remainder of the array). And then to sort the array, we swap whatever is at position i with whatever is at min_pos. BUT if min_pos is still set to i, in other words, we never found an element smaller than the element at index i, then we don't need to do a swap. So that's why we check 'if (min_pos != i)', because IF min_pos == i there is no need to swap. If we didn't do this check, the algorithm would still work. We would just swap the element at index i with itself. This would be doing extra work for no reason though. And it is 'more efficient' to check whether we need to swap at all then to do swaps unnecessarily (swapping is a bit more 'expensive' in terms of the computational and memory work required). I hope this answers your question! 😀
Excellent explanation. Thanks for putting this together.
You’re welcome Jason! :-)
Wish i saw this before my exams, you explained it so well.
Thank you, I'm glad you enjoyed the explanation! 😀
What exam is that
@@randomvide1 CAPE exams, sorta like British A level exams
@chrxnic_vxnity9900 best of luck.
I wish I found out about this channel earlier. It could have saved me a lot of time. Thank you❤❤.
You're very welcome, I'm glad you found the channel! ❤️
this could've saved me from severe depression of getting a bad quiz. it clicked because of your explaination!
Beautiful channel to learn C language, thank u so much sir, i have learnt many things from your channel..❤❤❤❤
Everything was going on well until (length - 1). Shouldn't it just be (i < length) since the loop will run from i = 0 to i = 9. I think if it runs to (i < length - 1) its literally running till (i = 8) and not (i = 9). Somebody please help me
I'm kinda late but it shouldn't compare up to the last one because there is nothing else to compare to
thank you! your explanation is very easy to understand.
You're welcome, I'm glad you found the explanation easy to understand! :-)
Portfolio courses always delivers..💯
Thank you! 😀
Question im having trouble wrapping my head around the use of temp variable and reassigning a[min_pos] = temp, when does that get placed , or swapped back into the array
So the temp variable is really just there to perform a swap between the element at index i and the "minimum element" found at index min_pos. The entire swap happens in 3 steps right here:
if (min_pos != i)
{
int temp = a[i]; // step 1
a[i] = a[min_pos]; // step 2
a[min_pos] = temp; // step 3
}
The goal is to swap the values at a[i] and a[min_pos]. So let's say:
a[i] = 9
a[min_pos] = 3
In step 1 we take what is in the current index i and store it into temp, so we would then have:
a[i] = 9
a[min_pos] = 3
temp = 9
...then we are safe to overwrite a[i] with a[min_pos] in step 2, because we have a copy of a[i] in temp, so after step 2 we have:
a[i] = 3
a[min_post] = 3
temp = 9
and then in step 3 we store into a[min_pos] what is in temp (the now previous value of a[i]), and we get:
a[i] = 9
a[min_pos] = 3
temp = 9
And then we've completed the swap of the values of a[i] and a[min_pos].
Does that help? :-)
i always have a hard time understanding this kinds of things cause i always forget which loop is executing and when it stops executing and muck it up by thinking once it finds a less than the previous number i is incremented leaving hence making it worthless and leaving me with the worst headache of today. gotta remember the nested loops man. but i gotta say my brain was not meant to follow through loops like this without quickly getting disoriented. thanks anyways
How about linked list representation of this linked list? do you have
We have this course on Linked Lists with C that you might like Francis: www.udemy.com/course/linked-lists-with-c/?couponCode=A22DEAL
Very helpful sir 🙏🙏🙏 appreciated
You’re very welcome! :-D
W video you are a life saver
I'm glad that it helped you out! 🙂
Very good and funny videos bring a great sense of entertainment!
Thank you! :-D
awesome video! but can you explain at 5:54 im not sure i understood that, can we do it without that line of code?
The if-statement that checks whether a swap is necessary? It should work OK if we just do the swap without checking whether it's necessary. :-)
This code is not giving me a sorted array
The original code is posted here, it will work if you run it exactly like this code: github.com/portfoliocourses/c-example-code/blob/main/selection_sort.c. :-)
hello, I still didn't get the last step. Can you explain it pls
I want to help you Sarah, but I'm not sure what I can say that's not already in the video. :-) I assume by last step you mean the swap that takes place in the if-statement. Basically, in the inner loop above that if-statement we search for the "smallest element in the remaining unsorted portion of the array, from index i to to length. We start off with the assumption that the smallest element is at index i, and if we find a smaller one we keep track of the index of this smallest element using min_pos. Now if the element at index i IS the smallest element, we don't need to do anything, because the "next smallest element" is already at index i, by "coincidence" let's say it just happens to be there. But if the next smallest element is not at index i, and instead min_pos is a different index between i + 1 and length, THEN we swap the element at min_pos with the element at index i. When we keep doing this for each index (the work done by the outer loop), we end up with a sorted array, but continually finding and putting the smallest element at that 'next index'. There is also more comments in the code explaining things here: github.com/portfoliocourses/c-example-code/blob/main/selection_sort.c. Hopefully this helps! :-)
svaka tebi cas, bolji si od ovih asisestenata na fakultetu
I'm glad you enjoyed the video! :-)
thank you so much!
You’re welcome! :-)
how do i use this with decimal?
You could change the type of the array and temp variable to double (or float). :-)
sir, appreciate your time and teaching style, just had a question, after the first for loop, you write int min_pos =i; i dont't get it, is this i the same i as in the loop ? how do we tell the program that asuume the first position in the unsorted area is the minimum one...
Yes, that is the same i as in the outer loop. And when we set min_pos = i, that is exactly when we are "telling the program" to assume the first position in the unsorted array is the minimum one. Because from there the inner loop with the counter variable j will check the rest of the values in the unsorted portion of the array and it will keep updating min_pos when it finds one the is smaller than whatever is at min_pos. Hopefully this helps... selection sort is tricky to wrap our heads around. :-)
One thing that might be worth trying is writing another for loop with a counter variable k, and have it output ALL the values of the array at the start of the outer loop with the counter variable i, as this can help us to visualize each step of the algorithm and see what it's doing:
for (int i = 0; i < length - 1; i++)
{
for (int k = 0; k < length; k++) printf("%d,", array[k]);
printf("
);
int min_pos = i;
for (int j = i + 1; j < length; j++)
if (a[j] < a[min_pos]) min_pos = j;
if (min_pos != i)
{
int temp = a[i];
a[i] = a[min_pos];
a[min_pos] = temp;
}
}
@@PortfolioCourses i don't know to appreciate you for taking this time to answer my question, just one more, in my outer loop, when i change
""i < length - 1"" to i < length, i simply get the same answer, why is that ?
@@kasra4187 If i goes up until length instead of length -1 it will essentially be looking at the last element in the array, but that element is sorted by default and so we don't need to actually look at it. When the inner loop starts j off at i + 1, the loop will do nothing in that case, because i + 1 is not less than length. The last element is sorted by default because after continually picking off the next smallest element again and again, the only thing that can possibly remain is an element >= those elements, which will be sorted already then.
Thx
You’re welcome! :-)
Hm... but why in the second loop it's 'length' and not 'length-1'?
Great question! 🙂 The algorithm works by continually finding the smallest element in the unsorted portion of the array, on the right-hand side toward the end of the array. By the time we reach the last element in the array as the only remaining unsorted element, we KNOW it must be larger than (or at least equal to) the other elements, because all the other elements in the sorted portion must have been smaller than this final element for them to be selected already.
@@PortfolioCourses Ohhh, I get it now! Thank you!!!
@@enyakot You're welcome! 😀
Nice...do You have a master or phd in computer science?
Yes, I have a PhD in computer science.
@@PortfolioCourses my degree is computer science (first year) and your c algorithms are the best...thank you a lot,You saved me and probably a lot of students too
@@jonjones6218 Thank you for the kind words, I'm very glad to hear that these videos have been helpful to you. I was hoping that these videos would be helpful to students in particular. I just want to make sure that you saw this too: th-cam.com/video/8HWeT_2XC4U/w-d-xo.html. I could very likely do something like create a discount code for your fellow students, if you think they would be interested... in general helping to spread the word about this channel is the most helpful thing right now. :-)
I don't understand why we need 9 iterations instead of 10 for the outer for loop
Because on the 10th iteration of the outer loop, there would only be a single element in the "unsorted portion" of the array. And one element is always sorted, by default. If we have two elements left, say 2,1, then yes we might need to re-arrange them. But if we only have one element, say 9 or something, there is no way to "sort" it. And we ALSO know that the left-portion of the array is sorted, and that all of these numbers in the left-portion are *smaller* than (or equal to) the last element in that last index of the array. And so we don't need to do anymore work at this point, we can correctly infer that the array must now be sorted when only one element remains in the unsorted portion of the array.
@@PortfolioCourses thank u for the answer
i understand the concept but not sure how to use it in my own code would this also work?
Written in C. I.E.
a[] = {5,2,7,4,1,6,3,0};
for (int i = 0; i < 8 -1; i++)
{
int temporaryV = a[ i ];
for ( int j = i + 1; j < i; j++)
{
if ( a[ j ] < temporaryV)
{
temporaryV = a[ j ];
a[ j ] = temporayV;
}
}
}
It *might* sort the list, but it doesn't look like the selection sort algorithm as multiple swaps could be happening in that inner loop. The selection sort algorithm works in a 'very specific way' and so if we deviate from it, though it might work, it won't be a proper implementation of selection sort.
The code in the video is found here: github.com/portfoliocourses/c-example-code/blob/main/selection_sort.c
@@PortfolioCourses ok thank you
You’re welcome! :-)
Simple algorithm🙃
I always had to draw "pictures" with arrows to understand how sorting algorithms worked myself. :-)
@@PortfolioCourses Yes, I'm having hard time trying to undertand the merge sort algorithm, I didn't get the recursion on you implementation, I will rewatch the video again, hopefully I will get it😔, and thank u for the reply.
I found merge sort pretty difficult to wrap my head around when I first learned it, it's definitely more difficult to understand.
👌
Thank you! 😀
horrible style of writing code
Why do you think the style is “horrible”?
@@PortfolioCourses kinda hard to read, i finally got used to it and understood the code but it took me a while.
@@kevinstarofficial You are just a dump programmer. Admit it.
i have a problem ,in selection sort code : I do it from my own it do compiler .but when compiler it .not arrange in wright answer .wrong arrange alwas in "index 4" .could you check pls .and tell me the answer if you do not mind ,thanks a lot ,
#include
#include
#include
#include
#include
#include
void selction_sort(int arry[],int len);
void swap_funcation(int*x ,int*y);
void print(int arry[],int len);
int main(void)
{
int arry[]={6,4,9,7,50,8,11,15,30,80};
int len = sizeof(arry) / sizeof(arry[0]);
selction_sort(arry,len);
print(arry,len);
}
void selction_sort(int arry[],int len)
{
for(int i=0 ; i
I didn't get why we had to take if(min_pos != i)
Great question Bapun!
Strictly speaking, we don't *need* to do this check. We start off with the assumption that min_pos = i; at the top of the outter loop. That is, we assume that the minimum element is at position i in the array. And then the inner loop tries to find a position at which there is an even smaller element, and we update min_pos when we do (min_pos is set to the position of the *smallest* element in the remainder of the array). And then to sort the array, we swap whatever is at position i with whatever is at min_pos. BUT if min_pos is still set to i, in other words, we never found an element smaller than the element at index i, then we don't need to do a swap. So that's why we check 'if (min_pos != i)', because IF min_pos == i there is no need to swap.
If we didn't do this check, the algorithm would still work. We would just swap the element at index i with itself. This would be doing extra work for no reason though. And it is 'more efficient' to check whether we need to swap at all then to do swaps unnecessarily (swapping is a bit more 'expensive' in terms of the computational and memory work required).
I hope this answers your question! 😀