Sorting numbers in descending order but with `0`s at the start

Question

I have a challenge in JavaScript that I’m trying to figure out for a while already.

Consider this array:

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

I have to output this result:

arr = [0, 0, 0, 0, 0, 5, 4, 3, 2, 1]

I’m following this line of logic to position the zeros in front, adjusting the index value:

arr.sort((x, y) => {
    if (x !== 0) {
        return 1;
    }

    if (x === 0) {
        return -1;
    }

    return y - x;
});

But I’m stuck at this result:

arr = [0, 0, 0, 0, 0, 1, 2, 3, 4, 5]

Does anyone have any tips on how to solve this?

Answer 1

You could sort by the delta of b and a (for descending sorting) and take Number.MAX_VALUE, for falsy values like zero.

This:

Number.MAX_VALUE - Number.MAX_VALUE

is equal to zero.

let array = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

array.sort((a, b) => (b || Number.MAX_VALUE) - (a || Number.MAX_VALUE));

console.log(...array);

Answer 2

As mdn docs says:

If a and b are two elements being compared, then:

If compareFunction(a, b) returns less than 0, sort a to an index lower than b (i.e. a comes first).

If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behavior, thus, not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.

If compareFunction(a, b) returns greater than 0, sort b to an index lower than a (i.e. b comes first).

compareFunction(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned, then the sort order is undefined.

So, the compare function has the following form:

function compare(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  }
  if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

arr.sort((x, y) => {
    if (x > 0 && y > 0) {
        return y - x;
    }
    return x - y;
});

console.log(arr);

Answer 3

If you care about efficiency, it's probably fastest to filter out the zeros first. You don't want sort to waste time even looking at them, let alone adding extra work to your comparison callback to handle that special case.

Especially if you expect a significant number of zeros, one pass over the data to filter them out should be much better than doing a larger O(N log N) sort that will look at each zero multiple times.

You can efficiently prepend the right number of zeros after you're done.

It's also just as easy to read the resulting code. I used TypedArray because it's efficient and makes numeric sorting easy. But you can use this technique with regular Array, using the standard idiom of (a,b)=>a-b for .sort.

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

let nonzero_arr = Int32Array.from(arr.filter(n => n != 0));
let zcount = arr.length - nonzero_arr.length;
nonzero_arr.sort();      // numeric TypedArray sorts numerically, not alphabetically

// Reverse the sorted part before copying into the final array.
nonzero_arr.reverse();

 // efficient-ish TypedArray for main result
let revsorted = new Int32Array(arr.length);   // zero-filled full size
revsorted.set(nonzero_arr, zcount);           // copy after the right number of zeros

console.log(Array.from(revsorted));      // prints strangely for TypedArray, with invented "0", "1" keys

/*
   // regular Array result
let sorted = [...Array(zcount).fill(0), ...nonzero_arr]  // IDK if this is efficient
console.log(sorted);
*/

I don't know if TypedArray .sort() and then .reverse is faster than using a custom comparison function to sort in descending order. Or if we can copy-and-reverse on the fly with an iterator.

---

Also worth considering: only use one TypedArray of the full length.

Instead of using .filter, loop over it and swap the zeros to the front of the array as you go. This takes one pass over your data.

Then use .subarray() to get a new TypedArray view of the non-zero elements of the same underlying ArrayBuffer. Sorting that will leave you the full array with a zero start and a sorted tail, with the sort only ever looking at the non-zero elements.

I didn't see a partition function in the Array or TypedArray methods, but I barely know JavaScript. With good JIT, a loop shouldn't be too much worse than a built-in method. (Especially when that method involves a callback like .filter, and unless it uses realloc under the hood to shrink, it has to figure out how much memory to allocate before it actually filters).

I used regular-Array .filter() before converting to a TypedArray. If your input is already a TypedArray you don't have this problem, and this strategy gets even more attractive.

Answer 4

Just modify the condition of your compare function like this -

let arr = [-1, 0, 1, 0, 2, -2, 0, 3, -3, 0, 4, -4, 0, 5, -5];
arr.sort((a, b) => {
   if(a && b) return b-a;
   if(!a && !b) return 0;
   return !a ? -1 : 1;
});

console.log(arr);

Answer 5

Not playing code golf here:

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, -1];
arr.sort(function(a, b) {
  if (a === 0 && b !== 0) {
    // a is zero b is nonzero, a goes first
    return -1;
  } else if (a !== 0 && b === 0) {
    // a is nonzero b is zero, b goes first
    return 1;
  } else {
    // both are zero or both are nonzero, sort descending
    return b - a;
  }
});
console.log(arr.toString());

Answer 6

Don't write your own numeric sorting if it already exists. What you want to do is exactly what you say in the title; sort numbers in descending order except zeroes at the start.

const zeroSort = arr => [...arr.filter(n => n == 0),
                         ...new Float64Array(arr.filter(n => n != 0)).sort().reverse()];

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

Don't write any code you don't need to; you might get it wrong.

Pick the TypedArray based on what Type of numbers you want the Array to handle. Float64 is a good default since it handles all normal JS numbers.

Answer 7

You can do this like this:

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

let result = arr.sort((a,b) => {
  if(a == 0 || b == 0)
    return a-b;
  return b-a;
})
console.log(result)

or you can do this:

let arr = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];

let result = arr.sort().sort((a,b) => {
  if(a > 0 && b > 0)
    return b-a
  return 0
})

console.log(result)

Answer 8

most of the answers above are not optimum keeping following real life scenario:

1. not always 0 is to be filtered out. so all answers which use Only Sort function are not good enough per me
2. inputs not always will be integers, but strings or even objects to be compared during sort. so answers using TypedArray for doing Sort and Reverse are not good enough

i would prefer something like following

function customSort( source, target )  { target - source } // a custom sorting depending on business logic required

function sortAndFilter(inputArray, candidateValue) { // a Candidate Value to be filtered out

// step 1: use optimized custom sort (think Merge Sort) to sort all items. You would like to pass candidateValue(s) to be Not considered for sorting and move them to separate list or at beginning/end of the array depending on business logic

const reversedArray = inputArray.sort( customSort);

// step 2: merge the sorted list(s) with custom logic. in this case its just moving the candidateValue to front and removing from elsewhere so following is good enough
reversedArray.forEach( (item, index) => {
    if (item === candidateValue) {
        reversedArray.splice(index, 1)
        reversedArray.unshift(item)
    }
});
return reversedArray
}

console.log(sortAndFilter(arr,0))

Answer 9

const myArray = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5];
const splitArray = myArray.reduce((output, item) => {
     if(!item) output[0].push(item);
    else output[1].push(item);
    return output;
}, [[], []]);
const result = [...splitArray[0], ...splitArray[1].reverse()]
console.log(result);