Best algorithm to perform alternate sorting of array using javascript?

Question

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.

Answer 1

Here is a quick solution, using ternary operators and modulo operator for toggling.

let arr = [1, 4, 5, 8, 3, 2, 6, 9, 7, 10];
let j = 0;
let k = arr.length - 1;

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

let new_array = [];
for (let i in arr) {
  new_array[i] = i % 2 == 0 ? arr[k--] : arr[j++];
}
// prints array
console.log(new_array);

Answer 2

var a = [1,4,5,8,3,2,6,9,7,10];
var b = a.sort((a, b) => a - b);
var c = a.sort((a, b) => a - b).reverse();
var d = [];

let e = a.length-1;
let f = e/2;

for(let i=0; i<f; i++)  d.push( b.pop(), c.pop() );

Replace b and c in the for loop with functions to test:

for(let i=0; i<f; i++) d.push( a.sort((a, b) => a - b).pop(), a.sort((a, b) => a - b).reverse().pop() );

Answer 3

I would sort the array, and then iterate it, picking values from the begining and the end (inloop calculated offsets), in each iteration. A final check to odd arrays would complete the process.

let 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(var i=0; i<L; i++) b.push( a[l-i] ,a[i] );
if(a.length%2) b.push( a[i] ); // add last item in odd arrays

console.log(b);

Result :

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

Algorithm bennefits:

• 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.
• A single conditional cheking at the end of the procces, to handle odd arrays, slightly improves the speed.

I've prepared some PERFORMANCE TESTS, with some of the proposed algorithms : Original Array(10 items) and Big Array(1000 items)

Answer 4

My solution for readability / no hidden magic:

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

// Sort
var arr1 = arr.sort((a,b) => (a - b));

// Compose
var arr2 = [];
for (var i = 0; i < arr1.length; i++) {
  arr2.push(arr1[(i % 2) === 0 
    ? arr1.length-1-(i/2)   // get from end half
    : (i-1)/2               // get from begin half
  ])
}

// Output
console.log(arr2); // = [10, 1, 9, 2, 8, 3, 7, 4, 6, 5] 

Their interview answer "that the algorithm is not optimal." is not unexpected ofcourse. I would inquire why they say that, and ask if its really benefitial to spend dollar time on dimes here. (or tens of dollars on cents, actually)

Answer 5

Here is one way to do it:

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

// Sort the source array
arr.sort((a, b) => a - b);

// This will be the final result
var result = [];

// Create two pointers
var a = 0,
  b = arr.length - 1;

while (result.length < arr.length) {
  // Push the elements from start and end to the result array
  result.push(arr[b]);

  // Avoid bug when array is odd lengthed
  if (a !== b) {
    result.push(arr[a]);
  }

  a++;
  b--;
}

console.log(result);

The idea is to have two pointers (a and b) traversing the the sorted original array from both the directions and appending the elements in result.

Answer 6

If you assume that the array will be a set of sequential numbers (a good question to ask about the data) you can do this very quickly with no need to sort or mutate the original array(i.e O(n)):

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

let a = arr.reduce((a, c, i) => {
  a[c > arr.length >> 1 ? (arr.length - c) << 1 : (c << 1) - 1] = c
  return a
}, [])
console.log(a)

Answer 7

Another alternative view ... should this funky sort be done in place, like .sort is?

let input = [1, 4, 5, 8, 3, 2, 6, 9, 7, 10];
input.sort((a, b) => b - a).every((n, i, a) => (a.splice((i * 2 + 1), 0, a.pop()), (i * 2) < a.length));
console.log(input);

Answer 8

sort the array and divide into two parts , now use reduce to put elements from the two arrays

//original array
var arr = [1, 4, 5, 8, 3, 2, 6, 9, 7, 10];
//sorting origina array in ascending order
var m = arr.sort(function(a, b) {
  return a - b;
});

// diving the sorted array in two parts
let getFirstSet = m.splice(0, arr.length / 2);
// now m containleft over items after the splice
// again sorted it in descending order to avoid back looping
let getSecondSet = m.sort(function(a, b) {
  return b - a;
});

//using reduce function
let newArray = getFirstSet.reduce(function(acc, curr, index) {
  // pushing element from second array containing 10,9,8,7,6
  acc.push(getSecondSet[index]);
  // pushing element from first array containing 1,2,3,4,5
  acc.push(getFirstSet[index]);
  return acc;
}, []); // [] is the initial array where elements will be pushed

console.log(newArray)

Answer 9

Here's my answer, based off the intuition that you're taking from the front then the back repeatedly from the sorted array until you're empty. The trick is avoiding "max" and "min" which evaluate the entire array, and just sorting it once.

Many of the other answers will put an undefined into the array if the original array has an odd length. I would leave a comment on those but I do not have the reputation. This is why I bounds check twice per loop.

var arr = [1,4,5,8,3,2,6,9,7,10];
// Sort numerically (not lexicographically)
arr.sort((a, b) => a - b)
// The output array
var out = []
// Take from the front, then back until original array is empty
while (true) {
  if (arr.length == 0) break
  out.push(arr.pop())
  if (arr.length == 0) break
  out.push(arr.shift())
}
// Output answer
console.log(out)

Answer 10

Alternative method with only one variable to increment:

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

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

var result = [];

var a = 0;
while (result.length < arr.length) {
    result.push(arr[a]);
    result.push(arr[arr.length - a - 1]);
    a++;
}

console.log(result);