admin管理员组文章数量:1323524
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 thanpreviousLast
- Push
previousLast
as first element and again call itself with this array.
- Push
- 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!
Share Improve this question asked Jan 2, 2019 at 6:18 RajeshRajesh 25k5 gold badges50 silver badges83 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
6 Answers
Reset to default 3I 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.
peekLast
callsArray.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.
Use of spread arguments in expressions like
[ ...arr, x ]
copiesarr
entirely.arr.concat([ x ])
does the same thing without making copy (or mutation) ofarr
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
版权声明:本文标题:javascript - Recursive sort in JS - Stack Overflow 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.betaflare.com/web/1742131722a2422191.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论