What are we selecting here? Why is it called selection sort?
Selection sort is another simple sorting algorithm that works by growing a subset of either largest numbers or smallest numbers.
As the name suggests the algorithm works by making selections. You pass over elements and keep a reference of largest one. Once you reach the end of unsorted portion of array, you swap the last element with the largest element seen.
Now that largest element is at it's correct position, therefore there is no need of again checking this element. Hence you reduce your each iteration by one.
Quadratic time O(n^2)
//Selection sort maintains and grows a subset the largest i items in sorted order
function selctionSort(arr: number[]): number[] {
for (let i = 0; i < arr.length; i++) {
let maxIndex = i;
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] < arr[maxIndex]) {
maxIndex = j;
}
}
let temp = arr[arr.length - i - 1];
arr[arr.length - i - 1] = arr[maxIndex];
arr[maxIndex] = temp;
}
return arr;
}
console.log(selctionSort([6, 5, 1, 2, 3]));
console.log(selctionSort([0, 5, 2, 3, 4, 1, -1]));