Today we will be discussing Selection Sort! What this algorithm does, is sort the items in place inside the array. Although, that may sound like it would be a fast way to sort an array, selection sort proves you wrong.
The Pseudocode
- Write a function called selectionSort that takes an array as an argument.
- iterate through the array with a variable i. Store the first element as the smallest value seen.
- iterate through the array again with a variable of j at the next index of i.
- if the our value at arr[j] has a smaller value than our lowest variable found, we can assign that value as the lowest.
- if our value at the index of i is not the smallest value encountered. Start the swapping sequence.
- Repeat the same steps with the next element until the array is sorted.
The Code
function selectionSort(arr){
console.log(arr, 'original')
for(var i = 0; i < arr.length; i ++){
var lowest = i
for(var j = i + 1; j < arr.length; j++){
if(arr[j] < arr[lowest]){
lowest = j
}
}
// if our current i is not the lowest value, start switching
if(i !== lowest){
//create switch here
var temp = arr[i]
console.log(arr)
arr[i] = arr[lowest]
console.log(arr)
arr[lowest] = temp
console.log(arr)
console.log(temp, 'temp holding at place for a switch')
console.log(lowest, 'lowest @ index')
console.log(arr[i], 'arr[i] has now became lowest')
console.log(arr[lowest], 'arr[lowest]')
}
}
return arr
}
selectionSort([7,9,4])
[ 7, 9, 4 ] 'original'
[ 7, 9, 4 ]
[ 4, 9, 4 ]
[ 4, 9, 7 ]
7 'temp holding at place for a switch'
2 'lowest @ index'
4 'arr[i] has now became lowest'
7 'arr[lowest]'
[ 4, 9, 7 ]
[ 4, 7, 7 ]
[ 4, 7, 9 ]
9 'temp holding at place for a switch'
2 'lowest @ index'
7 'arr[i] has now became lowest'
9 'arr[lowest]'
[ 4, 7, 9 ]
Explanation
The part to understand is how the swap works. Basically, if we find that i is not the lowest value, that's where the magic of swapping happens. If we find out that the value where i is place is not the smallest value, we must create variable temp and assign it in place of arr[i] as a place holder for swapping. We thin assign arr[i] with the value that arr[lowest] is holding. That will now place the smallest value in its correct position. The last swap in place is to assign arr[lowest] to temp, giving the lowest the large value in place close to where it needs to be.
The Time & Space Complexity
Given that our selection sort function has a nested for loop, along with a consistent amount of swapping with every comparison made to every other element in the array, this puts our Time Complexity at O(n^2). However, Space Complexity of this algorithm is O(1), we are swapping in-place of array, which means isn't a need for creating a new array or add extra space in our existing array.
The Conclusion
Well folks, that concludes my blog about Selection Sort! I hope this was helpful on your personal journey of how to understand Algorithms! Stay tuned for the next topic on Insertion Sort!
Happy Coding!
Top comments (0)