Sorting Array with JavaScript reduce function

Solution 1:

It makes no sense to use reduce here, however you could use a new array as an accumulator and do insertion sort with all elements:

array.reduce((sorted, el) => {
  let index = 0;
  while(index < sorted.length && el < sorted[index]) index++;
  sorted.splice(index, 0, el);
  return sorted;
}, []);

Here is the version without reduce:

array.sort((a, b) => a - b);

Now some general tips for writing reducers:

how must be the reduce call back function?

You either take an approach with an accumulator, then the reducer should apply a modification to the accumulator based on the current element and return it:

(acc, el) => acc

Or if accumulator and the elements have the sane type and are logically equal, you dont need to distinguish them:

 (a, b) => a + b

what is the initialValue of reduce function?

You should ask yourself "What should reduce return when it is applied on an empty array?"

Now the most important: When to use reduce? (IMO)

If you want to boil down the values of an array into one single value or object.

Solution 2:

Array.sort mutates the array where using Array.reduce encourages a pure function. You could clone the array before sorting.

I believe this question is designed to get you thinking differently by enforcing constraints. It tests your knowledge of how reduce works and as the answers show there are many ways to skin a cat. It'll show your personal flavour of js in solving this.

I chose to use Array.findIndex and Array.splice.

const sortingReducer = (accumulator, value) => {
  const nextIndex = accumulator.findIndex(i => value < i );
  const index = nextIndex > -1 ? nextIndex : accumulator.length;
  accumulator.splice(index, 0, value);
  return accumulator;
}

const input = [5,4,9,1];
const output = input.reduce(sortingReducer, []);

Testing with the sample input produces

arr.reduce(sortingReducer, [])
// (17) [0, 3, 4, 4, 6, 7, 8, 11, 13, 23, 24, 52, 54, 59, 87, 91, 98]

Solution 3:

Here's an (imo) more elegant version of Jonas W's insertion sort solution. The callback just builds a new array of all lower values, the new one and all higher values. Avoids using explicit loops or indices, so it's easier to see at a glance that it works correctly.

const insertValue = (arr, value) =>
  [...arr.filter(n => n <= value), value, ...arr.filter(n => n > value)]

const testArr = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4]

console.log(testArr.reduce(insertValue, []))

Solution 4:

Here is an example of the sorting an array in descending order using reduce function.

what is the initialValue of reduce function

In this below function the initial value is the [] which is passed as thisArg in the reduce function.

 array.reduce(function(acc,curr,currIndex,array){
        //rest of the code here
        },[]//this is initial value also known as thisArg)

So basically an empty array is passed and the elements will be be pushed to this array

The accumulator here is the empty array.

const arr = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4];
var m = arr.reduce(function(acc, cur) {
  // this arrVar will have the initial array
  let arrVar = arr;
  // get the max element from the array using Math.max
  // ... is spread operator
  var getMaxElem = Math.max(...arrVar);
  // in the accumulator we are pushing the max value
  acc.push(getMaxElem);
  // now need to remove the max value from the array, so that next time it 
  // shouldn't not be considered
  // splice will return a new array
  // now the arrVar is a new array and it does not contain the current
  // max value
  arrVar = arrVar.splice(arrVar.indexOf(getMaxElem), 1, '')
  return acc;
}, []);
console.log(m)

Solution 5:

reduce constraints yourself to online sorting algorithms, where each element in the array is seen once and you do not now in advance the length of your array (note that using closures you could give more information to the reducing function but this kinds of defeats the purpose of the question).

insertion sort is an obvious and easy example; I won't detail the implementation as the other answers are already very good in this regard. However you can mention a few optimizations that might probably seen as very positive to the interviewer:

Use binary search to find the insertion point can reduce the complexity of an insertion step from O(n) to O(log n). This is called binary insertion sort: the overall number of comparisons will go from O(n^2) to O(n log n). This won't be faster because the real cost is due to "splicing" the output array but if you had expensive comparisons (say, sorting long strings for instance) it could make a difference.
If you sort integer, you can use radix sort and implement a linear online sorting algorithm with reduce. This is quite trickier to implement, but very suited to a reduction.