Implementazione dell'algoritmo Quicksort in Java

1. Panoramica

In questo tutorial, esploreremo in dettaglio l'algoritmo QuickSort, concentrandoci sulla sua implementazione Java.

Discuteremo anche dei suoi vantaggi e svantaggi e poi analizzeremo la sua complessità temporale.

2. Algoritmo QuickSort

Quicksort è un algoritmo di ordinamento, che sfrutta il principio divide et impera. Ha una complessità media O (n log n) ed è uno degli algoritmi di ordinamento più utilizzati, soprattutto per i grandi volumi di dati.

È importante ricordare che Quicksort non è un algoritmo stabile. Un algoritmo di ordinamento stabile è un algoritmo in cui gli elementi con gli stessi valori appaiono nello stesso ordine nell'output ordinato come appaiono nell'elenco di input.

La lista di input è divisa in due sottoelenchi da un elemento chiamato pivot; un sottoelenco con elementi minori del pivot e un altro con elementi maggiori del pivot. Questo processo si ripete per ogni sottoelenco.

Infine, tutti i sottoelenchi ordinati si uniscono per formare l'output finale.

2.1. Passaggi dell'algoritmo

  1. Scegliamo un elemento dalla lista, chiamato pivot. Lo useremo per dividere l'elenco in due sottoelenchi.
  2. Riordiniamo tutti gli elementi attorno al perno: quelli con un valore inferiore vengono posizionati prima di esso e tutti gli elementi maggiori del perno dopo di esso. Dopo questo passaggio, il perno è nella sua posizione finale. Questo è il passaggio importante della partizione.
  3. Applichiamo i passaggi precedenti in modo ricorsivo a entrambi i sottoelenchi a sinistra ea destra del pivot.

Come possiamo vedere, il quicksort è naturalmente un algoritmo ricorsivo, come ogni approccio divide et impera.

Facciamo un semplice esempio per capire meglio questo algoritmo.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Supponiamo di scegliere 5 come perno per semplicità
  2. Per prima cosa metteremo tutti gli elementi inferiori a 5 nella prima posizione della matrice: {3, 4, 5, 6, 5, 9}
  3. Lo ripeteremo quindi per il sotto-array sinistro {3,4}, prendendo 3 come pivot
  4. Non ci sono elementi inferiori a 3
  5. Applichiamo il quicksort al sotto-array a destra del pivot, ovvero {4}
  6. Questo sotto-array è costituito da un solo elemento ordinato
  7. Continuiamo con la parte destra dell'array originale, {6, 5, 9} finché non otteniamo l'array ordinato finale

2.2. Scegliere il perno ottimale

Il punto cruciale in QuickSort è scegliere il miglior pivot. L'elemento centrale è, ovviamente, il migliore, poiché dividerebbe l'elenco in due sottoelenchi uguali.

Ma trovare l'elemento centrale da un elenco non ordinato è difficile e richiede tempo, ecco perché prendiamo come perno il primo elemento, l'ultimo elemento, la mediana o qualsiasi altro elemento casuale.

3. Implementazione in Java

Il primo metodo è quickSort () che prende come parametri l'array da ordinare, il primo e l'ultimo indice. Per prima cosa controlliamo gli indici e proseguiamo solo se ci sono ancora elementi da ordinare.

Otteniamo l'indice del pivot ordinato e lo usiamo per chiamare in modo ricorsivo il metodo partition () con gli stessi parametri del metodo quickSort () , ma con indici diversi:

public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }

Continuiamo con il metodo partition () . Per semplicità, questa funzione prende l'ultimo elemento come perno. Quindi, controlla ogni elemento e lo scambia prima del pivot se il suo valore è inferiore.

Alla fine del partizionamento, tutti gli elementi meno il perno si trovano a sinistra di esso e tutti gli elementi più grandi del perno si trovano a destra di esso. Il pivot si trova nella sua posizione ordinata finale e la funzione restituisce questa posizione:

private int partition(int arr[], int begin, int end) { int pivot = arr[end]; int i = (begin-1); for (int j = begin; j < end; j++) { if (arr[j] <= pivot) { i++; int swapTemp = arr[i]; arr[i] = arr[j]; arr[j] = swapTemp; } } int swapTemp = arr[i+1]; arr[i+1] = arr[end]; arr[end] = swapTemp; return i+1; }

4. Analisi degli algoritmi

4.1. Complessità temporale

Nel migliore dei casi, l'algoritmo dividerà l'elenco in due sottoelenchi di uguale dimensione. Quindi, la prima iterazione dell'intero elenco di n dimensioni richiede O (n) . Ordinare i restanti due elenchi secondari con n / 2 elementi richiede 2 * O (n / 2) ciascuno. Di conseguenza, l'algoritmo QuickSort ha la complessità di O (n log n) .

Nel peggiore dei casi, l'algoritmo selezionerà un solo elemento in ogni iterazione, quindi O (n) + O (n-1) +… + O (1) , che è uguale a O (n2) .

In media QuickSort ha una complessità O (n log n) , rendendolo adatto a volumi di big data.

4.2. QuickSort vs MergeSort

Discutiamo in quali casi dovremmo scegliere QuickSort su MergeSort.

Sebbene sia Quicksort che Mergesort abbiano una complessità temporale media di O (n log n) , Quicksort è l'algoritmo preferito, poiché ha una complessità di spazio O (log (n)) . Mergesort, d'altra parte, richiede O (n) memoria extra, il che lo rende piuttosto costoso per gli array.

Quicksort richiede di accedere a diversi indici per le sue operazioni, ma questo accesso non è direttamente possibile nelle liste concatenate, non essendoci blocchi continui; quindi per accedere a un elemento dobbiamo iterare su ogni nodo dall'inizio della lista collegata. Inoltre, Mergesort è implementato senza spazio aggiuntivo per LinkedLists.

In tal caso, è generalmente preferibile aumentare le spese generali per Quicksort e Mergesort.

5. conclusione

Quicksort è un elegante algoritmo di ordinamento che è molto utile nella maggior parte dei casi.

È generalmente un algoritmo "sul posto", con la complessità temporale media di O (n log n).

Un altro punto interessante da menzionare è che il metodo Arrays.sort () di Java utilizza Quicksort per ordinare gli array di primitive. L'implementazione utilizza due pivot e funziona molto meglio della nostra semplice soluzione, ecco perché per il codice di produzione è solitamente meglio usare metodi di libreria.

Come sempre, il codice per l'implementazione di questo algoritmo può essere trovato sul nostro repository GitHub.