Algoritmo QuickSort in JavaScript con esempio

Cos'è l'ordinamento rapido?

Ordinamento rapido è un algoritmo di ordinamento comparativo che segue il Dividere e conquistare Questo approccio seleziona un elemento come pivot, divide l'array in una parte che contiene valori inferiori al pivot e una parte che contiene valori superiori, e poi applica la stessa procedura a ciascuna parte finché l'intero array non è ordinato.

Quick Sort è uno degli algoritmi di ordinamento più utilizzati in ogni linguaggio di programmazione. Se scrivi JavaCopione, probabilmente hai già utilizzato quello integrato ordinare() metodo, quindi potresti chiederti perché vale la pena imparare un'implementazione separata di Quick Sort. Per rispondere a questa domanda, devi prima sapere cosa significa ordinamento e qual è l'ordinamento predefinito in JavaLo script lo fa davvero.

Quick Sort si definisce in tre proprietà:

• Al suo posto: riorganizza l'originale schieramento e non alloca un secondo array delle stesse dimensioni.
• Ricorsivo: ciascuna partizione produce due intervalli più piccoli che vengono ordinati dalla stessa funzione.
• Instabile: due elementi con chiavi uguali possono finire in un ordine relativo diverso da quello iniziale.

Cos'è l'ordinamento?

Ordinare significa disporre gli elementi in un ordine definito. Hai quasi certamente incontrato questo concetto a scuola: mettere i numeri dal più piccolo al più grande è ascendente ordine, e metterli dal più grande al più piccolo è discendente ordinamento. L'ordinamento non è limitato ai numeri. Le stringhe possono essere ordinate alfabeticamente, le date cronologicamente e gli oggetti in base a qualsiasi campo tu scelga, come prezzo o punteggio.

L'ordinamento è importante perché i dati ordinati consentono operazioni più veloci. Una ricerca binaria viene eseguita in tempo O(log n), ma solo su input ordinati. La deduplicazione, le query di intervallo, il ranking e le operazioni di unione diventano tutte molto più economiche una volta che i dati sono ordinati, ed è per questo che ogni linguaggio di programmazione include almeno una routine di ordinamento.

Ordinamento predefinito in JavaCopione

Come menzionato prima, JavaLo script fornisce ordinare(). Prendi un piccolo array come [5,3,7,6,2,9] che vuoi in ordine crescente. Chiamando ordinare() sull'array sembra fare esattamente questo.

Lo screenshot qui sopra mostra la console del browser che stampa l'array ordinato. Ecco lo stesso codice:

var items = [5, 3, 7, 6, 2, 9];
console.log(items.sort());

Produzione:

[ 2, 3, 5, 6, 7, 9 ]

Quel risultato è corretto, ma solo per caso. Array.prototype.sort() converte ogni elemento in una stringa e confronta le stringhe a meno che non si fornisca una funzione di confronto. Ogni valore in questo array è una singola cifra, quindi l'ordine delle stringhe corrisponde all'ordine numerico. Modificando i dati, l'illusione si spezza.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

Produzione:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

Quale algoritmo utilizza la funzione sort()?

Le specifiche non indicano un algoritmo, quindi ogni motore sceglie il proprio. I motori moderni utilizzano tutti un algoritmo basato sulla fusione:

• V8 (Chrome, Edge, Node.js) ha utilizzato TimSort Disponibile dalla versione 8 7.0, inclusa in Chrome 70.
• Ragno scimmia (Firefox) utilizza unisci ordinamento.
• JavaScriptCore (Il safari) utilizza anche unisci ordinamento.

Dal 2019 ES il linguaggio garantisce che sort() is stabile, il che esclude un semplice Quick Sort all'interno del motore. L'ordinamento basato sulla fusione richiede O(n) memoria ausiliaria e deve chiamare il tuo JavaScript comparatore per ogni singolo confronto. Un Quick Sort numerico scritto a mano confronta i numeri direttamente e li ordina sul posto, quindi può vincere su array numerici di grandi dimensioni. Ordinare 1,000,000 di numeri interi casuali su Node.js 22 ha richiesto circa ms 100 con l'ordinamento rapido qui sotto e approssimativamente ms 210 con sort((a, b) => a - b).

Quick Sort è quindi un progetto che vale la pena scrivere quando si ha bisogno di ordinamento in loco, di un controllo preciso sulla memoria o semplicemente di una solida comprensione del funzionamento degli algoritmi di ordinamento. Analizziamone i meccanismi nel dettaglio.

Come funziona l'ordinamento rapido?

Quick Sort ripete un'operazione fondamentale, chiamata partizionamento, su intervalli sempre più ristretti. Ecco i passaggi in ordine:

1. Trovare il perno elemento nell'array.
2. Posizionare il puntatore sinistro sul primo elemento dell'intervallo.
3. Posizionare il puntatore destro sull'ultimo elemento dell'intervallo.
4. Confronta l'elemento indicato dal puntatore sinistro con il pivot. Se è minore del pivot, sposta il puntatore sinistro di un passo a destra. Continua finché l'elemento a sinistra non è maggiore o uguale al pivot.
5. Confronta l'elemento indicato dal puntatore destro con il pivot. Se è maggiore del pivot, sposta il puntatore destro di un passo a sinistra. Continua finché l'elemento a destra non è minore o uguale al pivot.
6. Se il puntatore sinistro è ancora minore o uguale al puntatore destro, scambia i due elementi.
7. Incrementa il puntatore sinistro e diminuisce il puntatore destro.
8. Se l'indice sinistro è ancora minore o uguale all'indice destro, ripetere dal passaggio 4. Altrimenti, restituire l'indice del puntatore sinistro.

Il diagramma sopra tracQuesti sono i movimenti del puntatore su un array di esempio. Ogni elemento più piccolo del pivot finisce alla sua sinistra e ogni elemento più grande finisce alla sua destra, che è esattamente ciò che indica l'indice restituito. La sezione seguente illustra lo stesso array passo dopo passo.

Come determinare l'elemento pivot

La scelta del pivot è l'unica decisione che distingue un Quick Sort veloce da uno lento. Se prendi sempre il prima di tutto elemento, un array già ordinato produce la peggiore divisione possibile: un lato vuoto e un lato con ogni elemento rimanente. Ciò trasforma l'algoritmo in O(n²). Prendendo il mezzo L'elemento (la lunghezza dell'array divisa per due) evita questa trappola per gli input ordinati e invertiti, ed è per questo che il codice seguente lo utilizza.

Strategie di pivot comuni:

• Primo o ultimo elemento: È il più semplice da programmare, ma ha una complessità O(n²) sui dati ordinati.
• Elemento intermedio: Un buon valore predefinito che gestisce array ordinati e invertiti in O(n log n).
• Elemento casuale: rende impossibile prevedere in anticipo l'input peggiore.
• Mediana di tre: calcola la mediana del primo, del secondo e dell'ultimo valore; è la scelta standard nelle librerie di produzione.

Ora esaminiamo l'algoritmo Quick Sort sull'array. [5,3,7,6,2,9].

STEP 1: Il perno è l'elemento centrale. Con sinistra = 0 e destra = 5, Math.floor((5 + 0) / 2) dà indice 2, quindi il valore pivot è 7.

STEP 2: Avvia i puntatori alle estremità dell'array. Il puntatore sinistro si trova all'indice 0 (valore 5) e il puntatore destro si trova all'indice 5 (valore 9).

STEP 3: Confronta il valore a sinistra con il pivot. 5 < 7, quindi spostati a destra all'indice 1. 3 < 7, quindi spostati a destra all'indice 2. Il valore lì è 7, che non è minore del pivot, quindi il puntatore sinistro si ferma all'indice 2.

STEP 4: Confronta il valore a destra con il pivot. 9 > 7, quindi spostati a sinistra all'indice 4. Il valore lì è 2, che non è maggiore del pivot, quindi il puntatore a destra si ferma all'indice 4.

STEP 5: L'indice sinistro (2) è minore o uguale all'indice destro (4), quindi scambiamo i due valori. L'array diventa [5,3,2,6,7,9].

STEP 6: Sposta entrambi i puntatori di un passo verso l'interno. Il puntatore sinistro si trova ora all'indice 3 e il puntatore destro all'indice 3.

STEP 7: Ripeti la scansione. Il valore all'indice 3 è 6, e 6 < 7, quindi il puntatore sinistro avanza all'indice 4. Il valore all'indice 3 non è maggiore del pivot, quindi il puntatore destro rimane all'indice 3.

STEP 8: L'indice sinistro (4) è ora maggiore dell'indice destro (3), quindi il ciclo termina e la funzione restituisce 4Tutto ciò che precede l'indice 4 è minore o uguale al pivot, e tutto ciò che segue l'indice 4 è maggiore o uguale ad esso.

In base a questa procedura, è necessario il codice per due operazioni: scambioping due elementi e partizionamento di un intervallo.

Code per scambiare due Numbers in JavaCopione

Come mostra lo screenshot dell'editor qui sopra, la funzione di supporto per lo scambio utilizza una variabile temporanea per scambiare i valori a due indici. Modifica direttamente l'array e non restituisce nulla.

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

Produzione:

[ 9, 3, 7, 6, 2, 5 ]

Code per eseguire la partizione

Il codice nello screenshot qui sopra trasforma i passaggi da 1 a 8 in una funzione. I due interni loops avanzano i puntatori, il if Il blocco esegue lo scambio e la funzione restituisce l'indice di divisione.

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swap two elements
            i++;
            j--;
        }
    }
    return i;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

Produzione:

[ 5, 3, 2, 6, 7, 9 ]
4

L'output corrisponde esattamente alla procedura manuale: dopo un passaggio di partizionamento l'array è [5,3,2,6,7,9] e l'indice di suddivisione restituito è 4.

Eseguire il ricorsivo Operaproduzione

Una volta che il partizionamento restituisce l'indice di divisione, lo si utilizza per dividere l'intervallo ed eseguire l'ordinamento rapido (Quick Sort) su ciascuna metà. Per questo motivo viene chiamato algoritmo "Divide et Impera". La ricorsione continua finché ogni sottointervallo non contiene un singolo elemento, a quel punto l'intero array è ordinato.

Nota: Quick Sort opera sullo stesso array per tutta la durata dell'operazione. Non vengono creati nuovi array durante il processo, il che lo rende un algoritmo in-place.

Quindi chiami il partizione() funzione spiegata sopra e utilizzare il suo valore di ritorno per dividere il schieramento in parti. Ecco il codice che lo fa:

Si notino le due condizioni di guardia evidenziate nello screenshot. left < index - 1 conferma che almeno due elementi rimangono sul lato sinistro e index < right conferma lo stesso per il lato destro. Senza queste protezioni, la funzione richiamerebbe se stessa all'infinito su intervalli a singolo elemento.

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

Produzione:

[ 2, 3, 5, 6, 7, 9 ]

Ordinamento rapido completo Code

Mettendo insieme le parti relative a scambio, partizionamento e ricorsione si ottiene l'implementazione completa:

var items = [5, 3, 7, 6, 2, 9];

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swapping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray);

Produzione:

[ 2, 3, 5, 6, 7, 9 ]

Lo screenshot qui sopra mostra il programma completo nell'editor insieme all'array ordinato nella console. Questa implementazione è stata verificata con un array già ordinato, un array ordinato in ordine inverso, array contenenti valori duplicati e identici, numeri negativi, un singolo elemento e un array vuoto, e restituisce il risultato corretto in ogni caso.

Complessità temporale e spaziale dell'ordinamento rapido

Ogni passaggio di partizionamento tocca ogni elemento dell'intervallo una sola volta, quindi un singolo passaggio ha un costo O(n). Il costo totale dipende quindi da quante volte l'array può essere suddiviso prima che gli intervalli diventino banali.

La complessità spaziale è O(log n) Per questa versione in loco, non viene allocato un secondo array, quindi l'unica memoria aggiuntiva è lo stack di ricorsione, e la suddivisione bilanciata mantiene tale stack profondo circa log₂(n) frame. Nel caso peggiore degenere, lo stack cresce fino a O(n) frame, motivo per cui array molto grandi possono causare un overflow dello stack di chiamate.

Due numeri concretizzano questo risultato. L'ordinamento di 4,096 valori casuali con il codice sopra riportato ha richiesto circa 65,000 confronti, contro un valore teorico di n·log₂(n) pari a 49,152, e la ricorsione più profonda ha raggiunto 24 frame, mentre log₂(4096) è pari a 12. Entrambi i valori rientrano nel piccolo fattore costante previsto per un algoritmo O(n log n).

Ordinamento rapido vs altri metodi di ordinamento Algorithms

L'ordinamento rapido (Quick Sort) raramente è l'unica opzione. La tabella seguente lo confronta con gli altri algoritmi che più probabilmente incontrerai, in modo da poter scegliere quello più adatto ai tuoi dati.

In pratica, Quick Sort di solito risulta vincente perché il suo ciclo interno è compatto e funziona su intervalli contigui ottimizzati per la cache. Scegliete Merge Sort quando avete bisogno di un ordinamento stabile o con complessità O(n log n), Heap Sort quando la memoria è estremamente limitata e Insertion Sort per array molto piccoli o quasi ordinati. Le librerie di produzione spesso li combinano: introsort inizia con Quick Sort, passa a Heap Sort se la ricorsione diventa troppo profonda e termina con Insertion Sort su intervalli di piccole dimensioni.

Come ordinare rapidamente oggetti e stringhe

L'implementazione mostrata finora confronta i valori con < and >, che lo limita ai numeri. Le applicazioni reali hanno bisogno di ordinare oggetti per una proprietà, stringhe in ordine alfabetico o date in ordine cronologico. La soluzione è spostare il confronto in una callback, esattamente come quella integrata sort() fa.

Un comparatore riceve due valori e restituisce un numero negativo quando il primo dovrebbe venire prima, un numero positivo quando il secondo dovrebbe venire prima e zero quando i due sono equivalenti. Sostituendo i due confronti codificati direttamente nel codice con chiamate al comparatore, l'algoritmo funziona con qualsiasi tipo di dato.

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

Produzione:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Tre dettagli meritano di essere notati. La guardia di ricorsione è ora left >= right, che è corretto per qualsiasi intervallo e non dipende dalla lunghezza dell'array esterno. Il confronto tra stringhe utilizza localeCompare() In questo modo i caratteri accentati e la distinzione tra maiuscole e minuscole vengono gestiti correttamente, anziché tramite punti di codice grezzi. Inoltre, poiché l'ordinamento rapido non è stabile, i record che condividono lo stesso stipendio potrebbero scambiarsi di posto; se l'ordine originale è importante, ordina utilizzando una seconda chiave di spareggio.

Pronto a continuare? Rafforza le basi con il JavaIntroduzione alla sceneggiatura, esercitarsi con la meccanica del puntatore in JavaCicli di script, lavorare attraverso di più pratico JavaEsempi di codice script, confrontare le implementazioni in Ordinamento di inserzione and Ordinamento heap, oppure aggiungi tipi statici a questo algoritmo con il TypeScript riferimento.

DOMANDE FREQUENTI