Implement Selection Sort - Trouble with Duplicates

JavaScript
1

Tell us what’s happening:
I am not sure what’s wrong with this selection sort algorithm. I should be looping through each item in the array and swapping it with the minimum value between it and the end of the array.

This algorithm works when there are no duplicate values:
console.log(selectionSort([5, 3, 2, 1, 4])); // returns [1, 2, 3, 4, 5]

It does not work when duplicates are present:
console.log(selectionSort([5, 3, 2, 1, 3])); // returns [1, 2, 5, 3, 3]

What am I missing?

Your code so far


function selectionSort(array) {
  // change code below this line
  // Loop through the array
  for (let i = 0; i < array.length; i++) {
    // Save the current item
    const currval = array[i];

    // Find the minimum item from the current index to the end
    const minval = Math.min(...array.slice(i));

    // Save the index of the minval
    const mindex = array.indexOf(minval);

    // If the current value is greater than the minimum value
    if (currval > minval) {
      // Swap the two in place
      array[i] = minval;
      array[mindex] = currval;
    }
  }


  // change code above this line
  return array;
}


// test array:
// [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]

Your browser information:

User Agent is: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.87 Safari/537.36.

Link to the challenge:
https://learn.freecodecamp.org/coding-interview-prep/algorithms/implement-selection-sort/

2

You don’t want to touch the sub array that has been sorted. For example, suppose the current step of algorithm looks like this:
[ 1 2 3 | 5 3 ] (elements left to | are sorted)
then you shouldn’t touch [1 2 3]. However, you do it with indexOf() which acts upon the whole array.

What happens in the next step of previous illustration is that

  • curval = 5, minval = 3
  • mindex = 2, because the first appearance of minval is at index 2
  • swap index 3 and 2
  • arr = [ 1 2 5 3 | 3]

Clear?

1 Like
3

I don’t know how I missed this indexOf problem. I can fix that. Thanks for taking a look!

Heres a Gist of a couple of my solutions, including the corrected version of the above:

4

The only gripe that I have is that your comments are unnecessary. You may have heard from somewhere that you should always comment your code line by line, but this is a really bad practice even for a learning purpose. If you want to know why let me know.