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.

 
 
Alessio Mungelli

Alessio Mungelli

Computer Science student at UniTo (University of Turin), Network specializtion, blogger and writer. I am a kind of expert in Java desktop developement with interests in AI and web developement. Unix lover (but not Windows hater). I am interested in Linux scripting. I am very inquisitive and I love learning new stuffs.

 
 
 

Articoli correlati

Ecco cosa dicono i tuoi mi piace sui social media

I social network sono diventati una presenza molto diffusa nella vita quotidiana della maggior parte delle persone, e sembra che rimarranno tali per un lungo periodo di tempo. Adesso, i…

Come scaricare un'e-mail in formato PDF in Gmail per Android

Ora scoprirete quanto sia facile salvare un'e-mail ricevuta o inviata tramite Gmail in formato PDF, il tutto con il vostro smartphone Android. Gmail è una delle applicazioni di posta elettronica più…

Un approccio a Java: switch statement

Ciao a tutti e bentornati! Dopo una pausa, torniamo oggi con un'altra parte del corso introduttivo alla programmazione, parlando di switch statement, conosciuto anche come costrutto di selezione multipla.  Intuizione L'idea dello switch statement…

Un approccio a Java: Il ciclo while

Ciao a tutti e bentornati! Dopo aver fatto una breve, ma corposa, introduzione sui cicli, andiamo oggi a vedere finalmente le prime implementazioni che utilizzano quello che abbiamo definito ciclo precondizionale. In Java, come…

Un approccio a Java: I cicli - Introduzione

Ciao a tutti e bentornati! Sino ad ora, abbiamo parlato di variabili e di strutture di selezione, andando a considerare alcuni degli aspetti fondamentali di questi due concetti. Teoricamente, per…

Un approccio a Java: strutture di selezione - casi d'uso

Ciao a tutti e bentornati! Sino ad ora ci siamo preoccupati di fare una carrellata quanto più completa riguardo i concetti fondamentali di cui abbiamo bisogno per approcciarci all'utilizzo delle…

Un approccio a Java: operatori booleani

La volta precedente, abbiamo ampiamente parlato delle variabili booleane, cercando di delineare quali siano le principali operazioni che si possono effettuare proprio a livello pratico.  Di tutti i casi esaminati, non abbiamo…

Un approccio a Java: le variabili booleane

Ciao a tutti e bentornati! La volta precedente, ho fatto un'introduzione alle strutture condizionali, definendo il loro funzionamento. Prima di poter dare qualche esempio pratico, è necessario chiarire in che modo ci…

Un approccio a Java: strutture condizionali

Ciao a tutti e bentornati! Le volte precedenti abbiamo introdotto il concetto di variabile, tentando di definire alcuni concetti basilari a riguardo.  Alcune situazioni fanno però intuire come il solo concetto…

Un approccio a Java: Le variabili - caso d'uso

Ciao a tutti amici e bentornati! Dopo l'introduzione fatta sulle variabili, cerchiamo di analizzare alcune criticità che si possono presentare in situazioni alquanto comuni. Partiamo quindi analizzando degli esempi pratici.  Esempio 1: divisione…

Un approccio a Java: Le variabili

Ciao a tutti e bentornati! Quest'oggi inizieremo un percorso che ci porterà a studiare, ed eventualmente ripassare, quelle che sono le basi della programmazione. Inizieremo parlando di variaibli. Introduzione Chiunque voglia approcciarsi al…

Hashmap con Concatenamento: hashing, collisioni e prime funzioni

Oggi andremo a vedere dei concetti strettamente legati alle hashmap. I concetti che andremo a vedere sono quelli di hashing e collisioni. Hashing L'idea dell'hashing con concatenamento è quella di creare una sorta di array di…

Clicky