Algoritmo QuickSort in JavaCopione

Cos'è l'ordinamento?

L'ordinamento non è altro che disporre gli elementi nell'ordine che vogliamo. Potresti esserti imbattuto in questo ai tempi della scuola o dell'università. Come ordinare i numeri dal più piccolo al più grande (ascendente) o dal più grande al più piccolo (discendente) è quello che abbiamo visto finora e si chiama ordinamento.

Ordinamento predefinito JavaCopione

Come menzionato prima, JavaLa sceneggiatura ha ordinare(). Prendiamo 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. Chiama soltanto ordinare() 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 JavaCopione

Sebbene sort() dia il risultato desiderato, il problema risiede nel modo in cui ordina gli elementi dell'array. Sort() predefinito in JavaUsi dello script ordinamento per inserzione by Motore V8 di Chrome and Unisci ordinamento by Mozilla Firefox and Safari.

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

Quindi, per capirlo completamente, devi sapere come funziona l'ordinamento rapido e vediamolo in dettaglio ora.

Cos'è l'ordinamento rapido?

Segue l'ordinamento rapido Dividere e conquistare algoritmo. Divide gli elementi in parti più piccole in base a determinate condizioni 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.

1. Selezionare innanzitutto un elemento da chiamare come perno elemento.
2. Successivamente, confronta tutti gli elementi dell'array con l'elemento pivot selezionato e disponili in modo tale che gli elementi inferiori all'elemento pivot siano alla sua sinistra e maggiori dell'elemento pivot siano alla sua destra.
3. Infine, esegui le stesse operazioni sugli elementi laterali sinistro e destro dell'elemento pivot.

Quindi, questo è lo schema di base dell'ordinamento rapido. Ecco i passaggi che devono essere seguiti uno per uno per eseguire l'ordinamento rapido.

Come funziona QuickSort

1. Prima trova il "perno" elemento nell'array.
2. Avvia il puntatore sinistro sul primo elemento dell'array.
3. Inizia il puntatore destro sull'ultimo elemento dell'array.
4. Confronta l'elemento che punta con il puntatore sinistro e se è inferiore all'elemento pivot, sposta il puntatore sinistro verso destra (aggiungi 1 all'indice sinistro). Continua finché l'elemento del lato sinistro non è maggiore o uguale all'elemento pivot.
5. Confronta l'elemento che punta con il puntatore destro e se è maggiore dell'elemento pivot, sposta il puntatore destro verso sinistra (sottrai 1 all'indice destro). Continua finché l'elemento del lato destro non è inferiore o uguale all'elemento perno.
6. Controlla se il puntatore sinistro è inferiore o uguale al puntatore destro, quindi scambia gli elementi nelle posizioni di questi puntatori.
7. Incrementa il puntatore sinistro e diminuisce il puntatore destro.
8. Se l'indice del puntatore sinistro è ancora inferiore all'indice del puntatore destro, ripetere il processo; altrimenti restituisce l'indice del puntatore sinistro.

Vediamo quindi questi passaggi con un esempio. Consideriamo la serie di elementi che dobbiamo ordinare è [5,3,7,6,2,9].

Determinare 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, darà 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.

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

STEP 1: Determina il perno come elemento centrale. COSÌ, 7 è l'elemento perno.

STEP 2: Inizia i puntatori sinistro e destro rispettivamente come primo e ultimo elemento dell'array. Quindi, il puntatore sinistro punta a 5 all'indice 0 e il puntatore destro punta 9 all'indice 5.

STEP 3: Confronta l'elemento sul puntatore sinistro con l'elemento pivot. Poiché, 5 < 6 sposta il puntatore sinistro a destra sull'indice 1.

STEP 4: Ora, ancora 3 <6, quindi sposta il puntatore sinistro su un altro indice a destra. Quindi ora 7 > 6 smette di incrementare il puntatore sinistro e ora il puntatore sinistro si trova sull'indice 2.

STEP 5: Ora confronta il valore sul puntatore destro con l'elemento pivot. Da 9 > 6 sposta il puntatore destro verso sinistra. Ora, poiché 2 < 6, smetti di spostare il puntatore destro.

STEP 6: Scambia tra loro entrambi i valori presenti sui puntatori sinistro e destro.

STEP 7: Sposta entrambi i puntatori di un altro passo.

STEP 8: Poiché 6 = 6, sposta i puntatori di un ulteriore passo e si ferma quando il puntatore sinistro incrocia il puntatore destro e restituisce l'indice del puntatore sinistro.

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

Codice per scambiare due numeri in JavaCopione

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

Codice per eseguire la partizione come menzionato nei passaggi precedenti

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;
}

Eseguire l'operazione ricorsiva

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

Pertanto, l'ordinamento rapido viene eseguito finché tutti gli elementi sull'array di sinistra e sull'array di destra non vengono ordinati.

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

Quindi dobbiamo chiamarlo così partizione() spiegato sopra e in base a ciò dividiamo il schieramento in parti. Quindi ecco il codice in cui lo usi,

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 result = quickSort(items, 0, items.length - 1);

Completa il codice di ordinamento rapido

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); //sawpping 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); //prints [2,3,5,6,7,9]

NOTA: L'ordinamento rapido viene eseguito con la complessità temporale di O(nlogn).