Mistake in a "selection sort" algorithm

Question

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?

.pop() doesn't accept an argument. It always removes the last element of the array and returns the value. — Pointy
– Pointy, Commented Oct 13, 2022 at 19:38
Does this answer your question? The pop() method using a for loop — PM 77-1
– PM 77-1, Commented Oct 13, 2022 at 19:41
SelectionSort is meant to be an in-place algorithm, so pushing and popping are sins. Prefer swapping. — user1196549
– user1196549, Commented Nov 1, 2022 at 10:43

Amaroke · Accepted Answer · 2022-10-13 19:46:15Z

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>

Mehmed · Accepted Answer · 2022-10-13 19:58:21Z

1

arr.pop(smallest) does not pop the element at index smallest. It only pop the last element of arr array.

answered Oct 13, 2022 at 19:58

Mehmed

91 silver badge4 bronze badges

Collectives™ on Stack Overflow

Mistake in a "selection sort" algorithm

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related