Introduzione agli algoritmi di ordinamento rapido in Java
L'ordinamento rapido in Java noto anche come ordinamento di scambio di partizioni è un algoritmo di ordinamento di divisione e conquista. L'ordinamento rapido è un buon esempio di algoritmo che sfrutta al meglio le cache della CPU, a causa della sua divisione e conquista della natura. L'algoritmo Quicksort è uno degli algoritmi di ordinamento più utilizzati, in particolare per ordinare gli elenchi di grandi dimensioni e la maggior parte dei linguaggi di programmazione lo hanno implementato. Nell'algoritmo Quicksort, i dati originali sono divisi in due parti che vengono ordinate individualmente e quindi unite per produrre dati ordinati.
Consideriamo che l'array (8, 6, 3, 4, 9, 2, 1, 7) deve essere ordinato utilizzando Ordinamento rapido.
I passaggi per implementare algoritmi di ordinamento rapido
1. Scegliere un elemento chiamato pivot dall'array. Generalmente, l'elemento centrale viene scelto come perno. Prendiamo 4 come perno.
2. Riorganizzare l'array in due parti in modo tale che elementi meno del perno vengano prima del perno e elementi più grandi del perno compaiano dopo il perno. Sono seguiti i seguenti passi:
- Scegli l'elemento più a sinistra, ovvero 8, Poiché 4 è il perno e 8 è più di 4, 8 deve essere spostato a destra di 4, Sul lato destro lasciamo 7 poiché è maggiore di 4 e scegli 1 per lo scambio con 8 quindi dopo lo scambio l'array diventa: 1, 6, 3, 4, 9, 2, 8, 7
- Scegli il successivo elemento sinistro, ovvero 6, poiché 4 è il perno e 6 è più di 4, 6 deve essere spostato a destra di 4, sul lato destro lasciamo 7, 8 poiché sono maggiori di 4 e scegli 2 per lo scambio con 6 quindi dopo lo scambio l'array diventa: 1, 2, 3, 4, 9, 6, 8, 7
- Ora poiché tutti gli elementi a sinistra del pivot sono inferiori al pivot e tutti gli elementi a destra del pivot sono maggiori del pivot, abbiamo finito con 4 come pivot.
3. Applicare in modo ricorsivo i passaggi 1 e 2 per l'array secondario sinistro (array con elementi inferiori al pivot) e per l'array secondario destro (array con elementi più del pivot). Se l'array contiene solo uno o zero elementi, l'array viene considerato assortito.
Programma per implementare algoritmi di ordinamento rapido
Ecco un programma Java per ordinare un array di numeri interi usando un algoritmo di ordinamento rapido.
Codice:
import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)
Produzione:
Vantaggi degli algoritmi di ordinamento rapido
Di seguito sono riportati i vantaggi dell'algoritmo di ordinamento rapido:
- Ottima località di riferimento: la località di riferimento è la capacità di un processore di accedere ripetutamente alla stessa posizione di memoria per un breve periodo di tempo. L'ordinamento rapido in Java offre un'eccellente località di riferimento a causa del numero molto ridotto di cache cache, che sulle architetture moderne è fondamentale per le prestazioni.
- L'ordinamento rapido è parallelo: una volta completato il passaggio iniziale di partizionamento di un array in regioni più piccole, tutti i singoli sottoparagrafi possono essere ordinati indipendentemente in parallelo. Per questo motivo, l'ordinamento rapido ha prestazioni migliori.
Analisi di complessità dell'ordinamento rapido
Quicksort è un algoritmo veloce e ricorsivo di coda che funziona secondo il principio di divisione e conquista. Ecco la sua analisi della complessità nel caso migliore, medio e peggiore:
- Migliore complessità del caso: se un array o un elenco contiene n elementi, la prima esecuzione avrà bisogno di O (n). Ora l'ordinamento dei due subarrays rimanenti richiede 2 * O (n / 2). Questo conclude la complessità di O (n logn) nel migliore dei casi.
- Complessità media dei casi : il caso medio di quicksort è O (n log n).
- Peggior complessità del caso: la scelta del primo o dell'ultimo causerebbe prestazioni nel caso peggiore per dati quasi ordinati o quasi inversi. L'ordinamento rapido esegue O (n 2) nel caso peggiore.
In Java, array. Il metodo Sort () utilizza un algoritmo di ordinamento rapido per ordinare un array.
Articoli consigliati
Questa è una guida agli algoritmi di ordinamento rapido in Java. Qui discutiamo i passaggi per implementare, i vantaggi e l'analisi della complessità di un algoritmo di ordinamento rapido in Java insieme al programma. Puoi anche consultare i seguenti articoli per saperne di più -
- Inserimento ordinamento in Java
- ciclo do-while in Java
- JComponent in Java
- Quadrati in Java
- Scambiare in PHP
- Ordinamento in C #
- Ordinamento in Python
- Algoritmo C ++ | Esempi di algoritmo C ++