This content originally appeared on flaviocopes.com and was authored by flaviocopes.com
Suppose we have an array of numbers, and we want to sort it by element size.
You could have an array of objects, and you could compare an object property, like sorting by age, or alphabetically by last name. The details don’t change.
We work in this way: we pick the first item. Then we compare it with the second item. If the second item is smaller, we swap it with the first. And so on, we compare this first item with every item in the array.
Once we know we have the smallest item, we switch to the second element, and we compare it with every item in the array, ignoring index 0, since we already know that’s the minimum. And so on, until the end of the array.
As you can see, the algorithm is very expensive. It not only iterates on every item of the array: for each item, it iterates again the array.
Its complexity is O(n^2). Note that technically the number of items we compare keeps becoming smaller, but this does not mean anything in terms of the Big O conventions for complexity.
Here’s our implementation of selection sort.
const selectionSort = (originalList) => {
//we first copy the array to avoid modifying the original array, since objects are passed by reference in JS
const list = [...originalList]
const len = list.length
for (let i = 0; i < len; i++) {
let min = i
for (let j = i + 1; j < len; j++) {
if (list[min] > list[j]) {
min = j
}
}
if (min !== i) {
// a new minimum is found. Swap that with the current element
;[list[i], list[min]] = [list[min], list[i]]
}
}
return list
}
const listOfNumbers = [1, 6, 3, 4, 5]
console.log(selectionSort(listOfNumbers)) //[1,3,4,5,6]
This content originally appeared on flaviocopes.com and was authored by flaviocopes.com
flaviocopes.com | Sciencx (2020-11-22T05:00:00+00:00) JavaScript Algorithms: Selection Sort. Retrieved from https://www.scien.cx/2020/11/22/javascript-algorithms-selection-sort/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.