Home > Mobile >  Mistake in a "selection sort" algorithm
Mistake in a "selection sort" algorithm

Time:10-14

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.

  • Related