Ordinamento rapido in javascript
Come funziona l'algoritmo di ordinamento veloce
L'algoritmo QuickSort raccoglie un elemento e lo considera un elemento di perno; Ora l'elemento pivot è riservato.
Successivamente, prenderemo i due puntatori "P" e "Q".
Il puntatore "P" si sposterà dal lato sinistro al lato destro e non si fermerà fino a quando non trova un maggiore o uguale all'elemento perno.
Il secondo puntatore "Q" si sposterà dal lato destro al lato sinistro e smetterà di cercare quando trova un elemento inferiore o uguale all'elemento perno.
Quindi, "P" ordinerà gli elementi più piccoli sul lato sinistro e "Q" ordinerà gli elementi maggiori sul lato destro.
Ora capiremo il funzionamento dell'algoritmo di ordinamento rapido con l'aiuto di un esempio:
Supponiamo di avere una serie di sei elementi e vogliamo ordinarlo in ordine crescente usando un algoritmo QuickSort:
Nel passaggio iniziale, selezioniamo "36" come elemento per pivot (elemento medio):
Nel passaggio successivo, selezioniamo i nostri puntatori, puntatore "P" per spostarsi da sinistra a destra e puntatore "Q" per spostarsi dal lato destro al lato sinistro:
Ora il valore del puntatore sinistro "P" verrà confrontato con il valore pivot, poiché "35" è inferiore a "36" sposta il puntatore "P" sull'elemento adiacente. D'altra parte, confronta il valore del puntatore giusto "Q" con il valore pivot, "39" è maggiore di "36", quindi il puntatore "Q" si sposta sull'elemento adiacente a sinistra:
Ora, il puntatore "P" punta a "33" e viene confrontato con pivot "36", il valore del puntatore "P" è inferiore al valore pivot, quindi il puntatore "P" verrà spostato sull'elemento adiacente. Mentre il valore del puntatore "Q" 32 "è inferiore al valore di perno" 36 ", quindi si fermerà qui:
Il valore del puntatore sinistro "37" è maggiore del valore del perno "36", quindi si fermerà anche qui. Ora, 'P' si ferma a '37' e 'Q' si ferma a '32'.
Ora controlleremo se il puntatore "P" attraversa il puntatore "Q" o no. In questo caso, finora "P" non attraversa il puntatore "Q", quindi scambieremo il valore del puntatore "P" con il valore del puntatore "Q":
Ora 'P' e 'Q' indicano rispettivamente '32' e '37', sposta i puntatori ancora una volta, ora p = q ('36 '= '6'):
Sposta i puntatori ancora una volta, mentre il puntatore "P" attraversa il puntatore "Q", quindi qui, si fermerà e restituirà l'indice del puntatore "P". Fino ad ora, l'elemento pivot è nella sua posizione giusta e tutti gli elementi maggiori dell'elemento pivot sono sul lato destro del perno e tutti gli elementi inferiori agli elementi per giri sono sul lato sinistro del perno. In questo modo, ordineremo l'intero elenco.
Ora implementeremo questo concetto in JavaScript. Innanzitutto, il codice per scambiare elementi:
funzione swap_elements (elementi, left_index, destro_index)var temp = elements [left_index];
elementi [left_index] = elements [destro_index];
Elements [destro_index] = temp;
Successivamente, il codice per dividere un elenco in sotto-listi:
funzione sub_lists (elementi, left_pointer, destro_pointer)var pivot = elements [matematica.pavimento ((destra_pointer + left_pointer) / 2)],
i = left_pointer,
j = destra_pointer;
mentre io <= j)
while (elements [i] pivot)
J--;
if (i 1)
index = sub_lists (elementi, left_pointer, destro_pointer);
if (left_pointer < index - 1)
Quick_sort (elementi, left_pointer, indice - 1);
if (indice < right_pointer)
Quick_sort (elementi, indice, destra_pointer);
elementi di ritorno;
Abbiamo creato una funzione che prende tre parametri all'interno della funzione. Dividiamo l'intero elenco in sotto-list e scopriamo il puntatore sinistro e il puntatore destro e scriviamo il codice per incrementare il puntatore sinistro se è inferiore all'elemento pivot e diminuiamo il puntatore giusto se è maggiore dell'elemento per pivot:
Ora scriveremo il codice per gestire il comportamento ricorsivo dell'ordinamento rapido. Poiché nel passaggio sopra viene restituito l'indice di Left_Pointer e lo utilizzeremo per dividere l'elenco in sotto-listi e per applicare QuickSort su quei sotto-listi:
funzione Quick_sort (elementi, left_pointer, destro_pointer)VAR INDICE;
Se (elementi.lunghezza> 1)
index = sub_lists (elementi, left_pointer, destro_pointer);
if (left_pointer < index - 1)
Quick_sort (elementi, left_pointer, indice - 1);
if (indice < right_pointer)
Quick_sort (elementi, indice, destra_pointer);
elementi di ritorno;
Lo snippet di codice completo andrà così:
VAR ELEMENTS = [35,33,37,36,32,39];funzione swap_elements (elementi, left_index, destro_index)
var temp = elements [left_index];
elementi [left_index] = elements [destro_index];
Elements [destro_index] = temp;
funzione sub_lists (elementi, left_pointer, destro_pointer)
var pivot = elements [matematica.pavimento ((destra_pointer + left_pointer) / 2)],
i = left_pointer,
j = destra_pointer;
mentre io <= j)
while (elements [i] pivot)
J--;
if (i 1)
index = sub_lists (elementi, left_pointer, destro_pointer);
if (left_pointer < index - 1)
Quick_sort (elementi, left_pointer, indice - 1);
if (indice < right_pointer)
Quick_sort (elementi, indice, destra_pointer);
elementi di ritorno;
var sorted_array = Quick_sort (elementi, 0, elementi.lunghezza - 1);
console.log ("L'elenco ordinato:", Sorted_array);
Abbiamo inizializzato l'array non desiderato all'inizio del programma e alla fine del programma abbiamo chiamato la funzione "Quick_sort ()" per ottenere l'array ordinato finale:
Infine, quando eseguiamo questo codice otteniamo l'output risultante come:
Conclusione:
QuickSort è un algoritmo di smistamento che funziona sulla divisione e conquista la filosofia e dividi il problema in sotto-problemi più piccoli. E continua questo processo fino a raggiungere l'obiettivo risultante. In questo articolo, discutiamo di come funziona QuickSort e implementiamo questo concetto in JavaScript per risolvere qualsiasi array nel modo più efficiente.