Algoritmo QuickSort in JavaScript

Cos'è l'ordinamento rapido?

L' algoritmo di ordinamento rapido segue l'approccio Divide and Conquer. Divide gli elementi in parti più piccole in base ad alcune condizioni ed esegue le operazioni di ordinamento su quelle parti più piccole divise.

L'algoritmo di ordinamento rapido è uno degli algoritmi più utilizzati e popolari in qualsiasi linguaggio di programmazione. Ma, se sei uno sviluppatore JavaScript, potresti aver sentito parlare di sort () che è già disponibile in JavaScript. Quindi, potresti aver pensato quale sia la necessità di questo algoritmo di ordinamento rapido. Per capirlo, prima abbiamo bisogno di cosa sta ordinando e qual è l'ordinamento predefinito in JavaScript.

Cos'è l'ordinamento?

L'ordinamento non è altro che disporre gli elementi nell'ordine che vogliamo. Potresti averlo riscontrato ai tempi della scuola o del college. Come disporre i numeri dal più piccolo al più grande (ascendente) o dal maggiore al più piccolo (discendente) è ciò che abbiamo visto fino ad ora ed è chiamato ordinamento.

Ordinamento predefinito in JavaScript

Come accennato in precedenza, JavaScript ha sort () . Facciamo un esempio con pochi array di elementi come [5,3,7,6,2,9] e vogliamo ordinare gli elementi di questo array in ordine crescente. Basta chiamare sort () sull'array di elementi e ordina gli elementi dell'array in ordine crescente.

Codice:

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

Qual è il motivo per scegliere l'ordinamento rapido rispetto all'ordinamento predefinito () in JavaScript

Sebbene sort () dia il risultato che vogliamo, il problema risiede nel modo in cui ordina gli elementi dell'array. L'ordinamento predefinito () in JavaScript utilizza l'ordinamento per inserzione del motore V8 di Chrome e l' ordinamento Merge di Mozilla Firefox e Safari .

Tuttavia, questo non è adatto se è necessario ordinare un numero elevato di elementi. Quindi, la soluzione è utilizzare l'ordinamento rapido per set di dati di grandi dimensioni.

Quindi, per capire completamente, è necessario sapere come funziona l'ordinamento rapido e vediamolo in dettaglio ora.

Cos'è l'ordinamento rapido?

L'ordinamento rapido segue l' algoritmo di Divide and Conquer . Divide gli elementi in parti più piccole in base a qualche condizione ed esegue le operazioni di ordinamento su quelle parti più piccole divise. Quindi, funziona bene per set di dati di grandi dimensioni. Quindi, ecco i passaggi su come funziona l'ordinamento rapido in parole semplici.

Per prima cosa seleziona un elemento che deve essere chiamato come elemento pivot .
Quindi, confronta tutti gli elementi dell'array con l'elemento pivot selezionato e disponili in modo tale che gli elementi minori dell'elemento pivot siano a sinistra e maggiori di pivot siano a destra.
Infine, esegui le stesse operazioni sugli elementi del lato sinistro e destro dell'elemento pivot.

Quindi, questa è la struttura di base dell'ordinamento rapido. Ecco i passaggi che devono essere seguiti uno per uno per eseguire l'ordinamento rapido.

Come funziona QuickSort

Per prima cosa trova l' elemento "pivot" nell'array.
Avvia il puntatore sinistro sul primo elemento dell'array.
Avvia il puntatore destro sull'ultimo elemento dell'array.
Confronta l'elemento che punta con il puntatore sinistro e se è minore dell'elemento pivot, sposta il puntatore sinistro a destra (aggiungi 1 all'indice sinistro). Continuare fino a quando l'elemento del lato sinistro è maggiore o uguale all'elemento perno.
Confronta l'elemento che punta con il puntatore destro e se è maggiore dell'elemento pivot, sposta il puntatore destro a sinistra (sottrai 1 all'indice destro). Continuare fino a quando l'elemento del lato destro è minore o uguale all'elemento perno.
Verificare se il puntatore sinistro è minore o uguale al puntatore destro, quindi ha visto gli elementi nelle posizioni di questi puntatori.
Incrementa il puntatore sinistro e decrementa il puntatore destro.
Se l'indice del puntatore sinistro è ancora inferiore all'indice del puntatore destro, ripetere il processo; altrimenti restituisce l'indice del puntatore sinistro.

Quindi, vediamo questi passaggi con un esempio. Consideriamo l'array di elementi che dobbiamo ordinare è [5,3,7,6,2,9].

Determina l'elemento Pivot

Ma prima di procedere con l'ordinamento rapido, la selezione dell'elemento pivot gioca un ruolo importante. Se selezioni il primo elemento come elemento pivot, le prestazioni peggiori nell'array ordinato. Quindi, è sempre consigliabile scegliere l'elemento centrale (lunghezza dell'array divisa per 2) come elemento pivot e noi facciamo lo stesso.

Di seguito sono riportati i passaggi per eseguire l'ordinamento rapido mostrato con un esempio [5,3,7,6,2,9].

FASE 1: Determina il perno come elemento centrale. Quindi, 7 è l'elemento pivot.

PASSAGGIO 2: avviare i puntatori sinistro e destro rispettivamente come primo e ultimo elemento della matrice. Quindi, il puntatore sinistro punta a 5 all'indice 0 e il puntatore destro punta a 9 all'indice 5.

PASSO 3: confronta l'elemento nel puntatore sinistro con l'elemento pivot. Da allora, 5 <6 sposta il puntatore sinistro a destra sull'indice 1.

FASE 4: Ora, ancora 3 <6 quindi sposta il puntatore sinistro su un altro indice a destra. Quindi ora 7> 6 smetti di incrementare il puntatore sinistro e ora il puntatore sinistro è all'indice 2.

PASSO 5: Ora, confronta il valore nel puntatore destro con l'elemento pivot. Dato che 9> 6 sposta il puntatore destro a sinistra. Ora come 2 <6 smetti di muovere il puntatore destro.

PASSO 6: scambia entrambi i valori presenti ai puntatori sinistro e destro l'uno con l'altro.

PASSAGGIO 7: spostare entrambi i puntatori di un ulteriore passaggio.

PASSO 8: Poiché 6 = 6, sposta i puntatori su un altro passo e fermati quando il puntatore sinistro incrocia il puntatore destro e restituisce l'indice del puntatore sinistro.

Quindi, qui in base all'approccio sopra, abbiamo bisogno di scrivere codice per lo scambio di elementi e il partizionamento dell'array come menzionato nei passaggi precedenti.

Codice per scambiare due numeri in JavaScript:

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

Codice per eseguire la partizione come indicato nei passaggi precedenti:

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

Eseguire l'operazione ricorsiva

Una volta eseguiti i passaggi precedenti, verrà restituito l'indice del puntatore sinistro e sarà necessario utilizzarlo per dividere l'array ed eseguire l'ordinamento rapido su quella parte. Quindi, si chiama algoritmo Divide and Conquer.

Quindi, l'ordinamento rapido viene eseguito fino a quando tutti gli elementi sulla matrice di sinistra e sulla matrice di destra non vengono ordinati.

Nota: l' ordinamento rapido viene eseguito sullo stesso array e nel processo non vengono creati nuovi array.

Quindi, dobbiamo chiamare questa partition () spiegata sopra e in base a essa dividere l'array in parti. Quindi ecco il codice dove lo usi,

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Codice di ordinamento rapido completo:

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 elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]