Having learnt bubble sort, it’s time for you to discover how the next sorting algorithm, called Selection sort, works. In bubble sort, each iteration pushed the next highest number to the end. You will do something similar in this sorting too, but in a smarter way. The following video will show you how it’s done.

$$/$$

Video Transcript

So till now you had seen bubble sort and seen that there are a large number of comparisons and swaps involved while doing a bubble sort. Now, what was the result of each iteration of bubble sort? In bubble sort, after each iteration, the maximum element was getting pushed towards the rightmost edge of the array. So instead of doing so many number of swaps, wouldn't it have been better if we would have sort of maintained what is the max element in the array and simply swapped it with the last element? So this is the basic logic of how selection sort work. Here we are going to find the min element in each step, which is the minimum element, and swap it with the leftmost element in the unsorted array. So here if my array looks something like this 75421, what I'll do is that I'll begin from this index and in each step I will maintain a variable which I will call as min. So this variable min maintains the minimum element in my unsorted array. For starting, I would initialize this min variable with my index zero. That is I will assume that my element at index zero is my min element. So now my min is here. I will compare all of the corresponding consecutive elements and see if my min changes. So currently my min is here, whose value is seven. In the next step I will see if this element is less than or more than seven. I would see that since five is less than seven, I would update my min value and my min would now come at this index. In the corresponding next step, I would see that since four is again less than five, my min will get updated to this index. Similarly, in the next step, again, since two is less than four, my min index would come out to be here. And in my last comparison, I would see that since one is again less than two, so my min index would correspondingly be updated till that index. So what I'll do at the end of this iteration is that I will swap the leftmost element with my element at the min index. That is I will swap seven with the min element which is one.

So the end of this iteration will give me an array which looks something like this. Now I can clearly see that this element has now been placed at its correct position. So in my next iteration I can conveniently ignore this element and begin the same process from this index. So as I did in my previous step, I would initialize my min index from here. Now I will repeat the same procedure and check for all the consecutive elements and compare it with my min. In the next step, I find that since four is less than five, I would update my min value to this particular index. Currently, my min would be at this index. In the last step I would compare two with seven and find that I need not update my min because my min is already this and since this is smaller than seven, my min remains the same. So at the end of this iteration I will simply swap my min element with the index from where I started my iteration which was this index. So on swapping this and this that is, I'll swap two with five. My resultant array would look something like this.

Applying the same logic as above, I will now ignore these two elements since they are already in place. I will begin my iteration from this point and name this index as my min index. On comparing it with the next element, I see that since four is less than five, I need not change my min index. Moreover, when I again compare my four with seven, I would see that there is no need for changing the min value. Now, since my min element coincides with the point from which I began my iteration, I need not to do anything but simply move one step ahead and carry on the next iteration. In the next iteration, my checking process would begin from this point. So again, my min would be initialized from this point and I would check the number which is adjacent to it. It would find that since five is less than seven, so the min which I already have, which is this point is correct, so I need not update my min pointer. Similarly, in the last step my procedure would start from this point. That is I would initialize my min from here and it would compare it with itself and need not change anything. So after all these iterations, my final resultant array would look something like this and finally my array would be in the sorted order. If you notice carefully, you would see that there are very less number of swaps involved in this process. This is similar to Bubble Sort in the manner that here also in each step only one number is getting placed at the correct position. But the number of swaps involved are very much less as compared to Bubble Sort. The number of comparisons however, are similar to the number of comparisons in Bubble Sort. But we are utilizing the fact that in each iteration only one element is getting placed at its correct position. So we can simply swap the current minimum element to its correct position. Now, you can see that this array was an example of my worst case scenario because here all the elements were in the reverse order. Now, I want you to think that what were the number of swaps involved if you would have carried out Bubble Sort on this and how many swaps did we do here when we did selection Sort? Think about it carefully and answer in the question that follows.

Video Recap

Selection sort is a sorting algorithm that finds the minimum element in each iteration and swaps it with the leftmost element in the unsorted array.
This reduces the number of swaps involved as compared to bubble sort, where a large number of comparisons and swaps are required.
The algorithm works by initializing a minimum variable and comparing it with the consecutive elements in the array to find the minimum element.
The minimum element is then swapped with the leftmost element in the unsorted array, and the process is repeated until the array is sorted.
In each iteration, only one element is getting placed at its correct position, which minimizes the number of swaps required.
The number of comparisons involved is similar to bubble sort, but the algorithm utilizes the fact that only one element is getting placed at its correct position in each iteration.
Selection sort is more efficient than bubble sort in terms of the number of swaps involved, but it still has a time complexity of $O (n^{2})$ .
Selection sort works well for small arrays but becomes inefficient for large arrays.
In the worst-case scenario, where all the elements are in reverse order, selection sort requires n-1 swaps, whereas bubble sort requires $n * (n - 1) / 2$ swaps.

You’ve learnt that Selection sort also, at the end of each iteration, pushes the next highest number to the end. However, this time it was done with fewer number of swaps. You just picked the highest number in each iteration and swapped it with the last, unsorted number. So, each iteration in the worst case needs only one swap. This is unlike bubble sort where you have to compare and swap every two numbers every time they are out of order. In the next video, you will look at the pseudocode of Selection sort.

$$/$$

Now that you have learnt how to write the pseudocode for Selection sort, let’s move on to our next segment where you will see the Java implementation of the algorithm.