Selection Sort in 1 Video | Theory + Code + Complexity Analysis | Sorting Algorithms

Añadido: 2026-06-06

[00:00:00]Hey everyone, I hope you all are safe and doing good. So next sort is selection sort. We are done with bubble and insertion sort. Let's see what is selection sort. See this array is given to you and you have to sort it in ascending order. I assume this. So first thing this is also comparison based sorting.

[00:00:18]Now what I'll do in this code uh this sort first I will select this also assume that uh the two part of the array one is sorted one is unsorted. But in this case at first this is sorted part. So there is nothing in sorted array and this com this this complete is unsorted.

[00:00:38]So this is unsorted and this is sorted at first there is nothing in sorted. So what we do is from unsorted part we select the smallest element. If I want to arrange in ascending order if you want to arrange in descending order then you pick largest element. So in this case I I just want to uh sort in ascending order. So in this case from the unsorted part we pick the smallest element. So you can check the smallest element is one to somehow we pick we will discuss that process also don't worry. So the smallest element is uh we select the smallest element and what we do we swap this with the first element in this unsorted part.

[00:01:24]So the first element of consolidated part is 10. Smallest element from this part is one. So we swap this with this.

[00:01:30]So after swapping this becomes 1 is this 8 2 5 4 and 10.

[00:01:38]Now this is my sorted portion. This is my unsorted portion.

[00:01:46]Again we do the same process from unsorted part. Again select the smallest element. Smallest element is two and swap with the first element of the unsorted first element of the unsorted part or you can say now with the second element at first we swap with the first element then with the sec second element then third and fourth and fifth like this. So the smallest is two. We swap this with this. After swapping this now array becomes one. Here we have two. Eight would be here. We have five. We have four. We have 10. Now this is my sorted part. And this is unsorted part of the array.

[00:02:28]Repeatedly again same process. From unsorted part select the smallest element that is four. Swap it with the first element of the unsorted part. So we do the same process. 1 2 smallest is four. We swap this with this. Four would be here. Here we have five as it is.

[00:02:46]Eight would be here and 10.

[00:02:48]Now this is my sorted part. This is my unsorted part. Like this one by one we keep adding in the sorted portion of the array the data. So the sorted portion keep growing and we just keep repeating the same process until the complete array is sorted. At last we get this much sorted part and only one element is left. So we know that no need to do any swapping that is already at it correct position.

[00:03:14]So that's how we do.

[00:03:16]Okay. So here we select the smallest element or the largest element depending on uh in which order you are sorting the data and then we so basically we are selecting the position at first at this position I will uh swap that the smallest element then at this position the smallest element I'll find and I'll place that here right so now the process is now how you will find out the minimum element from this okay overall ID data is clear to you but how you will find out the smallest element we know there are we can search smallest element by comparing that's not that uh it's a you can say big deal so how we do this thing let's see let's now define let's now uh write down step by step this at first we have this array sorted is this unsorted is this so we start from here my i is here at first okay so at first I'll assume that my min minimum is 10. Whatever at zero index at the starting of the unsorted that is my minimum. So my minimum is also this. So my minimum index index is also zero or the element here is 10. So my min is also here.

[00:04:37]Okay.

[00:04:40]Now what I do is I keep comparing this starting from this with all the elements. So for that you need another var another pointer or variable J.

[00:04:50]Suppose I have J.

[00:04:54]Three things we need.

[00:04:56]Okay.

[00:04:58]Now minimum is this. So I'll compare this with this. The next element whatever at J is this element less than this 10 because this I assume that minimum element yes less than 10. So it's not that we swap. No what we do is we change my min index. My min index now becomes one.

[00:05:21]So now my min is my min is here and J++ now J is here.

[00:05:29]Again check this two is this two now whatever the data at at J index is less than this min yes so again I might change my min now my min becomes two I don't I'm not swapping I just do my min is now here now J++ again check the data is this less than to less than whatever the mint data right now no okay no need to change my mint just to J++ is this less than two? No. Just do J++.

[00:06:04]Is this data less than whatever min data right now? Yes. Yes. In that case again change min. Now my min becomes five. Now my min is also here J++ but this is out of bound. So we stop right. So now we get the minimum data because at fifth index definitely the minimum data. So now we swap what? We swap this with this. How to get this? We know this I pointer is still pointing to this. So we swap this with this. After swapping now this becomes 1 8 2 5 4 and 10.

[00:06:45]So now I can guarantee I can say that with guarantee that this at the very first of the area I have the smallest data the smallest element that is for sure right.

[00:06:56]Okay, now this is pass one. This was basically pass one.

[00:07:03]After pass one, this is my array. Now this is my sorted portion. This is unsorted portion.

[00:07:10]Now I'll start pass two.

[00:07:14]Now in pass two obviously I would be started from here. I is here. Same again I'll I'll consider my min is equal to also one because index is one. So min is also here min and now I'll start j is here again check same thing same process again repeat I'll consider this as minimum I keep uh checking the data 2 less than 8 yes so I will change my min index to here min index now becomes 01 2 so my min is here and I'll do j ++ j is here is this five less than two No, Min would be as it is just J++. Is this four less than two?

[00:07:58]No, just J++. Is this 10 less than two?

[00:08:01]No, just J++. And now we are out. Stop.

[00:08:04]Now min is index is two. So this is the minimum data at index two. Element is also two. Now we swap this with eight.

[00:08:13]Have to get eight. We know that I is still pointing to 8.

[00:08:17]Yes. So we swap this with this. So after swapping it becomes 1 2 8 5 4 and 10.

[00:08:26]Now this is my sorted data and this is unsorted portion.

[00:08:32]Now from unsorted portion start from here. Now I would be this.

[00:08:37]Now I is here min is also here and J is here. Again same process. Repeat the same process. So see if you analyze in first pass how many comparisons you need we check we consider this as min element. So we compare now this with this then this with this then this with this this with this in worst case with every element we compare to get the minimum element the smallest element. So if there are n in this case 1 2 3 4 5 3 and 3 six elements are there. How many comparison were there? This with this one then again two then three then four then five I guess five comparison. So minus one comparison you need inverse case or especially in this case only five comparison because only six elements we have. Yes. Number of swaps.

[00:09:32]How many number of swaps in first pass?

[00:09:36]There is only one swap. After finding the minimum element, the smallest element, then only we swap with the first element in the unsorted part. So only one swap. Yes. Okay. Same for pass two number of comparisons in this case especially because the eight we assumed minimum element. Then we compare this with this first with this then this was the minimum. So we change this then this with this then this with this then this with this. So 1 1 2 3 4 four comparison number of swaps 1.

[00:10:18]Yes. Same suppose in third pass. After second pass this is my array. So let's go for pass three quickly. I'll just go for pass three.

[00:10:29]Now after pass two my array is something like this. This is sorted. This is unsorted. So my I is here my min I here and J is here. So min is equal to 0 1 2 3 4 5 min is two. I'll assume 8 is minimum. Now compare this with this. Is this element minimum? Yes. Change the min index to here. Min index becomes three. Now J ++ J is here and min is here. Again compare is this less than min. Yes. So J would be plus+ and min would be whatever the J is. So min is four. Now is this less than this?

[00:11:09]No. So min would be as it is.

[00:11:13]J would be here. That is out of bound.

[00:11:15]So we stop. Right. Now whatever minimum element that is at index four. So at index four we have four. The data is there. So we swap this with the eight.

[00:11:25]The first element in this unsorted part.

[00:11:27]So after swapping now the array is 1 2 we swap this with this. So four, five is as it is, 8 is here, 10 is here.

[00:11:37]Now this is my sorted part. This is my unsorted part. Now I'll consider this as minimum element. J would be here. So I would be again I would be plus+ now.

[00:11:48]Right? So this is my pass three. After pass three, this is the array. Now I'll go for pass four.

[00:11:54]Number of comparison. Number of comparison pass three only four data data is source only three comparisons here we need only three number of swap only one number of swap only one after finding the minimum smallest element we swap at the last only one swap now next pass four in pass four let's minimum so min is equal to 0 1 2 3 4 5 at third min is three check j is here. 8 less than five. No. So we just do J++ min would be as as it is. 10 less than five. No. J++ min would be as it is. J++ J is out. So stop. Now min is three. So at third index only we have the minimum element.

[00:12:41]So at first we we done that I is equal to minimum. So after doing all the iteration of J. If still I and min equal it means no need to do swapping or if this is not the case then only we swap.

[00:12:58]But in worst case suppose we need swapping. So in this case number of swap is also one. Number of comparison in past four. So if we swap five with five now array becomes something like this 1 2 4 5 8. So this is now my sorted part.

[00:13:13]This is unsorted part I ++. So I is here now J is here and I'll consider min this. So in this pass four number of comparison only two only two number of comparison only one swap we need in worst case. Now for this same min is this. So my min is is equal to I whatever the i is that is four 0 1 2 3 4 index four j is this is 10 less than 8.

[00:13:39]No. So min would be as it is just j ++ but j is out. Stop.

[00:13:44]Min is at the fourth index only. So we swap eight with eight. So in this case I and min both are same. only to swap right. So number of comparison only one comparison we need in this case. So in pass this was my pass five because after pass four this was the array in pass five I need only one comparison one comparison and one swap.

[00:14:08]Yes after this array becomes something like this 1 2 4 5 if you swap eight with eight. So eight is this and 10. So this is my sorted part. This is unsorted part but in unsorted part now I have only one element so there is no need to again sort just this is already sorted we stop. So how many passes we need pass 1 2 3 4 and five.

[00:14:37]How many elements? Six elements. So n was six. Number of passes required are five. So we can say number of passes required number of passes required in selection sort are n minus one n minus one number of comparisons in first pass how many comparison five then four then three then two then one like this. So total comparison 1 + 2 + 3 + 4. So it's like number of comparison total number of comparison is equal to 1 + 2 + 3 + up to n minus one. Yes, same we know what is this the formula n into n - 1 / 2 right after this we take the polomial so it's n² see the formula for n natural number is we know that is the formula is n into n + 1 / 2 this is the formula but here n is n minus one so rather than n I'll put n minus one so n minus one into n is n - 1 + 1 so we can cancel 1 1 so it becomes n so n into n - 1 divid by 2 if you solve this maybe you get something like n into nx2 - 1 by 2 so it becomes n² by 2 - nx2 but we can ignore this constant and less dominating term that is n² is more so we just consider in bigger notation n² that's why the time complexity is n² number of comparisons are n² square. So the time complexity is also n² in worst case that is selection sort.

[00:16:24]Okay. Now see number of swaps I guess you get number of swaps in this case only one in every pass only one swap only five swap.

[00:16:33]So number of swaps are number of comparison in selection sort n² s order of n² time complexity is also n² in worst case number of swabs required we know five swaps so basically n minus one swap n minus one so we can say order of n in number of swaps it's good it needs fewer number of swaps in selection sort.

[00:17:03]But the problem with selection sort is if the data is already sorted. Let's take I have this data.

[00:17:13]It's already sorted and now I want to arrange in sort in ascending order and I want to apply selection sort. So what the sort will do? At first this is unsorted part this is sorted part. I just assume this one is main element and this is I also this is J.

[00:17:33]So I'll just first select the minimum element from the unsorted part and swap this with the first element of the unsorted part. Min is equal to at zero index index 0 1 2 3 4 5.

[00:17:47]Now compare this with this. Is this less than 10? No. So no need to check. No need to update. Mean just update J. J is J++. Is this less than 10? No. J++ is 30 less than 10? No. J++ is 40 less than 10 no J++ is 50 less than 10 no J++ J is out stop min is still at zero index so basically it's like yeah we have compared how many comparison five six elements but how many comparisons here we have done five then with this one comparison then with this two then three then four then five number of swaps we can check If I and min are same, no need to do swapping. So zero swap. Let's let's say zero swap. But comparison are still five. After after this the array would be 10, 15, 20, 30, 40 and 50. This is the array and this becomes my sorted part and this is unsorted part. Now even after one pass, this was pass one. We are not able to find out that this is already sorted or not.

[00:19:00]Let's take here we have 30 here we have suppose 29. So we know that array is not already sorted but still still you need no you don't need any swapping still the minimum element is 10. So even after you compare this with this 29 is this less than 10? No.

[00:19:20]So J++ and that's it. So no swapping is done. So it's not that if you haven't swapped anything, if there's no swapping then the data is already sorted like we have done in bubble sorting. If there's no swapping, data is already sorted. So no need to go further. But not in this case. In this case also no need. We don't need any swap.

[00:19:40]Okay. But array is not sorted. We can't say it's sorted.

[00:19:45]It's 29. It's 29.

[00:19:48]Yes. So same process you need to repeat.

[00:19:51]Even if you have sorted array, same process you need to repeat. Now you go through the past two. Same process you need to repeat. This I'll consider minimum. This would be my J. This would be my I. Keep comparing this with is this less than 50? No. J++. Is this less than 15? No. J++. Is this less than 15?

[00:20:10]No. J++. Is this less than 15? No. J++.

[00:20:13]And stop. So minimum is still there. No swapping we need. If I and min both are at same after all the iteration of J all the iterations of J no swapping is done still but comparison are still 1 2 3 4 four comparison swap is zero after that array becomes this 15 20 30 40 and 50. So after pass two this is my sorted this is my unsorted part but still we don't know that it's already sorted or not.

[00:20:45]So in this case also in the best case even if the array is already sorted you require five passes in first pass comparison five then four then three then two then one same comparison.

[00:20:58]So in this also we need a number of comparison are 1 2 3 4 + up to n minus one. So same n² so time complexity is same n² so even in best case best case means we assume that data is already sorted. So that is the best case in that case itself you need n² time complexity in average case also it's n² so it's not at all good selection sort in every case time complexity is n square you need comparison yeah although swaps are less in this case rather than bubble and insertion sort but time complexity is this okay so it's definitely not adaptive It's not adaptive because it cannot take advantage of already sorted data. Time complexity is not reducing. It's same. So it's not adaptive. Even if it's not stable as well. You can just check this. You can take here a same elements two or three same element and you can check after setting after sorting the relative ordering will be changed. You can take this example yourself and check this. So it's not stable. Yeah, it's in place.

[00:22:16]No extra memory we need. So it's in place. Space complexity is order of one.

[00:22:21]Space complexity for selection sort is order of one. No extra space we need.

[00:22:25]Within the same array we do swapping kind of thing.

[00:22:29]Yes.

[00:22:31]But yeah one one point is number of swaps are less even if in worst case it's n in the previous cases in bubble insertion was n square. Number of swap were also n square but here in n. So if swaps are costly somewhere you have some requirement that swaps you should reduce number of swaps in that case maybe you can consider this but otherwise it's not good at all.

[00:22:56]Okay. Okay. So first let's try to write down what pseudo code for this or code for this. How we do? We simply what we do is in this case first first loop is obviously for for number of passes passes are n minus one then actually the inside loop is for number of actual comparison so two loops we need for sure nested loop so first we do what first write item in a loop so we call selection sort let's name it the method name is selection sort and we pass the array. So let's take an array here.

[00:23:39]Now first loop I'll take i=0 till I less than whatever size of this. Let's suppose I have n is equal to whatever array do.length the size. So it's n minus one i less than n minus one and i ++ because I need only five passes. So from zero till n minus one less than n minus one. Yes. Next process what we have done we have chosen min index. So min is also whatever i is that is my min index.

[00:24:10]Okay.

[00:24:11]Next next we take j. So we just have like suppose j is equal to i + 1.

[00:24:20]j is equal to i + 1 because j was at first this I consider that this is the minimum index. So I'll consider j here and start comparing.

[00:24:32]So J is equal to I + 1. Now I'll just write down while or you can you use for loop also or Y loop also. It's up to you. Okay. Let's write down while or for loop. In for loop if you want to write. So no need to initialize it again. I mean separately within a for loop itself you can write four.

[00:24:53]J is equal to I + 1 and J less than N minus one and J ++ same J is also okay I mean less than one N minus one or it should be I guess J should be less than equal to N minus one because if N is 6 so N minus one is five index is still five so J should go till five J is we are starting from 1. So J is here. from 1 2 3 4 5 till five.

[00:25:30]Four iteration. 1 2 3 4 five. Five iteration we need 4 J 1 2 3 4 5 right for I we need it should go from 0 till 5 right because at last there is only one remaining element left so we can't that is unnecessary if we go for this also the next pass only one element we have so no need to again go for pass six so pass is still here only so zero I would be zero So 1 2 3 4 till four means less than five less than n minus one but for J should go till five till the last so it should be less than equal to I guess you got why it's less than equal to it's only less than now we check if if array of j if this is less than array of min if this is the case then we change min is equal to min is equal to whatever j We keep doing this thing and after this for loop now that's it within this for loop we write this thing after this for loop we swap but we do not directly swap after this what we write if my min is not equal to I then only we swap we swap I or sorry we swap Yes, we swap I with min because I is still the first index I with whatever minimum you get right now.

[00:27:12]Then we swap this with this.

[00:27:15]Now we just close the outer loop as well.

[00:27:18]That is selection sort.

[00:27:21]Okay. So from loop itself you can find out like we are running from 0 to n.

[00:27:26]Inner loop is also for if I is zero then inner loop is running from I + 1 to J minus 1 I almost n then I becomes 1 then also it is running from almost N. So it's n square time order of n square time complexity number of compression how many times this inner loop runs that will give you basically the time complexity right. So now pause the video and write down this program.

[00:27:53]Let's create a new Java class selection sort and in the same I'm just taking main and I'm just pasting the same array whatever we have taken in insertion sort and we just create a method selection sort and I'll call this and I'll pass array okay or if you want to pass array length then also you can pass array length or array length minus The size or size is array length only now. So we pass only the size that is array length array and array length.

[00:28:32]Now let's define this selection sort we have int array and int n size we have n. Now outer loop will run from 0 till i less than n minus one.

[00:28:54]and I ++ obviously.

[00:29:00]Now in this we take a min. Min is equal to I.

[00:29:04]Right? Now min is also I then we go for another loop. J is equal to I + 1 and J less than equal to N minus one and J++.

[00:29:20]Now we check if whatever at JF index that data is less than whatever at min index then I'll change my min. Min is equal to J.

[00:29:34]And after the center loop we check if my min is not equal to I then we swap. I'll pass my array then I and min.

[00:29:48]That's it.

[00:29:49]and swap you know have to do I think we have done already swapping so I'll just write down here swap so that's how we swap this thing we have already done many times now after this let's print the array so I'll simply call the inbuilt method arrays dot do string and I'll simply pass the array Let's try to run this and see.

[00:30:27]Okay. Index out of bounds. Six is out of bound for length six.

[00:30:36]Okay. Sorry, it's not I less than, it's J less than equal to N minus one because inner loop is J. My bad. Let's run this.

[00:30:49]So it's sorted 11 1 4 5 6 10. Now you try out yourself. I guess it's not that much stuff. You can easily write down the code for this. So now you go to what is selection sort right now. Okay, it's not at all good because in every case the time complexity is n square for selection sort. Yeah, number of swaps are less than the other sorts bubble and insertion but time complexity is not at all good. So for large data it's not good. Maybe for smaller data you can go for this.

[00:31:23]Now in the next lecture we'll see what is quick sort. So all the basic sorting is done. Bubble insertion selection. Now we'll go for efficient uh sorting algorithm quick merge and these. So that's it for this lecture. I'll see you in the next lecture. Till bye-bye. Take care.