I pass the tests, just wondering if I’m cheating using the min function here?
/*
Here we will implement selection sort. Selection sort works by selecting the minimum value in a list and swapping it with the first value in the list. It then starts at the second position, selects the smallest value in the remaining list, and swaps it with the second element. It continues iterating through the list and swapping elements until it reaches the end of the list. Now the list is sorted. Selection sort has quadratic time complexity in all cases.
Instructions: Write a function selectionSort which takes an array of integers as input and returns an array of these integers in sorted order from least to greatest.
*/
function selectionSort(array) {
let sortArray = [];
for (let i = 0; i < array.length+sortArray.length; i++) {
let min = Math.min(...array);
sortArray.push(min);
array.splice((array.indexOf(min)),1);
}
return sortArray;
}
// test array:
selectionSort([
4,
1,
2,
8,
345,
123,
43,
32,
5643,
63,
123,
43,
2,
55,
1,
234,
92
]);
I think so… I’m guessing it’s still a big O of N^2 because each time it looks for the min it’s looping through the array, so we’ve still got something on the order of nested loops happening.
i think the ‘no no’ here is mutating your function arguments. its a bad habit that can cause bugs in more complex code.
otherwise nothing really wrong with the way youve used min here
function selectionSort(array) {
let temp = array // copy array so you can remove values without changing array
let sortArray = [];
for (let i = 0; i < temp.length; i++) { // only loop through temp
let min = Math.min(...temp) // gets the min from temp
sortArray.push(min)
temp.splice((temp.indexOf(min)),1) // removes the min for the next loop
}
return sortArray;
}
I’d say it isn’t in the spirit of the challenge - obviously it works, but it’s not really optimal and you’re running a sort on top of a sort. If the challenge is to write a sort function, I would take that as meaning “don’t use the built in sort”. Regarding it not being optimal, you’re copying the input array then iterating through that copy once per loop (though it being array that gets smaller on every iteration means that that’s not a massive issue). You probably shouldn’t worry about mutation with these challenges either: you want the sorts to be as fast as possible, and repeated copying will work against that.
I’ll confess I tried writing the nested for loops way and got frustrated when it wouldn’t work, and was like - the tests don’t say not to use the Math.min method… so am I just making this harder than it needs to be?
Really struggling to wrap my head around recursion and nested looping at the moment. Any advice?
thats kinda janky. also you should only loop through one array at a time
try this
function selectionSort(array) {
let temp = array;
let sortArray = [];
for(let i = 1; i < array.length; i++){ // i is the count, not the index (notice that i = 1)
let min = Math.min(...temp)
sortArray.push(min)
temp.splice(temp.indexOf(min), 1)
}
return sortArray
}
console.log(selectionSort([2, 5, 1])); // returns [1, 2, 5]
Still doesn’t work on larger arrays - I’ve been testing against a 16 element array
try this, maybe this is what you meant
function selectionSort(array) {
let temp = array;
let count = array.length;
let sortArray = [];
for(let i = 0; i < count; i++){ // i is the count, not the index
let min = Math.min(...temp)
sortArray.push(min)
temp.splice(temp.indexOf(min), 1)
}
console.log(sortArray);
return sortArray
}
you don’t need to create or push to another array, or splice the original array
just loop over array
you don’t need to use Math.min or indexOf: use a variable to hold the value of the min index. Each iteration of the main loop, check the rest of the array starting from from your current index (using a for loop).
In that loop, check if the array[current index] is less than the value at the array[min index]: if it is, update min index to be current index.
this means you always have the index of the (next) minumum value. If the current value you’re on in the loop is > than the one at array[min index] then swap them in place*.
(for this, with very primitive tests in the dev console,it’s fine up until 20000 entries, when there’s a slight slowdown. Jumping to 200000 and it gets super slow and takes around 30 seconds)
* EDIT: which you can do via either let temp = array[i]; array[i] = array[j]; array[j] = temp; or, simpler, [arr[i], arr[j]] = [arr[j], arr[i]]
Hi,
I completed this challenge and my solution is similar with the above. But I am not sure this method is cheating or not… As I know well don’t touch the original array, only changed index…
I hope I understood the task. The above solution return with a copy of array (sortArray), not with the original array. My solution return with the original (but sorted) array. Is it right or I must find any other way?
My code:
function selectionSort(array) {
// change code below this line
for (let i = 0; i < array.length; i ++) {
const min = Math.min(...(array.slice(i)));
const minInex = array.lastIndexOf(min);
const tempStore = array[i];
array[i] = array[minInex];
array[minInex] = tempStore;
}
return array;
// change code above this line
}
console.log(selectionSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]));