Recursive and Non-recursive SelectionSort

Question

This is a naive attempt of writing a recursive and non-recursive versions for SelectionSort(). My goal is mainly to present an elegant, easy-to-understand, idiomatic code, and therefore, performance is a distant priority. Please comment away!

// Find the index at which the minimum value 
// exists inside the Array 
function findMinIndex(a){
    return a.reduce((iMin, x, i, arr) => x < arr[iMin]? i : iMin, 0); 
}

// Remove the minimum value from the array 
// Return the value removed 
function removeMin(a){
    idx = findMinIndex(a); 
    minVal = a[idx];   // for [1, -5, 3], minVal = -5
    a.splice(idx, 1);  // [1, -5, 3] -> [1, 3] 
    return minVal;
}

// Selection sort, in recursive mode  
// As the name suggests, we select and 'splice' it 
// away from the array, and recursively 
// concatenate it to get the final result
function selectRecursive(a) { 
    if (!a.length) return [];   // terminating case 
    minVal = removeMin(a);      // remove the smallest
    console.log(v, a); 
    return [minVal].concat(selectRecursive(a)); 
}

var myl = [1, 2, 3, 99, 22, 55, 5];
selectRecursive(myl);

OUTPUT

1 [ 2, 3, 99, 22, 55, 5 ]
2 [ 3, 99, 22, 55, 5 ]
3 [ 99, 22, 55, 5 ]
5 [ 99, 22, 55 ]
22 [ 99, 55 ]
55 [ 99 ]
99 []
[ 1, 2, 3, 5, 22, 55, 99 ]

In addition, a non-recursive (less intuitive in my opinion) version of SelectionSort (using push, slice, splice and the spread operator) is presented below.

function selectionSort(a) {
  var length = a.length;
  for (var i = 0; i < length; i++) {
    a.push(  // select and append at the end
      ...a.splice(
        findMinIndex( // get min in a sliced 'a'
          a.slice(0, length - i)), 1) 
    ); 
  }
  return a;
}

Answer 1

I'll take this a function at a time before looking at your end goal.

function findMinIndex(a){
    return a.reduce((iMin, x, i, arr) => x < arr[iMin]? i : iMin, 0); 
}

The largest problem with this function is that it fails for empty arrays. findMinIndex([]) incorrectly returns 0, an index which does not exist. If the array is empty, I'd suggest returning a flag value of -1.

Since undefined is less than -Infinity, we then have to swap the comparison around to make it work with essentially the same logic.

function findMinIndex(a){
    return a.reduce((iMin, x, i, arr) => x > arr[iMin]? iMin : i, -1); 
}

I would argue that this is still more complex than it needs to be. There is no need to use the arr parameter as we can just use a from the function call. (Some may disagree with me here) While we are at it, it improves the clarity to rename a to arr.

function findMinIndex(arr){
    return arr.reduce((iMin, x, i) => x > arr[iMin]? iMin : i, -1); 
}

Next up:

function removeMin(a){
    idx = findMinIndex(a); 
    minVal = a[idx];   // for [1, -5, 3], minVal = -5
    a.splice(idx, 1);  // [1, -5, 3] -> [1, 3] 
    return minVal;
}

How this works if pretty obvious, which is good. The one issue is that you create the global variable minVal. It looks like you missed a let. Some people would tell you to avoid functions which mutate their parameters, and while I generally do this myself, since this function is very clear about what it is doing it probably isn't an issue. However, I would probably rewrite this as a one liner, or just inline it as you did in your answer.

function removeMin(a) {
    return a.splice(findMinIndex(a), 1)[0];
}

Now for your recursive function. It also creates a global variable minVal but besides that looks good to me! Really nothing to say here.

The non-recursive selection sort could certainly use some work.

function selectionSort(a) {
  var length = a.length;
  for (var i = 0; i < length; i++) {
    a.push(  // select and append at the end
      ...a.splice(
        findMinIndex( // get min in a sliced 'a'
          a.slice(0, length - i)), 1) 
    ); 
  }
  return a;
}

Personally, I would prefer just simple for loops in this case. No need for all those function calls.

function selectionSort(a) {
    for (let i = 0; i < a.length; i++) {
        let iLow = i;
        for (let j = i + 1; j < a.length; j++) {
            if (a[j] < a[iLow]) iLow = j
        }
        // Fancy destructuring to swap indexes
        [a[i], a[iLow]] = [a[iLow], a[i]]
    }
    return a;
}

Lastly, I can't help but mention a.sort() though I know that's not the point of this exercise.

Answer 2

After I played around with splice a little bit more, I was able to refactor out the removeMin function completely. It seems like splice and recursive SelectionSort were made for each other! Of course, some may argue the code has become less readable, or has it really?

function selectRecursive(a) {
    if (!a.length) return []; // terminal case
    minVal = a.splice(findMinIndex(a), 1); // select and remove
    console.log(minVal, a); // to witness the magic of recursion!  
    return minVal.concat(selectRecursive(a)); // concat recursively!
}