4

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!

Improve this question
2
  • @downvoter, feel free to share your feedback. We all are here to learn 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. Commented Jan 2, 2019 at 6:36

6 Answers 6

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(', '))

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Nice readability improvement, but contains similar (easily avoidable) inefficiencies. Guessing, but OP seems to care more about improvements to the computational process and less about the code itself.
Use of let communicates to me that the variable will be reassigned. Why not use const bindings here?
Yeah, @user633183, let is just SO habit. declaring with const is clearer. As far as optimizations, I really wanted to make the algorithm crystal clear. I hoped the comments would be enough to indicate where improvements could be made.
Honestly, I missed the source comment before remarking upon the doubled cycles. Sorry about that. It's a good answer.
1

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]))

Improve this answer

1 Comment

Thanks! Update code to support that as well. updated fiddle
0

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 comes 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.

Improve this answer

2 Comments

Just to be clear—the two filters does not make this exponential! Quicksort needs to scan the array to partition it — that's the N component in the O(N log N) typical behavior. This does it twice rather than once. It's still a linear operation. It can be optimized but it doesn't change the big-O complexity of the function.
You're right it's not actually an exponential process. Quick sort does need to scan the array, once but not twice.
0

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))

Improve this answer

Comments

0 
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]));
Improve this answer

1 Comment

Your answer could be improved by adding more information on what the code does and how it helps the OP.
-1 
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)]
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.