Java Algoritmi Di Ordinamento: Quick Sort



Bentornati in questa nostra panoramica sul mondo Java! Oggi andremo a parlare di un algoritmo di ordinamento tra i più celebri. Il Quick Sort.

A differenza del precedentemente trattato Bubble Sort, Quick Sort non si presta particolarmente a fini didattici siccome la sua implementazione potrebbe non risultare banale, ma a livello prestazionale offre vantaggi non indifferenti.

Cerchiamo di capire meglio di cosa si tratta.

Prima di tutto, vediamo un'illustrazione che ci da un'idea sommaria di cosa fa l'algoritmo.

QuickSortScheme

Caratteristiche fondamentali e descrizione

Il Quick Sort è uno degli algoritmi di ordinamento più utilizzati, specialmente quando si ha a che fare con grandi quantità di dati. Come altri algoritmi, fa parte della famiglia Divide and Conquer (dividi e conquista).

Significa che il lavoro non viene svolto sull'intera collezione di dati, ma viene bensì svolto ricorsivamente su sottoinsiemi finiti della collezione. Questo permette di rendere più leggere le operazioni di ordinamento dal momento in cui i valori da confrontare sono al più due.

Ricordiamo che il Quick Sort è un algoritmo stabile e soprattutto in-place. Generalmente nessun algoritmo è stabile, ma può essere reso stabile usando gli indici come metro di paragone.

Vediamo quali sono i passi principali dell'algoritmo.

Se la collezione contiene zero elementi o un elemento, allora è ordinata. In caso contrario si eseguono i seguenti passi:

  1. Si sceglie un pivot;
  2. Gli elementi della collezione sono divisi in due parti: quelli prima del pivot e quelli dopo il pivot;
  3. Si ordinano gli elementi ripetendo ricorsivamente i passi 1 e 2;

Implementazione

import java.util.*;
public class QuickSort 
{ 
/* 
Questa funzione prende l'ultimo elemento come pivot,
    piazza l'elemento di pivot nella sua posizione corretta
    nell'array ordinato. Inoltre piazza tutti gli elementi 
    "più piccoli" del pivot a sinistra e tutti quelli 
    "più grandi" alla destra del pivot.
*/
private static int partition(int arr[], int low, int high) 
{ 
int pivot = arr[high]; 
int index = (low-1); // indice dell'elemento più piccolo. -1 all'inizio 
for (int j=low; j<high; j++) 
{ 
// se elemento corrente minore di pivot
if (arr[j] < pivot) 
{ 
index++; 
// scambia arr[index] and arr[j] 
int temp = arr[index]; 
arr[index] = arr[j]; 
arr[j] = temp; 
} 
} 
// scambia arr[index+1] e arr[high] (o pivot) 
int temp = arr[index+1]; 
arr[index+1] = arr[high]; 
arr[high] = temp; 
return index+1; 
} 
/* La funzione principale che implementa QuickSort() 
arr[] --> array da ordinare, 
low --> indice iniziale, 
high --> indice finale */
public static void sort(int arr[], int low, int high) 
{ 
if (low < high) 
{ 
/* pi è l'indice di partizionamento, arr[pi] è ora al 
               posto giusto */
int pi = partition(arr, low, high); 
// Ordina ricorsivamente gli elementi prima di 
// partition e dopo partition 
sort(arr, low, pi-1); 
sort(arr, pi+1, high); 
} 
} 
// Programma guida.
public static void main(String args[]) 
{ 
int arr[] = {10, 7, 8, 9, 1, 5}; 
int n = arr.length; 
QuickSort.sort(arr, 0, n-1); 
System.out.println("sorted array"); 
System.out.println(Arrays.toString(arr)); 
} 
} 

Capiamo il codice

L'elemento cardine è la scelta del pivot ("perno"). Il pivot ideale sarebbe l'elemento medio della collezione, che però è difficile trovare se non si ha un insieme di elementi ordinati. Per cui le scelte possono essere differenti. Si può scegliere come pivot sempre il primo elemento, l'ultimo elemento, l'elemento in posizione centrale o un elemento random.

Il metodo principale è il metodo partition che prende come parametri la collezione da ordinare, in questo caso un array di numeri interi, e i due estremi di ordinamento left e right.

All'interno di questo metodo vengono fatte tutte le operazioni di scambio ed è il metodo che implementa l'algoritmo.

Il corpo del metodo contiene semplicemente delle operazioni di scambio effettuate solo in certe condizioni. Il principio molto elementare è che è inutile scambiare due elementi già ordinati, quindi si fa il controllo tra il pivot e l'elemento j.

Gli indici hanno il seguente significato:

  • i indica l'elemento più piccolo che si è esaminato;
  • j indica l'elemento corrente;

Il metodo sort non fa altro che fare da metodo wrapper a partition. Viene effettuato il controllo su low e high per verificare che "abbiano senso" e che non si verifichino situazioni dove low=2 e high=1 in virtù del fatto che si verrebbero a creare situazioni inconsistenti.

Viene inoltre calcolato il partition index, ovvero l'indice di partizionamento.

Abbiamo infine il main, dove viene creato l'array da ordinare. Successivamente viene richiamato il metodo sort sull'array e con indici 0 e n-1 (dove n indica la lunghezza dell'array).

Precisiamo che ho scelto volutamente di rendere statico il metodo sort. Ho deciso di fare questo perchè ho immaginato il codice presentato sopra come parte di una classe più grande che implementa più algoritmi insieme. Di conseguenza, essendo sort statico, lo deve essere anche partition

Si sarebbe potuto tranquillamente creare un metodo non statico da richiamare su un oggetto di tipo QuickSort.

Chiaramente, come nella maggior parte delle situazioni che si presentano in informatica, ci sono diverse varianti dell'implementazione de Quick Sort. Tutte hanno lo stesso risultato finale. Ciò che cambia sono i dettagli implementativi.

Cenni sulla complessità

Il tempo impiegato dal QuickSort può essere espresso come:

T(n) = T(k) + T(n-k-1) + theta(n)

I primi due termini sono le due chiamate ricorsive e k indica gli elementi minori del pivot. Il tempo effettivo dipende dalla scelta del pivot. Vediamo alcuni

casi notevoli.

Caso peggiore: 

T(n) = T(n-1) + theta(n)

Accade quando si prende come pivot sempre l'elemento più grande o l'elemento più piccolo

La complessità è assimilabile a theta(n2). Notiamo come qui la complessità sia esponenziale.

Caso migliore:

T(n) = 2T(n/2) + theta(n)

Qui la complessità è assimilabile a  theta(nLogn).

Caso intermedio:

T(n) = T(n/9) + T(9n/10) + theta(n)

Per fare un'analisi accurata della complessità nel caso intermedio, bisognerebbe calcolare tutte le possibili permutazioni degli elementi della collezione e non è per niente facile. Ci si può fare un'idea della complessità considerando il caso in cui partition mette O(n/9) elementi in un set e O(9n/10) elementi nell'altro.

La complessità è assimilabile a  theta(nLogn) anche in questo caso.

Curiosità: che cos'è il three-way-quick-sort?

Il three-way-quick-sort è una versione del Quick Sort dove la collezione da ordinare viene divisa così come segue:

  • array[low...i] è l'insieme degli elementi minori del pivot;
  • array[i...j-1] è l'insieme degli elementi uguali al pivot;
  • array[j...high] è l'insieme degli elementi maggior idel pivot;

E' evidente che questa versione sia conveniente solo quando ci sono diversi elementi ridondanti nella collezione. In caso contrario sarebbe priva di senso.

 
 
 
 
 

Articoli correlati

    Java Strutture Dati: Liste Concatenate

    Con il 2020 andiamo ad esaminare un nuovo aspetto della programmazione: le strutture dati. Spesso capita a tutti di utilizzare strutture messe a disposizione dai vari linguaggi di programmazione. L'obiettivo sarà…

    Java Algoritmi di Ordinamento: Selection Sort

    Andiamo oggi ad analizzare in dettaglio un algoritmo di ordinamento non molto efficiente ma piuttosto utilizzato in diversi ambiti. Stiamo parlando del Selection Sort. Vediamo meglio in dettaglio. Intuizione L'idea alla base è quella…

    Java algoritmi di ordinamento: Merge Sort

    Andiamo oggi ad analizzare uno tra i migliori algoritmi di ordinamento: il Merge Sort. Detto anche algoritmo per fusione, fa parte della famiglia dei Divide and Conquer proprio come il Quick Sort. A differenza del…

    Come ridurre il consumo di memoria in Chrome

    Google ha iniziato a testare una nuova funzione chiamata "Tab Freeze" che mira a ridurre il consumo di memoria in Chrome. Ed è interessante, perché il browser ormai consuma parecchie…

    Come creare un aplicazione Vue.js in 5 minuti

    Vue.js sta acquisendo sempre più popolarità, diventando un importante concorrente di framework come Angular o React.js. Come framework per i principianti, conquista i cuori dei giovani sviluppatori front-end e delle…

    Siamo governati dagli algoritmi?

    Siamo governati dagli algoritmi Non passa un minuto senza che una macchina decida parte del nostro futuro. Non stiamo parlando solo di libri o film raccomandati: gli algoritmi oggigiorno decidono il…

    Java algoritmi di ordinamento: Bubble Sort

    Programmando, nasce spesso la necessità di ordinare le collezioni di dati o oggetti che devono poi essere manipolate. Ordinare una lista può essere utile nei casi in cui si debbano…

    Java Design Pattern: Prototype Pattern

    Andremo ora a parlare di un pattern creazionale che ci permette di "copiare con classe". Sì, anche se sembra strano, il compito fondamentale di questo pattern è copiare. Sto parlando…

    Java Design Pattern: Builder Pattern

    Andiamo oggi a parlare di un pattern creazionale che in molte situazioni può rappresentare una valida alternativa alla costruzione di oggetti mediante costruttori: il Builder Pattern. La necessità di introdurre meccanismi…

    Java Design Pattern: Strategy Pattern

    Uno dei pattern che gode di una notevole popolarità ed è al contempo piuttosto semplice è lo Strategy Pattern. Membro della famiglia dei pattern comportamentali, ha il compito di gestire algoritmi,…

    Java Design Pattern: Factory Pattern

    Continuando il discorso sui design pattern iniziato precedentemente, andiamo oggi a vedere un altro pattern molto utilizzato: il Factory Method Pattern. Il GoF (Gang of Four Design Patterns) lo definisce così: Definisce…

    Java: Introduzione ai design pattern: Singleton

    Chiunque abbia anche una minima esperienza di programmazione, si sarà reso conto di come i problemi sianoricorrenti. Infatti troviamo spesso problemi con uno stesso pattern ma con contesti differenti. Ad esempio, un…