javascript - Recursive sort in JS - Stack Overflow

admin管理员组

文章数量:1323705

I was asked in an interview to write a program/algo to sort an array of number using recursion.

Though I vaguely answered it, I tried and came up with following code:

You can use following JSFiddle link to play around.

function sort(arr) {
	if (arr.length === 2) {
  	const v1 = arr[0];
    const v2 = arr[1];
    const isGreater = (
    	(isString(v1) && isString(v2) && v1.toString().toLocaleCompare(v2) > 0) ||
      (isNumber(v1) && isNumber(v2) && v1 > v2)
    );
  	return isGreater ? [ v2, v1 ] : [ v1, v2 ];
  } else {
  	const last = arr.pop();
    const ret = sort(arr);
    const newLast = ret.peekLast();
    
    if (newLast < last) {
      return [ ...ret, last ];
    } else {
    	return sort( [ last, ...ret ] );
    }
  }
}

function isString(value) { return typeof value === 'string'; }
function isNumber(value) { return Number.isFinite(value); }
Array.prototype.peekLast = function () { return this.slice().pop(); }

//console.log(sort([1,2,3,4,5]))

console.log(sort([5,4,3,2,1]))

I was asked in an interview to write a program/algo to sort an array of number using recursion.

Though I vaguely answered it, I tried and came up with following code:

You can use following JSFiddle link to play around.

function sort(arr) {
	if (arr.length === 2) {
  	const v1 = arr[0];
    const v2 = arr[1];
    const isGreater = (
    	(isString(v1) && isString(v2) && v1.toString().toLocaleCompare(v2) > 0) ||
      (isNumber(v1) && isNumber(v2) && v1 > v2)
    );
  	return isGreater ? [ v2, v1 ] : [ v1, v2 ];
  } else {
  	const last = arr.pop();
    const ret = sort(arr);
    const newLast = ret.peekLast();
    
    if (newLast < last) {
      return [ ...ret, last ];
    } else {
    	return sort( [ last, ...ret ] );
    }
  }
}

function isString(value) { return typeof value === 'string'; }
function isNumber(value) { return Number.isFinite(value); }
Array.prototype.peekLast = function () { return this.slice().pop(); }

//console.log(sort([1,2,3,4,5]))

console.log(sort([5,4,3,2,1]))

---

The algo I implemented is:

• Take the array and check if its length is greater than 2.
• If yes,
  • Remove last element and store it in a variable.
  • Again call same function without last element till it has 2 items.
  • Accept array returned from recursive call and peek the last element.
  • If newLast value is greater than previousLast
    • Push previousLast as first element and again call itself with this array.
  • If not, push previousLast to array and return it.
• Else,
  • For number and string check equality and return correct order.
  • For anything else, return same value

---

Question is, is there a better way to implement (algo wise)?

Note: I'm not expecting code improvements. Objective of this question is improvement in algo part or any general stuff I have missed.

I also know, current code does not support:

• Sort order. It will sort ascending only.
• May break for Date objects, and does not support Objects in general.

Thanks!

• javascript
• algorithm

Share Improve this question Follow asked Jan 2, 2019 at 6:18 RajeshRajesh 25k55 gold badges5050 silver badges8383 bronze badges 2

• @downvoter, feel free to share your feedback. We all are here to learn – Rajesh Commented Jan 2, 2019 at 6:26
• @PaulRooney Thanks! I was not aware about this. Will do more reading. Nonetheless, if you have any feedback about the algo I implemented, feel free to share it. It maybe worse than Haskell's but this is my first try. Have a good day. – Rajesh Commented Jan 2, 2019 at 6:36

Add a ment  | 

6 Answers 6

Sorted by: Reset to default 3

I think most interviewers would expect you to respond with quicksort or merge sort (or both) given that question. Of the two, quicksort, is easier to remember and recreate in a pinch because the merge step of merge sort is easy to mess up.

Quicksort is a really beautiful algorithm and is a natural fit for javascript's functional tools. It is worth really understanding if you'll be doing interviews:

const arr = [6, 1, 5, 3, 9, 6, 7, 10, 16, 4, 0, 12, 2]

function qsort(arr){
    if (arr.length < 2) return arr
    // choose a pivot, p
    // the choice of pivot can effect worst-case performance
    // for this, we'll just use the first element.
    const [p, ...rest] = arr

    // partition array into element greater and lesser that the pivot
    // this can be optimized so you don't loop through the array twice
    const low  = rest.filter(n => n <= p)
    const high = rest.filter(n => n > p)

    // recurse on both partitions and reassemble as recursion unwinds
    return [...qsort(low), p, ...qsort(high)]
}
console.log(qsort(arr).join(', '))

I see a vein of intermediate value creation that is not inconsequential.

1. peekLast calls Array.prototype.slice which makes a copy of the array. You copy an entire array just to return the last element.

   Array.prototype.peekLast = function () { return this.slice().pop(); }
   Array.prototype.peekLast = function () { return this[this.length]; }
   

   This gives you the same result every time without the need to copy.

2. Use of spread arguments in expressions like [ ...arr, x ] copies arr entirely.

   arr.concat([ x ]) does the same thing without making copy (or mutation) of arr

You call peekLast and use ...x once per element in the input. Calling sort on a list of just 100 items will copy over 10,000 elements, for these operations alone. A list of just 1,000 items will copy over 1,000,000 elements. Room for algorithm improvment? For sure.

---

Mark Meyer starts you off on the right foot. If you're going to use recursion, it's best writing your program in functional style, as it will yield the best results. Mixing imperative style (statements, mutations, reassignments, other side effects, etc) with recursion is a recipe for a migraine.

Mark's algorithm, however great a "code improvement", your question is asking for "algorithm improvements". Under this lens, Mark's algorithm suffers from similar intermediate value creation by use of many ...x expressions.

Another lurking offense is the double use of .filter on the same array, rest. This creates an inefficient process as it iterates entirely through rest two (2) times per element. This is a symptom of reaching for low-hanging built-in functions that do close to what you want, but not exactly what you want. A better function would iterate through the array once and return both results.

The inefficiencies in Mark's program are mostly forgivable because of the dramatic improvement in code quality. His program is much more readable than yours because he's using functional style, which is where recursion es from. The inefficiencies are also very easy to fix, so maybe that's an exercise for you?

Let's see if that gets your brain going. We'll see what answers other people submit before smothering you with too much information.

Your code will fail if we have duplicate elements because of this line. if (newLast < last) {

It will go into infinite recursion

Refer the snippet with the duplicate array passed as input

function sort(arr) {
	if (arr.length === 2) {
  	const v1 = arr[0];
    const v2 = arr[1];
    const isGreater = (
    	(isString(v1) && isString(v2) && v1.toString().toLocaleCompare(v2) > 0) ||
      (isNumber(v1) && isNumber(v2) && v1 > v2)
    );
  	return isGreater ? [ v2, v1 ] : [ v1, v2 ];
  } else {
  	const last = arr.pop();
    const ret = sort(arr);
    const newLast = ret.peekLast();
    debugger;
    if (newLast < last) {
      return [ ...ret, last ];
    } else {
    	return sort( [ last, ...ret ] );
    }
  }
}

function isString(value) { return typeof value === 'string'; }
function isNumber(value) { return Number.isFinite(value); }
Array.prototype.peekLast = function () { return this.slice().pop(); }

//console.log(sort([1,2,3,4,5]))

console.log(sort([3,3,5,2]))

this one work for me to sort an array recursively:

var array = [3,1,8,2,4,9,16,28];

const sum = (arr, i=0)=> {
  if(i === arr.length) return arr;
  if(arr[i+1] < arr[i]){
    const x = arr[i+1];
    arr[i+1] = arr[i];
    arr[i] = x;
  }
  return sum(arr,i+1);
}

console.log(sum(array))

function swap(arr, firstIndex, secondIndex){
    let a= arr[firstIndex];
    arr[firstIndex] = arr[secondIndex];
    arr[secondIndex] = a;
  return arr;
}
function sortArr(arr, index=0){
    if(index == arr.length) return arr;
  for(let i=0;i<arr.length; i++){
    if(arr[i] > arr[i+1]){
      arr = swap(arr, i, i+1);
    }
  }
  return sortArr(arr, index+1);
}

console.log(sortArr([4,1,3,2,0]));

function quicksort(num){
    if (num.length < 2){
        return num
    }
    let pivot = num[0];
    let slicedArr = num.slice(1);
    let left = [];
    let right = [];

    for(let i = 0; i < slicedArr.length; i++){
        if(slicedArr[i] <= pivot){
             left.push(slicedArr[i])
        }else{
             right.push(slicedArr[i])
        }
    }
    return [...quicksort(left), pivot, ...quicksort(right)]
}

本文标签： javascriptRecursive sort in JSStack Overflow