Introduzione all'ordinamento rapido in Java

Il seguente articolo Ordinamento rapido in Java fornisce una struttura per l'algoritmo di ordinamento rapido in Java. L'algoritmo di ordinamento rapido è uno degli algoritmi di ordinamento che è efficiente e simile a quello dell'algoritmo di ordinamento di tipo merge. Questo è uno degli algoritmi utilizzati prevalentemente per scopi di ordinamento in tempo reale. La complessità temporale peggiore di questo algoritmo è O (n 2), la complessità temporale media è O (n log n) e la complessità temporale migliore è O (n log n).

La complessità dello spazio se O (n log n) dove è n è la dimensione dell'input. Il processo di ordinamento prevede la suddivisione degli input, iterazioni ricorsive e marcatura di un elemento cardine per ciascuna ricorsione. Il tipo di ordinamento in questo algoritmo comporta un confronto di elementi adiacenti in modo iterativo.

Come funziona l'ordinamento rapido in Java?

L'algoritmo di ordinamento rapido può essere implementato in Java formando uno pseudo codice con una sequenza di passaggi progettati e seguiti in modo efficiente.

  1. Il principio principale dell'algoritmo di ordinamento rapido che funziona si basa sull'approccio di divisione e conquista ed è anche un algoritmo di ordinamento efficiente.
  2. L'array di input è diviso in sotto-array e la divisione si basa sull'elemento pivot che è un elemento centrale. I sotto-array su entrambi i lati dell'elemento pivot sono le aree principali in cui si verifica effettivamente l'ordinamento.
  3. L'elemento pivot centrale è la base per dividere l'array in due partizioni in cui la metà sinistra degli elementi dell'array è inferiore all'elemento pivot e la metà destra degli elementi dell'array è maggiore dell'elemento pivot.
  4. Prima di considerare l'elemento pivot, può essere chiunque dagli elementi di un array. Questo è normalmente considerato come quello centrale o il primo o l'ultimo per la facilità di comprensione. L'elemento pivot può essere casuale da uno qualsiasi degli elementi dell'array.
  5. Nel nostro esempio, l'ultimo elemento di un array è considerato un elemento pivot, in cui il partizionamento dei sotto-array inizia dalla fine destra dell'array.
  6. Infine, l'elemento pivot sarà nella sua posizione ordinata effettiva dopo il completamento del processo di ordinamento in cui il processo principale di ordinamento si trova nella logica di partizione dell'algoritmo di ordinamento.
  7. L'efficienza dell'algoritmo dipende dalla dimensione dei sotto-array e da come sono bilanciati. Più gli array secondari sono sbilanciati, più la complessità del tempo porterà alla complessità del caso peggiore.
  8. La selezione di elementi pivot in modo casuale determina la migliore complessità temporale in molti casi invece di scegliere un particolare indice di inizio, fine o medio come elementi pivot.

Esempi per implementare l'ordinamento rapido in Java

L'algoritmo QuickSort è stato implementato usando il linguaggio di programmazione Java come di seguito e il codice di output è stato visualizzato sotto il codice.

  1. Inizialmente il codice accetta l'input usando il metodo quickSortAlgo () con l'array, l'indice iniziale e l'indice finale, cioè la lunghezza dell'array come argomenti.
  2. Dopo aver chiamato il metodo quickSortAlgo (), controlla se l'indice iniziale è inferiore all'indice finale e quindi chiama il metodo arrayPartition () per ottenere il valore dell'elemento pivot.
  3. L'elemento di partizione contiene la logica di disporre gli elementi più piccoli e più grandi attorno all'elemento pivot in base ai valori dell'elemento.
  4. Dopo aver ottenuto l'indice dell'elemento pivot dopo l'esecuzione del metodo di partizione, il metodo quickSortAlgo () viene chiamato da solo in modo ricorsivo fino a quando tutti gli array secondari non vengono partizionati e ordinati completamente.
  5. Nella logica della partizione, l'ultimo elemento viene assegnato come elemento pivot e il primo elemento viene confrontato con l'elemento pivot, ovvero l'ultimo in cui gli elementi vengono scambiati in base al fatto che siano più piccoli o più grandi.
  6. Questo processo di ricorsione si verifica fino a quando tutti gli elementi di un array non vengono partizionati e ordinati in cui il risultato finale è un array ordinato combinato.
  7. Gli elementi vengono scambiati all'interno dell'iterazione for-loop solo nel caso in cui l'elemento sia minore o uguale all'elemento pivot.
  8. Dopo aver completato il processo di iterazione, l'ultimo elemento viene scambiato, ovvero il valore dell'elemento pivot viene spostato sul lato sinistro in modo da creare le nuove partizioni e lo stesso processo si ripete sotto forma di ricorsione che si traduce in una serie di operazioni di ordinamento su diverse possibili partizioni come una formazione di sotto-matrici dai dati elementi dell'array.
  9. Il codice seguente può essere eseguito su qualsiasi IDE e l'output può essere verificato modificando il valore dell'array in main () Il metodo principale viene utilizzato solo allo scopo di ottenere l'output nella console. Come parte degli standard di codifica Java, il metodo principale può essere rimosso di seguito e un oggetto può essere creato e metodi di seguito possono essere chiamati rendendoli non statici.

Implementazione del codice di Quick Sort Algorithm in Java

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)

Produzione:

Conclusione

L'algoritmo di ordinamento rapido è efficiente ma non molto stabile rispetto ad altre tecniche di ordinamento. L'efficienza degli algoritmi di ordinamento rapido si riduce nel caso di un numero maggiore di elementi ripetuti, il che è un inconveniente. La complessità dello spazio è ottimizzata in questo algoritmo di ordinamento rapido.

Articoli consigliati

Questa è una guida all'ordinamento rapido in Java. Qui discutiamo di come funziona Quick Sort in Java insieme a un esempio e implementazione del codice. Puoi anche consultare i nostri altri articoli suggeriti per saperne di più -

  1. Ordinamento dell'heap in Java
  2. Che cos'è un albero binario in Java?
  3. Manipolazione dei bit in Java
  4. Panoramica di Merge Sort in JavaScript
  5. Panoramica dell'ordinamento rapido in JavaScript
  6. Ordinamento dell'heap in Python
  7. I 6 migliori algoritmi di ordinamento in JavaScript

Categoria:

Sviluppo software