Selection Sort in JavaScript
12,613
Solution 1
The problem with your code is that the left and right parameters are passed in the wrong way round. Here is the working code:alert(newsort(arr, 0 ,arr.length));
Solution 2
var selectionSort = function(array){
for(var i = 0; i < array.length; i++){
//set min to the current iteration of i
var min = i;
for(var j = i+1; j < array.length; j++){
if(array[j] < array[min]){
min = j;
}
}
var temp = array[i];
array[i] = array[min];
array[min] = temp;
}
return array;
};
var array = [3,2,10,1]
console.log('selectionSort should return [1,2,3,10]-->',selectionSort(array));
It might be easier to reason with if you use a helper swap function:
//HELPER FUNCTION
var swap = function(array, firstIndex, secondIndex){
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var array = [2,1];
swap(array, 0, 1)
console.log('swap should return [1,2] -->', array);
var selectionSort = function(array){
for(var i = 0; i < array.length; i++){
//set min to the current iteration of i
var min = i;
for(var j = i+1; j < array.length; j++){
if(array[j] < array[min]){
min = j;
}
}
swap(array, i, min);
}
return array;
};
var array = [3,2,10,1]
console.log('selectionSort should return [1,2,3,10]-->',selectionSort(array));
Visual of selection sort:
[3,1,2]
|-----> iterate over list. find that min = 1 so we swap current i (3) with min(1)
[1,3,2]
|---> iterate over list. find that min = 2 so we swap current i (3) with min(2)
[1,2,3]
|---> iterate over list. find that min = 3 so we swap current i (3) with min(3)
Solution 3
Eloquent solution:
const selectionSort = (items) => {
items.forEach((val, i, arr) => {
const smallest = Math.min(...arr.slice(i))
const smallestIdx = arr.indexOf(smallest)
if (arr[i] > arr[smallestIdx]) {
const temp = arr[i]
arr[i] = arr[smallestIdx]
arr[smallestIdx] = temp
}
})
return items
}
Standard solution:
const selectionSort = (arr) => {
for (let i=0; i <= arr.length-1; i++) {
// find the idnex of the smallest element
let smallestIdx = i
for (let j=i; j <= arr.length-1; j++) {
if (arr[j] < arr[smallestIdx]) {
smallestIdx = j
}
}
// if current iteration element isn't smallest swap it
if (arr[i] > arr[smallestIdx]) {
let temp = arr[i]
arr[i] = arr[smallestIdx]
arr[smallestIdx] = temp
}
}
return arr
}
Testing:
console.log( // [14, 29, 56, 72, 92, 98]
selectionSort([29, 72, 98, 14, 92, 56])
)
Solution 4
const selectionSort = array => {
const arr = Array.from(array); // avoid side effects
for (let i = 0; i < arr.length - 1; i++) {
let minPos = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minPos]) {
minPos = j;
}
}
if (i !== minPos) {
[arr[i], arr[minPos]] = [arr[minPos], arr[i]];
}
}
return arr;
};
Author by
user3371104
Updated on June 23, 2022Comments
-
user3371104 about 2 years
function newsort(arr, left, right){ for(var i= left; i < right; ++i){ var min = i; for (var j = i; j < right; ++j){ if (arr[min] > arr[j]){ min = j; } } var temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } return arr;
}
var arr = [3,5,66,78,23,44,11,32,58]; alert(newsort(arr, arr.length, 0));
Above is the code for a function that I have written. I am still very new to JS, and as a result get confused at times when it comes to syntax. I currently just return the original array, but am trying to do the selection sort, the right/left/mid type.....I can't really tell what is going on at the moment. I am simply trying to sort and then return the array.
Anyone out there able to point me in the right direction?
thanks.....
-
keenthinker about 10 yearsThat is why IMO an appropriate name for
left
andright
would bestart
andend
. -
Ash Ryan Arnwine over 6 yearsDestructuring, a feature that came to JavaScript in ES2015, makes it possible to handle the swap in one line:
[array[i], array[min]] = [array[min], array[i]];
. It's still good to know how to write your own swap function, but destructuring is a great new tool to have in your tool belt. You can read more about destructuring on MDN.