Tri des nombres dans l'ordre décroissant mais avec des «0» au début

J'ai un défi en JavaScript que j'essaie de comprendre depuis un moment déjà.

Considérez ce tableau:

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

Je dois sortir ce résultat:

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

Je suis cette ligne de logique pour positionner les zéros devant, en ajustant la valeur d'index:

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

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

    return y - x;
});

Mais je suis bloqué sur ce résultat:

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

Quelqu'un a-t-il des conseils pour résoudre ce problème?

Vous pouvez trier par le delta de bet a(pour le tri décroissant) et prendre Number.MAX_VALUE, pour des valeurs fausses comme zéro.

Cette:

Number.MAX_VALUE - Number.MAX_VALUE

est égal à zéro.

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

Comme le dit mdn docs:

Si a et b sont deux éléments comparés, alors:

Si compareFunction(a, b)renvoie moins de 0, triez aselon un indice inférieur à b(c.-à-d. A vient en premier).

Si compareFunction(a, b)renvoie 0, laissez a et b inchangés l'un par rapport à l'autre, mais triés par rapport à tous les différents éléments. Remarque: la norme ECMAscript ne garantit pas ce comportement, donc tous les navigateurs (par exemple les versions de Mozilla datant d'au moins 2003) respectent cela.

Si compareFunction(a, b) renvoie plus de 0, triez bsur un index inférieur à a (c'est-à-dire bvient en premier).

compareFunction(a, b)doit toujours renvoyer la même valeur lorsque donné une paire spécifique d'éléments aet bcomme ses deux arguments. Si des résultats incohérents sont renvoyés, l'ordre de tri n'est pas défini.

Ainsi, la fonction de comparaison a la forme suivante:

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

Si vous vous souciez de l'efficacité, il est probablement plus rapide de filtrer les zéros en premier . Vous ne voulez sortpas perdre de temps, même en les regardant, sans parler d'ajouter du travail supplémentaire à votre rappel de comparaison pour gérer ce cas spécial.

Surtout si vous vous attendez à un nombre important de zéros, un passage sur les données pour les filtrer devrait être bien mieux que de faire un tri O (N log N) plus grand qui examinera chaque zéro plusieurs fois.

Vous pouvez ajouter efficacement le bon nombre de zéros après avoir terminé.

Il est également tout aussi facile de lire le code résultant. J'ai utilisé TypedArray car il est efficace et facilite le tri numérique . Mais vous pouvez utiliser cette technique avec un tableau standard, en utilisant l'idiome standard de (a,b)=>a-bfor .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);
*/

Je ne sais pas si TypedArray .sort()puis .reverseest plus rapide que d'utiliser une fonction de comparaison personnalisée pour trier par ordre décroissant. Ou si nous pouvons copier et inverser à la volée avec un itérateur.

À considérer également: n'utilisez qu'un seul TypedArray de toute la longueur .

Au lieu de l'utiliser .filter, faites une boucle dessus et permutez les zéros à l'avant du tableau au fur et à mesure. Cela prend un seul passage sur vos données.

Ensuite, utilisez .subarray()pour obtenir une nouvelle vue TypedArray des éléments non nuls du même ArrayBuffer sous-jacent. Un tri qui vous laissera le tableau complet avec un début zéro et une queue triée, le tri ne regardant que les éléments non nuls.

Je n'ai pas vu de fonction de partition dans les méthodes Array ou TypedArray, mais je connais à peine JavaScript. Avec un bon JIT, une boucle ne devrait pas être bien pire qu'une méthode intégrée. (Surtout lorsque cette méthode implique un rappel .filter, et à moins qu'elle n'utilise reallocsous le capot pour rétrécir, elle doit déterminer la quantité de mémoire à allouer avant qu'elle ne filtre réellement).

J'ai utilisé regular-Array .filter() avant de convertir en TypedArray. Si votre entrée est déjà un TypedArray, vous n'avez pas ce problème et cette stratégie devient encore plus attrayante.

Modifiez simplement l'état de votre fonction de comparaison comme ceci -

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

Ne joue pas au golf de code ici:

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

N'écrivez pas votre propre tri numérique s'il existe déjà. Ce que vous voulez faire, c'est exactement ce que vous dites dans le titre; trier les nombres dans l'ordre décroissant sauf les zéros au début.

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

N'écrivez aucun code dont vous n'avez pas besoin; vous pourriez vous tromper.

Choisissez le tableau typé en fonction du type de nombres que vous souhaitez que le tableau gère. Float64 est une bonne valeur par défaut car il gère tous les nombres JS normaux.

Vous pouvez faire ceci comme ceci:

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)

ou vous pouvez le faire:

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)