# Recursive and Non-recursive SelectionSort

Posted on

Problem

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;
}
``````

Solution

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);
}
``````

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.

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!
}
``````