I was reading "grooking algorithms" and was writing "selection sort" algorithm in JavaScript. I have a mistake in code, but I can't find it. My code returns wrong values
function findSmallest(arr) {
let smallest = arr[0];
let smallest_index = 0;
for(let i=1; i<arr.length; i ) {
if(arr[i] < smallest) {
smallest = arr[i];
smallest_index = i;
}
}
return smallest_index;
}
function selectionSort(arr) {
let newArr = [];
for(let j=0; j<arr.length; j ) {
smallest = findSmallest(arr);
newArr.push(arr.pop(smallest))
}
return newArr
}
console.log(selectionSort([5, 3, 6, 2, 10]));
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
<script src="code.js"></script>
</head>
<body>
</body>
</html>
My script returns [10, 2, 6] array, but it supossed to return [2, 3, 5, 6, 10]
Can somebody please help me?
CodePudding user response:
It's probably not the cleanest way, but I took your code.
I replaced the loop from the second function because the size of the array changes every time u use pop (or here splice), because the element is removed from the array. And so I use splice to retrieve the right element and not the last one in the list each time. Splice returns an array, so I use the [0] to retrieve the element and therefore avoid having an array of arrays as output.
function findSmallest(arr) {
let smallest = arr[0];
let smallest_index = 0;
for(let i=1; i<arr.length; i ) {
if(arr[i] < smallest) {
smallest = arr[i];
smallest_index = i;
}
}
return smallest_index;
}
function selectionSort(arr) {
let newArr = [];
while(arr.length>0) {
smallest = findSmallest(arr);
elem = arr.splice(smallest,1)[0]
newArr.push(elem)
}
return newArr
}
console.log(selectionSort([5, 3, 6, 2, 10]));
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
<script src="code.js"></script>
</head>
<body>
</body>
</html>
CodePudding user response:
arr.pop(smallest)
does not pop the element at index smallest
.
It only pop the last element of arr
array.