Best algorithm to perform alternate sorting of array using javascript?

  • A+
Category:Languages

The following was my interview question. But I couldn't crack it and even could not think how to get this done.

var arr = [1,4,5,8,3,2,6,9,7,10]; 

Expected output of alternate sorting:

[10,1,9,2,8,3,7,4,6,5] 

What I have tried:
I tried slicing out the Math.max.apply(null,arr) and Math.min.apply(null,arr) alternatively to push into separate empty array. But It was told that the algorithm is not optimal.


I would sort the array, and then iterate it, picking the last and the first value, in each iteration

let a = [1, 4, 5, 8, 3, 2, 6, 9, 7, 10]; a.sort((a, b) => a - b); let b = []; while(a.length) b.push( a.pop(), a.shift() ); 

Result :

b =  [10, 1, 9, 2, 8, 3, 7, 4, 6, 5] 

Edit : This is a better solution, using the same concept, but without modifying the original array (improved performance), and a couple of micro optimizations :

var a = [1, 4, 5, 8, 3, 2, 6, 9, 7, 10]; a.sort((a, b) => a - b); let b =[];  let l = a.length-1;  // micro optimization let L = l/2;         // micro optimization for(let i=0; i<L; i++) b.push( a[l-i] ,a[i] ); 

Algorithm improvements:

  • Avoiding alterations in the original array (through pop and shift), improves the performance considerably.
  • Precalculating l and L before the loop , prevents the need of being calculated repeatedly in each iteration.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: