Algorithms: Selection Sort with Javascript
By Henri Parviainen
Selection sort is probably the easiest of sorting algorithms. It's not the fastest, but it's a great place to start to learn different algorithms. In this tutorial, you will learn how to implement selection sort in Javascript.
How selection sort works
Selection sort sorts an unsorted array by repeatedly finding smallest value on the array and placing it at the beginning of the array. Thus, eventually creating a new sorted array.
Let' go through the animation step by step.
let arr = [61, 91, 76, 19, 5, 9, 21, 42, 41, 77];
// Find the minimum value in arr[0...9]
// and place it at beginning of arr
// (swap values between the smallest value and value in position arr[0])
[5, 91, 76, 19, 61, 9, 21, 42, 41, 77];
// Find the minimum value in arr[1...9]
// and place it at beginning of arr[1...9]
// (swap values between the smallest value and value in position arr[1])
[5, 9, 76, 19, 61, 91, 21, 42, 41, 77];
// Find the minimum value in arr[2...9]
// and place it at beginning of arr[2...9]
// (swap values between the smallest value and value in position arr[2])
[5, 9, 19, 76, 61, 91, 21, 42, 41, 77];
// Find the minimum value in arr[3...9]
// and place it at beginning of arr[3...9]
// (swap values between the smallest value and value in position arr[3])
[5, 9, 19, 21, 61, 91, 76, 42, 41, 77];
//... Eventually we will get sorted array at the end.
[5, 9, 19, 21, 41, 42, 61, 76, 77, 91];Example
So, here is how we do a selection sort in Javascript.
Let's imagine we have an unsorted array with some numbers in it, and we need to get it sorted.
let numbers = [10, 12, 1, 122];We can do this with selection sort.
// Helper function for swapping the values
const swap = (arr, inx1, inx2) => {
let temp = arr[inx1];
arr[inx1] = arr[inx2];
arr[inx2] = temp;
return arr;
};
// Selection sort function
const selectionSort = arr => {
for (let j = 0; j < arr.length; j++) {
let min = j;
for (let i = j + 1; i < arr.length; i++) {
if (arr[i] < arr[min]) {
min = i;
}
}
if (min > j) {
arr = swap(arr, j, min);
}
}
return arr;
};
selectionSort([10, 12, 1, 122]);
// returns [1, 10, 12, 122]Conclusion
Selection sort is a simple and easy sorting algorithm that gets the job done, but as it uses two nested loops it has a time complexity of O(n2). Therefore, it's not as fast as some of the more sophisticated sorting algorithms like insertion sort, bubble sort or quick sort.
