Sortowanie liczb w kolejności malejącej, ale z początkiem „0”

Mam wyzwanie w JavaScript, które próbuję już wymyślić.

Rozważ tę tablicę:

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

Muszę przedstawić ten wynik:

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

Podążam tą linią logiczną, aby ustawić zera na wierzchu, dostosowując wartość indeksu:

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

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

    return y - x;
});

Ale utknąłem na tym wyniku:

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

Czy ktoś ma jakieś wskazówki, jak to rozwiązać?

Możesz sortować według delty bi a(dla sortowania malejącego) i brać Number.MAX_VALUE, dla wartości falsy takich jak zero.

To:

Number.MAX_VALUE - Number.MAX_VALUE

jest równy 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);

Jak mdn docs mówi:

Jeśli a i b to dwa porównywane elementy, to:

Jeśli compareFunction(a, b)zwraca mniej niż 0, posortuj awedług indeksu niższego niż b(tzn. Pierwszy jest).

Jeśli compareFunction(a, b)zwraca 0, pozostaw aib niezmienione względem siebie, ale posortowane względem wszystkich różnych elementów. Uwaga: standard ECMAscript nie gwarantuje takiego zachowania, dlatego nie wszystkie przeglądarki (np. Wersje Mozilli z co najmniej 2003 r.) Przestrzegają tego.

Jeśli compareFunction(a, b) zwraca więcej niż 0, posortuj bwedług indeksu niższego niż (tzn. Jest bpierwszy).

compareFunction(a, b)musi zawsze zwracać tę samą wartość, gdy podano określoną parę elementów ai bjako dwa argumenty. Jeśli zwracane są niespójne wyniki, kolejność sortowania jest niezdefiniowana.

Tak więc funkcja porównania ma następującą postać:

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

Jeśli zależy Ci na wydajności, prawdopodobnie najszybciej odfiltruje zera . Nie chcesz sorttracić czasu, nawet na nie patrząc, nie mówiąc już o dodaniu dodatkowej pracy do wywołania zwrotnego porównania w celu obsługi tego specjalnego przypadku.

Zwłaszcza jeśli spodziewasz się znacznej liczby zer, jedno przejście przez dane w celu ich odfiltrowania powinno być znacznie lepsze niż wykonanie większego sortowania O (N log N), który będzie sprawdzał każde zera wiele razy.

Po zakończeniu możesz skutecznie wstawić poprawną liczbę zer.

Równie łatwo jest odczytać wynikowy kod. Użyłem TypedArray, ponieważ jest wydajny i ułatwia sortowanie numeryczne . Ale możesz użyć tej techniki ze zwykłym Array, używając standardowego idiomu (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);
*/

Nie wiem, czy TypedArray, .sort()a następnie .reversejest szybszy niż używanie niestandardowej funkcji porównywania do sortowania w kolejności malejącej. Lub jeśli możemy kopiować i cofać w locie za pomocą iteratora.

Warto również rozważyć: użyj tylko jednego Tablicy Typów o pełnej długości .

Zamiast tego użyj .filterpętli i zamień zera na przód tablicy podczas pracy. To zajmuje jedno przejście przez twoje dane.

Następnie użyj .subarray() aby uzyskać nowy widok TypedArray niezerowych elementów tego samego bazowego ArrayBuffer. Sortowanie, które pozostawia pełną tablicę z zerowym początkiem i posortowanym ogonem, przy czym sortowanie obejmuje tylko niezerowe elementy.

Nie widziałem funkcji partycji w metodach Array ani TypedArray, ale ledwo znam JavaScript. Przy dobrym JIT pętla nie powinna być o wiele gorsza niż wbudowana metoda. (Zwłaszcza gdy ta metoda wymaga wywołania zwrotnego.filter , i jeśli nie używa się reallocpod maską do zmniejszenia, musi dowiedzieć się, ile pamięci do przydzielenia, zanim faktycznie się odfiltruje).

Użyłem tablicy regularnej .filter() przed konwersją na tablicę TypedArray. Jeśli Twój wkład jest już TypedArray, nie masz tego problemu, a ta strategia staje się jeszcze bardziej atrakcyjna.

Po prostu zmodyfikuj stan swojej funkcji porównania w ten sposób -

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

Nie grasz tutaj w golfa kodowego:

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

Nie pisz własnego sortowania numerycznego, jeśli już istnieje. To, co chcesz zrobić, to dokładnie to, co mówisz w tytule; sortuj liczby w kolejności malejącej, z wyjątkiem zer na początku.

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

Nie pisz kodu, którego nie potrzebujesz; możesz to źle pomylić.

Wybierz TypedArray w oparciu o typ liczb, które ma obsługiwać tablica. Float64 jest dobrym domyślnym, ponieważ obsługuje wszystkie normalne liczby JS.

Możesz to zrobić w następujący sposób:

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)

lub możesz to zrobić:

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)