Learn Selection Sort Algorithm | @SandeepJainGfG | Episode - 8 | GeeksforGeeks

Key Takeaways

hi let's talk about selection sort algorithm selection sort is one of the basic algorithms like insertion sort and bubble sort it is a comparison based algorithm and has Theta and square time in all cases the good thing about selection sort is it does less memory rights compared to other algorithms if you compare it with other popular algorithms like quick sort M sort insertion sort bubble sort Etc you can notice that this algorithm is going to do less memory rights compared to these algorithms however this is not the optimal algorithm in terms of memory rights there is another algorithm called cycle sort which is optimal in terms of memory rights memory right can be a costly operation in situations like Eep roam in Eep Roam if we do more rights age of this memory reduces so in those cases we can prefer selection sort over other sorting algorithms it's a basic simple sorting algorithm and can reduce memory rights not only Eep roam there can be other situations where memory rights are costly suppose you are writing data to hard disk you're sorting some files and you are putting individual files on the hard disk when you are swapping them or when you're putting them into the memory so this is an advantage of selection sort next important point about selection sort is it's a basic idea for Heap Sort Heap Sort idea is based on selection sort only it is just that Heap Sort uses Heap data structure to optimize the selection sort idea selection sort is not stable in basic form when we do selection sort the order of equal elements may change the next point is it's an in place algorithm it does not require extra memory for sorting let us now understand the basic idea of selection sort algorithm with this example we are going to sort this array in increasing order so the basic idea of selection sort algorithm is we find out the minimum element we put it at the first position then we find out the second minimum element and put it at the second position then we find out the third minimum element and put it at the third position we keep doing it at the end we have the array sorted now please pause this video and try to implement this idea let us see the KN implementation now we first Traverse the input array find out the minimum element and put it at the first position in our temp array and we replace this element with infinite now it travels through the input array again find out the minimum element again and put it at the next position in temporary array and replace this element with infinite now we Travers through the input array again find out the minimum element R here and replace it with infinite same thing we do for remaining elements this is replaced with infinite comes here replac with infinite and comes here replaced with infinite and comes here that's how we get the sorted array let's see the implementation we have created a temporary array of same size now we are traversing through the input array this I decides the index where this next minimum has to be put so first time index I was zero so we put two at index zero and inside this Loop we find out the minimum element first right we initialize the index of minimum element is zero then we Traverse through elements from 1 to n minus one and we compare it with current minimum if it's smaller than current minimum then update the current minimum and after that we put the found minimum element at index I and we put the value infinite at this minimum element index and at the end we copy the temporary array back to the original array so that our original array is modified and we have the sorted array so we are going to copy these elements here 2 5 8 10 18 and 20 so this is our final sorted array now please pause this video and try to optimize the solution in this solution we are using an extra array temp right and this selection sort algorithm should be in place we should not be using extra array to store the sorted array let us now see a better implementation that does not use an auxiliary array we do all operations within the same array let's Now understand the idea with this example in the first iteration like the naive implementation we find out the minimum element which is two here and instead of putting this two in into a temporary array we know this two is going to be at index zero so we swap it with the current element at index zero so 10 comes here the current element at index0 comes here and this element goes to the index zero right and now what we do is we know this element is sorted this is fixed at its correct position now we have this remaining array and we find out the minimum element in this remaining array and minimum element in this remaining array is five and next position where this minimum element should go is also five so we swap five with five and we have this array now so these two elements are sorted now we again find out the minimum element in the remaining array and minimum element in the remaining array is eight and the position where it should be is also the third position so we swap eight with it eight itself and we have this part sorted now we find out minimum element in the remaining array please note that at every point we are maintaining two arrays one array which is already sorted and one sub array which is yet to be sorted and we find out the minimum element in the unsorted part so minimum element now is 10 and where 10 should go now it should go at this position so we swap these two elements so 10 comes here and 20 goes there now we have remaining unsorted array as these two elements we find out the minimum in among these two which is 18 and we swap it with the position with its original position so they are swapped so we have 18 here now now we have only one element remaining we find out the minimum element in this one element which is 20 itself and we swap 20 over 20 we can in fact skip the last execution part of this code or this algorithm because we know it's going to be only one element and there's no point swapping this element with itself we can actually optimize this to run to n minus one instead of n right this is one optimization we can make because this part is not necessary there's only one element left and it's going to be swap with itself only so let's now see the implementation we are running a loop for I = to 0 to n minus one where elements from 0 to I are maintained to be sorted and elements from I + 1 to n minus1 are not sorted so we find out the minimum element from the unsorted part from I + 1 to n minus1 we find out the minimum element we find out the index of the minimum element in a variable called Min index and once we have found the minimum element we swap it with the array I because we know this element should be going at the array I and we move the element minimum index to I and I to minimum index we swap these two right that's the simple implementation of the selection sort let's now see stability in selection sort algorithm selection sort is not called stable because if there are two elements with the same value it may change the order of these elements and why do we care about stability see these two items values which are there in the arrays they might represent individual values of the objects for example these values are marks of the students and these students are ordered according to maybe alphabetically or Institute name and if there are two students with the same marks we want to keep them in alphabetic order right we don't want to change that order so if we apply selection sort here what happens here is this 90 moves to a position after this 90 see uh in the first iteration what we do in the selection s we find out the index of minum element which is three and we swap it with the first element so this 90 comes here and this where this selection s becomes unstable right and rest of the algorithm follows the same process right but this is the step where we have unstability and these 9s never change their position back again because it has come to the end its final position so we do not have stability in selection sort let us now see the time complexity of selection sort so the innermost statement is this statement that executes maximum number of times let's now try to find out how many times this is going to execute when I is zero it's going to execute n minus one times this condition is going to be checked n minus one times when I is 1 it's going to be checked n minus two times and when I reaches n minus 2 it's going to be checked one times only so this condition is being checked these many times in the first iteration of I it's going to check n minus one time then n minus 2 times nus 3 and so on then two and then one if we sum the series we are going to get n into N - 1 by 2 which is Theta n² so this is particular statement is being executed th and a square time and this the most executing statement of this Loop of of this code so that's why the time complexity of selection sort is thet n square and in selection sort it does not happen that the is a best case which is having time complexity less than n Square it always takes n Square time even if you provide the sorted array it's going to take n Square even if you provide reverse s it then also it's going to take n Square