Jak działa sort () w JavaScript?

W jaki sposób poniższy kod sortuje tę tablicę w kolejności numerycznej?

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  return a - b
})

Wiem, że jeśli wynik obliczeń to ...

Mniejsze niż 0 : „a” jest sortowane jako indeks niższy niż „b”.
Zero: „a” i „b” są uważane za równe i nie jest wykonywane sortowanie.
Większe niż 0: „b” jest sortowane jako indeks niższy niż „a”.

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ą za każdym razem przekazywane do funkcji. Założyłem, że najpierw zajęło "25" (a) i "8" (b), a następnie "7" (a) i "41" (b), więc:

25 (a) - 8 (b) = 17 (większe od zera, więc posortuj „b” tak, aby był niższy niż „a”): 8, 25

7 (a) - 41 (b) = -34 (mniej niż zero, więc posortuj „a” tak, aby był niższy niż „b”: 7, 41

W jaki sposób te dwa zestawy liczb są następnie sortowane względem siebie?

Proszę, pomóż borykającemu się nowicjuszowi!

Czy funkcja wywołania zwrotnego sortowania w tablicy jest wywoływana wiele razy podczas sortowania?

tak

Jeśli tak, chciałbym wiedzieć, które dwie liczby są przekazywane do funkcji za każdym razem

Możesz dowiedzieć się czegoś o sobie dzięki:

array.sort((a,b) => {
  console.log(`comparing ${a},${b}`);
  return a > b ? 1
               : a === b ? 0 
                         : -1;
});

EDYTOWAĆ

Oto wynik, który otrzymałem:

25,8
25,7
8,7
25,41

Interpreter JavaScript ma wbudowaną pewnego rodzaju implementację algorytmu . Podczas sortowania wywołuje funkcję porównania kilka razy. Liczba wywołań funkcji porównawczej zależy od konkretnego algorytmu, sortowanych danych i kolejności, w jakiej się znajdują przed sortowaniem.

Niektóre algorytmy sortowania działają słabo na już posortowanych listach, ponieważ powoduje to dokonywanie znacznie większej liczby porównań niż w typowym przypadku. Inni radzą sobie dobrze ze wstępnie posortowanymi listami, ale zdarzają się inne przypadki, w których można ich „oszukać”, aby działały źle.

W powszechnym użyciu jest wiele algorytmów sortowania, ponieważ żaden pojedynczy algorytm nie jest idealny do wszystkich celów. Dwa najczęściej używane do sortowania ogólnego to szybkie sortowanie i sortowanie przez scalanie . Szybkie sortowanie jest często szybsze z tych dwóch, ale sortowanie przez scalanie ma kilka fajnych właściwości, które mogą uczynić go lepszym ogólnym wyborem. Sortowanie przez scalanie jest stabilne , a szybkie sortowanie nie. Oba algorytmy można zrównoleglenie, ale sposób, w jaki działa sortowanie przez scalanie, sprawia, że ​​implementacja równoległa jest bardziej wydajna, a wszystko inne jest równe.

Twój konkretny interpreter JavaScript może używać jednego z tych algorytmów lub czegoś zupełnie innego. ECMAScript norma nie określa, który algorytm Wykonanie zgodne muszą używać. Nawet wyraźnie odrzuca potrzebę stabilności.

Porównywane są pary wartości, jedna para naraz. Porównywane pary stanowią szczegół implementacji - nie zakładaj, że będą takie same w każdej przeglądarce. Wywołanie zwrotne może być dowolne (więc możesz sortować ciągi znaków, cyfry rzymskie lub cokolwiek innego, gdzie możesz wymyślić funkcję zwracającą 1,0, -1).

Jedną rzeczą, o której należy pamiętać przy sortowaniu JavaScript jest to, że nie ma gwarancji, że będzie stabilny.

Czy funkcja wywołania zwrotnego sortowania w tablicy jest wywoływana wiele razy podczas sortowania?

Tak, dokładnie to. Funkcja zwrotna służy do porównywania par elementów w tablicy, jeśli jest to konieczne, aby określić, w jakiej kolejności powinny się one znajdować. Ta implementacja funkcji porównania nie jest nietypowa w przypadku sortowania liczbowego. Szczegóły w specyfikacji lub w niektórych innych bardziej czytelnych stron.

Czy funkcja wywołania zwrotnego sortowania w tablicy jest wywoływana wiele razy podczas sortowania?

Ponieważ jest to sortowanie porównawcze, biorąc pod uwagę N elementów, funkcja zwrotna powinna być wywoływana średnio (N * Lg N) razy w przypadku szybkiego sortowania, takiego jak Quicksort . Jeśli użyty algorytm to coś w rodzaju Bubble Sort , wówczas funkcja wywołania zwrotnego będzie wywoływana średnio (N * N) razy.

Minimalna liczba wywołań sortowania porównawczego to (N-1) i to tylko w celu wykrycia już posortowanej listy (tj. Wcześnie w sortowaniu bąbelkowym, jeśli nie ma zamiany).

Głęboka wiedza

Jeśli wynik jest ujemny, a jest sortowany przed b.

Jeśli wynik jest pozytywny, b jest sortowane przed a.

Jeśli wynikiem jest 0, żadne zmiany nie zostaną wprowadzone w kolejności sortowania dwóch wartości.

UWAGA:

Ten kod to widok wewnątrz metody sortowania krok po kroku.

WYNIK:

let arr = [90, 1, 20, 14, 3, 55];
var sortRes = [];
var copy = arr.slice();		//create duplicate array
var inc = 0;	//inc meant increment
copy.sort((a, b) => {
	sortRes[inc] = [ a, b, a-b ];
	inc += 1;
	return a - b;
});
var p = 0;
for (var i = 0; i < inc; i++) {
	copy = arr.slice();
	copy.sort((a, b) => {
		p += 1;
		if (p <= i ) {
			return a - b;
		}
		else{
			return false;
		}
	});
	p = 0;
	console.log(copy +' \t a: '+ sortRes[i][0] +' \tb: '+ sortRes[i][1] +'\tTotal: '+ sortRes[i][2]);
}

uruchom ten kod. Możesz zobaczyć dokładny proces sortowania od początku do końca.

var array=[25, 8, 7, 41]
var count = 1;
array.sort( (a,b) => { 
console.log(`${count++}). a: ${a} | b: ${b}`);
return a-b;
});
console.log(array);

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ą:

1. >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 -).
2. 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 .

var array=[25, 8, 7, 41]

array.sort(function(a,b){
  console.log(`a = ${a} , b = ${b}`);
  return a - b
});

WYNIK

• a = 8, b = 25
• a = 7, b = 8
• a = 41, b = 7
• a = 41, b = 8
• a = 41, b = 25

w mojej przeglądarce (Google Chrome wersja 70.0.3538.77 (oficjalna kompilacja) (64-bitowa)) w pierwszej iteracji argument a jest drugim elementem tablicy, a argument b jest pierwszym elementem tablicy.

jeśli funkcja Porównaj zwróci

1. Wartość ujemna niż b jest przenoszona do przodu do a.
2. Wartość dodatnia niż a jest przenoszone do przodu do b.
3. 0 (Zero) oba a i b pozostaną niezmienione.