L'ordinamento rapido è uno dei migliori metodi di ordinamento di array.

Se si sta programmando e il proprio codice va oltre la scrittura di una calcolatrice, spesso si incontrerà o si dovrà confrontare con la necessità di ordinare una particolare serie di dati. Ci sono molti modi per ordinare. In questo articolo analizzeremo i principali di essi e ci concentreremo sull'ordinamento rapido.

Concetto di ordinamento rapido

Ordinamento rapido - Ordinamento rapido o qsort. Per nome diventa chiaro di cosa si tratta e perché. Ma se non è chiaro, allora questo è un algoritmo Ordinando rapidamente la matrice, l'algoritmo ha un'efficienza di O (n log n) in media. Cosa significa? Ciò significa che il tempo di funzionamento medio dell'algoritmo aumenta lungo la stessa traiettoria del grafico di questa funzione. Alcuni linguaggi popolari hanno librerie incorporate con questo algoritmo e questo già indica che è estremamente efficace. Questi sono linguaggi come Java, C ++, C #.

L'algoritmo

Il metodo di ordinamento rapido utilizza la ricorsione e la strategia "Dividi e conquista".

1. Nell'array, cerchiamo un certo elemento di supporto, per semplicità, è meglio prendere quello centrale, ma se vuoi lavorare sull'ottimizzazione, dovrai provare diverse opzioni.

2. A sinistra del supporto, si cerca un elemento più grande del riferimento, a destra, un elemento più piccolo del riferimento, quindi li si scambia. Fatelo fino a quando il massimo a destra è inferiore al minimo a sinistra. Quindi, tutti i piccoli elementi vengono lanciati all'inizio, grandi - fino alla fine.

3. Applicare ricorsivamente questo algoritmo alle parti sinistra e destra del nostro algoritmo separatamente, poi ancora e ancora, fino a raggiungere un elemento o un certo numero di elementi. Qual è questo numero di elementi? C'è un altro modo per ottimizzare questo algoritmo. Quando la parte ordinata diventa approssimativamente uguale a 8 o 16, può essere elaborata mediante il suo ordinamento ordinario, ad esempio, bubble sort. Quindi aumenteremo l'efficienza del nostro algoritmo, da allora non elabora piccoli array quanto velocemente vorremmo.

Pertanto, l'intero array verrà elaborato e ordinato. E ora studieremo visivamente questo algoritmo.

Efficienza di ordinamento rapido

Ordina rapidamente l'algoritmo di ordinamento più veloce? Sicuramente no. Ora ci sono sempre più ordinamenti, al momento l'ordinamento più veloce è Timsort, funziona estremamente velocemente per gli array che erano originariamente ordinati in modo diverso. Ma non dimenticare che il metodo di ordinamento rapido è uno dei più facili da scrivere, è molto importante, perché, di norma, un semplice progetto richiede solo una semplice ortografia e non un algoritmo enorme che tu stesso non puoi scrivere. Anche Timsort non è l'algoritmo più complicato, ma il titolo del più semplice non è esattamente quello che fa per lui.

Implementazione dell'algoritmo

Bene, siamo arrivati ​​al "delizioso". Ora diamo un'occhiata a come questo algoritmo è implementato. Come accennato in precedenza, non è troppo complicato da implementare, anzi, anche semplice. Ma analizziamo ancora completamente ogni azione del nostro codice, in modo da capire come funziona l'ordinamento rapido.

Il nostro metodo è chiamato quickSort. Esegue l'algoritmo principale, in cui trasferiamo l'array, il suo primo e ultimo elemento. Memorizziamo in variabili i e k il primo e l'ultimo elemento del segmento ordinato in modo da non modificare queste variabili, come abbiamo bisogno di loro. Quindi controlliamo la distanza tra il primo e l'ultimo controllato: è maggiore o uguale a uno? In caso contrario, siamo arrivati ​​al centro e abbiamo bisogno di uscire dallo smistamento di questo segmento, e se così fosse, continueremo a farlo.

Quindi prendiamo il primo elemento nel segmento che viene ordinato per l'elemento di supporto. Facciamo il prossimo ciclo fino a raggiungere il centro. In esso facciamo altri due cicli: il primo è per la parte sinistra, e il secondo è per la destra. Li eseguiamo finché ci sono elementi che si adattano alla condizione, o finché non raggiungiamo l'elemento di supporto. Quindi, se l'elemento minimo è ancora a destra e il massimo è a sinistra, scambialo. Al termine del ciclo, modificare il primo elemento e il riferimento, se il riferimento è più piccolo. Quindi ricorsivamente rendiamo il nostro algoritmo per la parte destra e sinistra dell'array, e così continuiamo fino a raggiungere un segmento di 1 elemento in lunghezza. Quindi torneranno tutti i nostri algoritmi ricorsivi e usciremo completamente dall'ordinamento. Inoltre nella parte inferiore c'è un metodo swap, un metodo abbastanza comune per l'ordinamento di una serie di sostituzioni. Per non scrivere più volte la sostituzione di elementi, scriviamo una volta e cambiamo gli elementi in questa matrice.

In conclusione, possiamo dire che in termini di rapporto qualità-complessità, l'ordinamento rapido è nella posizione di leadership tra tutti gli algoritmi, quindi è necessario prendere nota del metodo e utilizzarlo se necessario nei propri progetti.