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

    Linux per Principianti: Guida all'installazione di Ubuntu

    Abbiamo dato precedentemente una panoramica su qualche aspetto di base dei sistemi Unix e in particolar modo Ubuntu. Abbiamo infatti fatto un'introduzione, dopodichè abbiamo parlato di terminale Ubuntu e infine abbiamo parlato…

    Linux per Principianti: I permessi

    Nei precedenti articoli abbiamo fatto una breve introduzione al mondo Unix e nell'articolo successivo abbiamo parlato di comandi base per la gestione del file system. Oggi andremo a parlare di permessi. Come esempio prenderemo sempre…

    Emergenza Covid-19: Progetto Solidarietà Digitale

    Come ormai molti di noi avranno sentito, il Decreto della Presidenza del Consiglio dei Ministri del 9 marzo 2020, entrata in vigoore oggi, 10 marzo 2020, estende le misure di…

    Linux Per Principianti: Terminale Ubuntu

    Ho introdotto nell'articolo precedente, consultabile qui, i concetti base relativi al mondo del pinguino. Oggi andiamo a vedere alcune operazioni di base che si possono svolgere mediante linea di comando su…

    Linux per Principianti: Introduzione

    Se hai pensato di migrare da Windows a un sistema operativo Unix, o Linux nello specifico ci sono cose che dovresti sapere. L'obiettivo è quello di dare le informazioni essenziali…

    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…