Come funziona sort() di JavaScript?

Question

In che modo il codice seguente ordina questa matrice in ordine numerico?

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

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

So che se il risultato del calcolo è ...

Meno di 0: "a" è ordinato ad essere un indice inferiore a "b".
Zero: "a" e "b" sono considerati uguali e non viene eseguito alcun ordinamento.
Maggiore di 0: "b" è ordinato per essere un indice inferiore a "a".

La funzione di richiamata di ordinamento di array viene richiamata più volte nel corso dell'ordinamento?

In tal caso, mi piacerebbe sapere quali due numeri vengono passati alla funzione ogni volta. Ho pensato che fosse necessario prima "25" (a) e "8" (b), seguito da "7" (a) e "41" (b), quindi:

25 (a) - 8 (b) = 17 (maggiore di zero, quindi ordinare "b" per essere un indice inferiore a "a"): 8, 25

7 (a) - 41 (b) = -34 (meno di zero, quindi ordinare " a" per essere un indice inferiore a "b":?! 7, 41

Come sono i due insiemi di numeri poi ordinati in relazione l'uno all'altro

Aiutateci un principiante che lotta

Answer 1

La funzione di richiamata di ordinamento di array viene richiamata più volte nel corso dell'ordinamento?

Sì

Se è così, mi piacerebbe sapere che due numeri sono passati nella funzione ogni volta

Si potrebbe scoprire la vostra auto con:

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

E DIT

Questa è l'uscita che ho:

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

Answer 2

Is l'arra y ordina la funzione di callback richiamata più volte nel corso del genere?

Sì, è esattamente così. Il callback viene utilizzato per confrontare coppie di elementi nella matrice in base alle necessità per determinare l'ordine in cui devono essere inseriti. Tale implementazione della funzione di confronto non è atipica quando si ha a che fare con un ordinamento numerico. Dettagli su the spec o su some altri siti more readable.

Answer 3

L'interprete JavaScript ha una sorta di implementazione sort algorithm incorporata. Chiama la funzione di confronto un certo numero di volte durante l'operazione di ordinamento. Il numero di volte che la funzione di confronto viene chiamata dipende dal particolare algoritmo, dai dati da ordinare e dall'ordine in cui si trova prima dell'ordinamento.

Alcuni algoritmi di ordinamento funzionano in modo insufficiente su elenchi già ordinati perché causano molti più confronti rispetto al caso tipico. Altri si adattano bene alle liste pre-ordinate, ma hanno altri casi in cui possono essere "ingannati" in prestazioni scadenti.

Ci sono molti algoritmi di ordinamento in uso comune perché nessun singolo algoritmo è perfetto per tutti gli scopi. I due più usati per lo smistamento generico sono Quicksort e merge sort. Quicksort è spesso il più veloce dei due, ma l'unisci sort ha alcune buone proprietà che possono renderlo una scelta globale migliore. Unisci ordina è stable, mentre Quicksort non lo è. Entrambi gli algoritmi sono parallelizzabili, ma il modo in cui unire i lavori di ordinamento rende l'implementazione parallela più efficiente, a parità di tutti gli altri.

Il tuo particolare interprete JavaScript può utilizzare uno di questi algoritmi o qualcos'altro interamente. Lo standard ECMAScriptdoes not specify which algorithm deve essere utilizzato da un'implementazione conforme. Rinuncia anche esplicitamente alla necessità di stabilità.

Answer 4

coppie di valori vengono confrontati, un paio alla volta. Le coppie confrontate rappresentano un dettaglio di implementazione, non assumendo che saranno uguali su tutti i browser. Il callback può essere qualsiasi cosa (in modo da poter ordinare stringhe o numeri romani o qualsiasi altra cosa in cui è possibile trovare una funzione che restituisce 1,0, -1).

Una cosa da tenere a mente con il tipo di JavaScript è che non è garantito che sia stabile.

Answer 5

La funzione di richiamata di ordinamento di array viene richiamata più volte nel corso dell'ordinamento?

Poiché questo è un confronto sorta, dato N elementi, la funzione di callback, occorre fare ricorso a tempi medi (N * lg n) per una sorta veloce come Quicksort. Se l'algoritmo utilizzato è qualcosa come Bubble Sort, la funzione di callback sarà invocata in media (N * N) volte.

Il numero minimo di invocazioni per un ordinamento di confronto è (N-1) e serve solo a rilevare una lista già ordinata (ad esempio, all'inizio di Bubble Sort se non si verificano swap).