Hey there. In this post i will share with you my little understanding of another Sorting Algorithm in Data Structures and Algorithm. in the last section i spoke about Bubble Sort which loops through the elements one by one comparing it to it’s nearest element and sorting it accordingly. remember we said swapping is going to be one of the key things we will be using in this part of DSA. Selection Sort in the other hand is not too different from the bubble sort in terms of it’s complexity and the looping process just that in this sort type we always look for the minimum element in the collection and once that has been found we set it to the current minimum at the time and swap it to the position of the previous minimum. don’t worry we will have a look at that in a sec.
with Selection sort the current position is kept in memory until a new minimum is discovered before doing any swapping, let’s take a look.
function selectionSort(arr){
let swap = (arr,index1,index2)=>(
[arr[index1],arr[index2]] = [arr[index2],arr[index1]]
);
let minimum = 0;
for(let i=0;i<arr.length;i++){
minimum = i;
for(j=i+1;j<arr.length;j++){ if(arr[minimum] > arr[j]){
minimum=j;
}
}
if(minimum !=i){
swap(arr,i,minimum);
}
}
return arr;
}
console.log(selectionSort([56,8,56,9,22,4,1,6]))
First let’s create a function selectionSort, inside it the first thing to do, remember we need to do some swapping so don’t forget to create a swap function to help in the process. we declared a variable called minimum to hold the minimum element in memory whenever we have one. Our first loop is to go through the collection to find our first minimum and in this case we used the first as one at the end of it because looping alone will not magically detect the minimum value. So then we created a second loop j=i+1 to be the next element to compare the minimum with and if the current minimum value is greater than j then it means j becomes a minimum value so we quickly assign it the minimum to be our current minimum, when this process is through in the second loop at least for the first time we have our minimum, then we swap it with the current position of i and we repeat the same process until the length of the array is reached. Now to eliminate repetition of comparing the same element twice we check if the current position is not our current minimum position before swapping that’s why there is an if statement before the swapping it’s not mandatory but it’s very optimal and performant to not waste time when we shouldn’t. The time complexity of a the Selection Sort in any case is O(n²) and having a space complexity in the best case as O(1) because of the extra value we needed to hold for the minimum for the swapping..
Selection Sort should be one of the easiest to write and not too in demand when it comes to speed but can be very suitable for sorting small collection of elements.
As we always do it. Read more and solve more question, that’s the only way to be good at this very one. until next time Bye 🙂