LabASD - Quicksort

Nicolas Farabegoli nicolas.farabegoli2@unibo.it

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-03-15

Implementare l'algoritmo Quicksort. Quicksort è un algoritmo di ordinamento ricorsivo di tipo divide et impera inventato da Charles Antony Richard Hoare nel 1959 e pubblicato nel 1961.

Figura 1: C. A. R. Hoare By Photograph by Rama, Wikimedia Commons, Cc-by-sa-2.0-fr, CC BY-SA 2.0 fr, https://commons.wikimedia.org/w/index.php?curid=15568323
Figura 1: C. A. R. Hoare By Photograph by Rama, Wikimedia Commons, Cc-by-sa-2.0-fr, CC BY-SA 2.0 fr, https://commons.wikimedia.org/w/index.php?curid=15568323

L'array da ordinare viene partizionato in modo diverso rispetto a Merge Sort. In particolare, Quicksort fa uso di una funzione partition(v, start, end) che, data una porzione di array v[start..end], seleziona uno dei valori detto pivot (chiamiamolo \(p\)). Successivamente, il contenuto della porzione di array viene permutato in modo che gli elementi minori o uguali a \(p\) si trovino a sinistra rispetto al pivot, e gli elementi maggiori a \(p\) si trovino a destra. La funzione partition() deve restituire la posizione (indice) del pivot. Si faccia riferimento alla Figura 2.

Figura 2: Risultato della funzione partition(v, start, end)
Figura 2: Risultato della funzione partition(v, start, end)

Di conseguenza, il pivot si trova nella posizione corretta rispetto all'array ordinato. Per completare l'ordinamento, Quicksort viene invocato ricorsivamente sul sottovettore che precede e segue la posizione del pivot.

La parte più complessa di QuickSort è la funzione partition(). Esistono diverse strategie per realizzarla; quella descritta nal libro si basa sul mantenimento delle invarianti seguenti (vedi Figura 3):

Figura 3: Invariante della funzione partition(v, start, end)
Figura 3: Invariante della funzione partition(v, start, end)

In rete si trovano molte animazioni di Quicksort.

Le prestazioni di Quicksort dipendono dalla bontà del partizionamento. Nel caso ideale in cui il pivot si trovi quasi al centro del sottovettore, il costo asintotico \(T(n)\) soddisfa l'equazione di ricorrenza:

\[ T(n) = \begin{cases} c_1 & \mbox{se } n \leq 1 \\ 2T(n/2) + c_2 n & \mbox{altrimenti} \end{cases} \]

che è la stessa di Merge sort e ha soluzione \(T(n) = \Theta(n \log n)\).

Se invece il partizionamento è totalmente sbilanciato (il pivot si trova all'inizio o alla fine di ciascun sottovettore), l'equazione di ricorrenza diventa

\[ T(n) = \begin{cases} c_1 & \mbox{se } n \leq 1 \\ T(n-1) + c_2 n & \mbox{altrimenti} \end{cases} \]

che ha soluzione \(T(n) = \Theta(n^2)\). È possibile evitare il caso pessimo scegliendo il pivot in modo casuale, oppure con strategie di partizionamento sofisticate ("mediana di mediane").

In questa esercitazione suggerisco di iniziare scegliendo il pivot in modo deterministico (l'algoritmo descritto nel libro di testo scelgie il pivot del sottovettore v[i..j] come v[j]). Una volta ottenuta una versione funzionante la si modifichi per scegliere il pivot in modo casuale.

Il programma fornito contiene alcuni test per verificare la parziale correttezza della funzione quicksort(). Nei test si confronta il risultato con quello prodotto dalla funzione qsort() della libreria standard C. La segnatura di qsort() è:

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
           int (*compare)(const void *, const void *));

dove:

Per compilare il programma da riga di comando:

    gcc -std=c90 -Wall -Wpedantic quicksort.c -o quicksort

(il flag -std=c90 indica di trattare il sorgente in modo conforme allo standard ANSI/ISO C90; è equivalente al flag -ansi).

Per approfondire

Questo programma misura in modo grossolano il tempo necessario per ordinare l'array. Considerando array di dimensioni sufficientemente grandi (es., 100000 elementi o più), come varia il tempo di esecuzione nei seguenti casi?

Per eseguire le prove occorre modificare la funzione main() per generare input opportuni. Nel caso possano risultare utili, vengono fornite due funzioni randab() e random_shuffle(), la cui specifica è indicata nei commenti al codice.

File