I have this code to do selection sort.
function selectionSort(array) {
for(let j = 0; j < array.length; j++) {
let smallest = array[j];
for(let i = j; i >= 0; i--) {
if(array[i] > smallest) {
let temp1 = array[i];
let temp2 = array[j];
array[i] = temp2;
array[j] = temp1;
}
}
}
return array;
}
selectionSort([8, 5, 2, 9, 5, 6, 3]).forEach(element => {
console.log(element);
});I have added one test case, that fails. My idea here is that j is element selector, like a pointer to it, and next loop iterates backwards checking elements before it, and swapping the smallest element. But it kind of works? Some test cases like [1, 3, 2] work just fine, but some like this one does not
Here is a guide to the selection sort algorithum.
Your outer loop should be tracking the first unsorted element. Technically yours is, but you are calling the first unsorted element smallest which it isn't.
Then your inner loop should be searching for the smallest unsorted element and swapping it with the first unsorted element from the outer loop. You are swapping every larger element (instead of the single smallest) element after the one at i.
There is something off about your alogithm, it should look something like the below.
function selectionSort(array) {
for (var i = 0; i < array.length - 1; i++) {
let min = i;
for(var j=i+1;j<array.length;j++){
if(array[j] < array[min])
min = j;
}
const tmp1 = array[min]
const tmp2 = array[i]
array[i] = tmp1;
array[min] = tmp2;
}
return array;
}
selectionSort([8, 5, 2, 9, 5, 6, 3]).forEach(element => {
console.log(element);
});Let's fix it. As the algorithm says,
function selectionSort(array) {
for (let j = 0; j < array.length - 1; j++) {
let smallest = array[j];
let smallest_index = -1;
for (let i = j + 1; i < array.length; i++) {
if (array[i] <= smallest) {
smallest = array[i]
smallest_index = i;
}
}
let temp1 = array[smallest_index];
let temp2 = array[j];
array[smallest_index] = temp2;
array[j] = temp1;
}
return array;
}
console.log("" + selectionSort([8, 5, 2, 9, 5, 6, 3]))