Sortowanie w JavaScript #43

Dawid R. -

W obiekcie Array mamy do dyspozycji metodę sort. Ma ona kilka zasad działania i aby sprawnie się nią posługiwać, warto zaznajomić się dokładnie z jej działaniem.

Metoda sort

Na początek po prostu wywołajmy metodę sort:

const arr1 = [2, 4, 5, 1, 3];
arr1.sort();
console.log(arr1); // [ 1, 2, 3, 4, 5 ]

Metoda sort wywołana na tablicy bez przekazanej funkcji callback sortuje elementy od najmniejszego do największego. Widzimy też, że metoda sort zmienia nam oryginalną tablicę. Dlatego, jeżeli nie chcemy modyfikować oryginalnej tablicy, przed sortowaniem należy wykonać kopię na przykład z
operatorem spread albo z metodą slice.

Jak wspomniałem wcześniej metoda sort bez dodatkowej funkcji callback sortuje rosnąco:

const arr2 = [2, 100, 30];
arr2.sort();
console.log(arr2); //   [ 100, 2, 30 ]

Ten przykład pokazuje jednak coś zupełnie innego i wydaje się, że tym razem tablica została źle posortowana. Wszystko jest jednak w porządku, jeśli chodzi o standardowe działanie metody sort. Bez funkcji callback, która najczęściej nazywana jest comparatorem metoda sort sortuje w sposób
leksykograficzny.

Wszystkie wartości zmieniane są do wartości string i porównywane są przez znaki kodowe w standardzie UTF-16. Oznacza to, że liczba 100 zamieniona na stringa, ma mniejszy znak kodowy niż liczba 2 reprezentowana jako string. W naszym odbiorze sortowane wydaje się nieprawidłowe, jednak dla
komputera wykonane jest prawidłowo.

Dlatego, jeżeli chcemy sortować tablice, warto zadbać o zaimplementowanie prawidłowego comparatora, którego przekażemy jako funkcję.

Komparator dla metody sort

Aby uniknąć standardowego sortowania przez porównanie kodów Unicode w systemie UTF-16, możemy stworzyć i przekazać do metody sort funkcję callback, funkcja ta często jest nazywana comparator.

const arr3 = [2, 100, 30];
const comparatorASC = (a, b) => {
  if (a < b) {
    return -1;
  } else if (a > b) {
    return 1;
  } else if (a === b) {
    return 0;
  }
};
arr3.sort(comparatorASC);
console.log(arr3); // [ 2, 30, 100 ]

Stworzyłem funkcję comparator z rozbudowaną instrukcją if, ale można to wszystko zapisać krócej, co zobaczymy później. Zrobiłem to jednak specjalnie, aby Wam pokazać jakie wartości i kiedy należy zwracać przy porównaniu.

Jest to comparator do sortowania rosnącego. Funkcja comparator przy każdej iteracji, przyjmuje dwa elementy. Jeżeli element a jest mniejszy niż b zwracamy wartość mniejszą niż zero, nie musi być to -1 ale dowolna ujemna wartość. Jeżeli więc z komparatora, zwracamy wartość ujemną przy
porównaniu dwóch elementów, oznacza to, że pierwszy element w sortowaniu powinien być przed elementem drugim. Czyli w tym przypadku a powinno być w tablicy zawsze przed b. Nie ma żadnych zmian.

Jeżeli zwrócimy wartość większą niż 0 oznacza to, że drugi element, czyli b powinien być przed elementem a. Elementy zamieniane są miejscami.

Jeżeli zwracamy wartość 0 oznacza to, że oba elementy są równe sobie i nie musi następować zmiana ich pozycji w tablicy.

const comparatorDESC = (a, b) => {
  if (a < b) {
    return 1;
  } else if (a > b) {
    return -1;
  } else if (a === b) {
    return 0;
  }
};
arr3.sort(comparatorDESC);
console.log(arr3); // [ 100, 30, 2 ]

Jeżeli natomiast chcemy sortować malejąco, przy odpowiednich porównaniach musimy zwrócić odwrotne wartości. W tym przypadku sortowania, jeżeli a będzie mniejsze od b zwracamy 1 . Oznacza to, że wartość b jako większa będzie stałą teraz przed wartością a.

Jeżeli a jest większe od b zwracamy -1, oznacza to, że w tablicy a jest większe, więc powinno być przed wartością b w sortowanej tablicy. Elementy pozostają bez zmian. Podobnie jest, gdy zwracamy wartość 0. Elementy również nie zmieniają miejsc.

Możemy to wytłumaczyć jeszcze krócej. Jeżeli zwrócimy z comparatora wartość powyżej zera, elementy a i b są zamieniane w tablicy. Jeżeli zwrócimy wartość zero lub mniejszą niż zerwo, elementy pozostają bez zmian.

Krótszy zapis komparatorów

Komparatory, które Wam pokazałem, można zapisać o wiele krócej:

const arr4 = [2, 1, 5, 4, 3];
arr4.sort((a, b) => a - b);
console.log(arr4); // [ 1, 2, 3, 4, 5 ]

Do metody sort przekazałem compoarator sortujący rosnąco. W tym przypadku zwracamy po prostu wynik różnicy. Będzie to zawsze jakaś wartość mniejsza niż 0, większa niż 0 lub po prostu 0. Metoda sort podejmuje odpowiednie działania, albo zamienia elementy, albo pozostawia na miejscu.

Jeżeli natomiast chcemy sortować malejąco, użyjemy takiego zapisu:

arr4.sort((a, b) => b - a);
console.log(arr4); // [ 5, 4, 3, 2, 1 ]

Tym razem od wartości b odejmujemy wartość a. W ten sposób odwracamy sortowanie i sortujemy malejąco.

Ten zapis jest na pewno krótki i zwięzły, ale może być trudniejszy w zrozumieniu, szczególnie dla osób, które dopiero stykają się z metodą sort.

Sortowanie wartości string

Czasami będziemy też musieli posortować wartości string. Musimy pamiętać, że porównywane są znaki według tabeli Unicode, co nie zawsze daje oczekiwane rezultaty. Jest jednak na to sposób:

const persons = ['ZoE', 'AnDy', 'Marie'];
persons.sort((a, b) => a.localeCompare(b));
console.log(persons);

Jeżeli będziemy chcieli stworzyć comparator dla wartości string najlepszą opcją może być użycie metody localeCompare
. Metodę wywołujemy na wartości string i przekazujemy jako parametr drugi string do porównania. Metoda ta po porównaniu wróci nam odpowiednią wartość number dla metody sort.

Użycie localCompare załatwia nam dużo problemów, gdy wartości string mają różne wielkości liter i znaki spoza tablic ASCII. Wydaje się, że dla elementów string jest to najlepsze rozwiązanie.

Co warto zapamiętać

  • standardowo metoda sort sortuje rosnąco

  • standardowo metoda sort konwertuje wszystko do string i potem porównuje znaki według kodów Unicode.

  • jeżeli chcemy sortować według własnej metody, musimy stworzyć i przekazać funkcję comparator czyli zwykłą funkcję callback

  • gdy comparator zwraca wartość powyżej 0, elementy w tablicy są zamieniane

  • gdy comparator zwraca wartość równą 0, elementy w tablicy pozostają bez zmian

  • gdy comparator zwraca wartość poniżej 0, elementy w tablicy pozostają bez zmian

  • gdy sortujemy wartości string porównajmy je za pomocą metody `localeCompare'

    Główny spis treści.