Aby pomóc wyjaśnić zachowanie programu Array#sorti jego komparatora, rozważ ten naiwny sposób wstawiania nauczany na początkowych kursach programowania:
const sort = arr => {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j && arr[j-1] > arr[j]; j--) {
[arr[j], arr[j-1]] = [arr[j-1], arr[j]];
}
}
};
const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array);
console.log("" + array);
Ignorując Wybór Sortowanie przez wstawianie jak algorytm, koncentrują się na zakodowanego na stałe komparatora: arr[j-1] > arr[j]. Ma to dwa problemy związane z dyskusją:
>Operator jest wywoływany na parach elementów tablicy, ale wiele rzeczy, których chcesz uporządkować takich jak obiekty nie odpowiadają >w rozsądny sposób (tak samo byłoby prawdziwe, jeśli użyliśmy -).- Nawet jeśli pracujesz z liczbami, często potrzebujesz innego układu niż rosnący, który został tutaj wprowadzony.
Możemy rozwiązać te problemy, dodając comparefnargument, który znasz:
const sort = (arr, comparefn) => {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
[arr[j], arr[j-1]] = [arr[j-1], arr[j]];
}
}
};
const array = [3, 0, 4, 5, 2, 2, 2, 1, 2, 2, 0];
sort(array, (a, b) => a - b);
console.log("" + array);
sort(array, (a, b) => b - a);
console.log("" + array);
const objArray = [{id: "c"}, {id: "a"}, {id: "d"}, {id: "b"}];
sort(objArray, (a, b) => a.id.localeCompare(b.id));
console.log(JSON.stringify(objArray, null, 2));
Teraz uogólniono naiwną rutynę sortowania. Możesz dokładnie zobaczyć, kiedy wywoływane jest to wywołanie zwrotne, odpowiadając na pierwszy zestaw wątpliwości:
Czy funkcja wywołania zwrotnego sortowania w tablicy jest wywoływana wiele razy podczas sortowania? Jeśli tak, chciałbym wiedzieć, które dwie liczby są przekazywane do funkcji za każdym razem
Uruchomienie poniższego kodu pokazuje, że tak, funkcja jest wywoływana wiele razy i możesz jej użyć, console.logaby zobaczyć, które liczby zostały przekazane:
const sort = (arr, comparefn) => {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j && comparefn(arr[j-1], arr[j]) > 0; j--) {
[arr[j], arr[j-1]] = [arr[j-1], arr[j]];
}
}
};
console.log("on our version:");
const array = [3, 0, 4, 5];
sort(array, (a, b) => console.log(a, b) || (a - b));
console.log("" + array);
console.log("on the builtin:");
console.log("" +
[3, 0, 4, 5].sort((a, b) => console.log(a, b) || (a - b))
);
Ty pytasz:
W jaki sposób te dwa zestawy liczb są następnie sortowane względem siebie?
Aby być precyzyjnym z terminologią ai bnie są to zbiory liczb - są to obiekty w tablicy (w twoim przykładzie są to liczby).
Prawda jest taka, że nie ma znaczenia, jak są sortowane, ponieważ jest to zależne od implementacji. Gdybym użył innego algorytmu sortowania niż sortowanie przez wstawianie, komparator byłby prawdopodobnie wywoływany na różnych parach liczb, ale na końcu wywołania sortowania niezmiennikiem, który ma znaczenie dla programisty JS, jest to, że tablica wyników jest sortowana zgodnie z komparator, przy założeniu, że komparator zwraca wartości zgodne z podaną przez Ciebie umową (<0 kiedy a < b, 0 kiedy a === bi> 0 kiedy a > b).
W tym samym sensie, w jakim mam swobodę zmiany implementacji mojego rodzaju, o ile nie naruszę mojej specyfikacji, implementacje ECMAScript mają swobodę wyboru implementacji sortowania w ramach specyfikacji języka , więc Array#sortprawdopodobnie wygenerują różne wywołania komparatorów na różnych silnikach. Nie można pisać kodu, w którym logika opiera się na jakiejś określonej sekwencji porównań (ani też komparator nie powinien przede wszystkim wywoływać skutków ubocznych).
Na przykład silnik V8 (w momencie pisania) wywołuje Timsort, gdy tablica jest większa niż pewna wstępnie obliczona liczba elementów i używa binarnego sortowania przez wstawianie dla małych fragmentów tablicy. Jednak używał szybkiego sortowania, który jest niestabilny i prawdopodobnie dawałby inną sekwencję argumentów i wywołań komparatorowi.
Ponieważ różne implementacje sortowania w różny sposób wykorzystują wartość zwracaną przez funkcję komparatora, może to prowadzić do zaskakującego zachowania, gdy komparator nie przestrzega kontraktu. Zobacz przykład w tym wątku .