QuickSort: codifica in linguaggio C

In questo articolo si esaminerà la codifica in linguaggio C dell'algoritmo del Quicksort.

Risorse collegate

• Il codice completo lo trovi qui
• Trovi la spiegazione teorica al seguente indirizzo:

Useremo due direttive e due variabili globali:

• La prima direttiva definisce il numero di elementi presenti nel vettore.
• La seconda direttiva serve per compilare linee di codice alternative fra loro a seconda che si è in fase di test del programma o in una situazione reale.
• la variabile intera nc serve per contare il numero di confronti effettuati
• la variabile n_elem memorizza il numero effettivo di celle utilizzate nel vettore

Attenzione non confondere una direttiva con una variabile: una direttiva è rivolta al compilatore per istruirlo di sostituire ad ogni occorrenza di NRO_ELEMENTI il numero 100 e non occupa memoria.

Esaminiamo il main().

Per cominciare una direttiva al compilatore (linee 139-145): se siamo in modalità test carichiamo un vettore statico di 15 elementi altrimenti richiamiamo la funzione carica_vettore che consentirà all'utente di indicare quanti e quali elementi caricare. Poi stampiamo tutti gli elementi sulla stessa riga (linee 147-149).

La linea 151 evidenzia gli elementi da confrontare inizialmente.

Con la linea 153 si richiama la funzione quicksort, passando come parametri il vettore, l'indice del primo e dell'ultimo elemento (cioè si considera inizialmente l'intero vettore). Infine si stampa il risultato dell'ordinamento e si indicano il numero di confronti effettuati per l'intero processo.

La funzione carica-vettore prende in input un vettore di interi. Sulla linea 22 dichiariamo due variabili di tipo intero: n indicherà quanti elementi si vorranno caricare e i sarà un indice. Il ciclo post condizionato (linee 24-27) serve per inserire il numero di elementi da caricare che non deve essere minore o uguale a zero o maggiore del numero degli elementi possibili per il vettore. Con il ciclo enumerativo (linee 29-32) carichiamo effettivamente ogni elemento del vettore sulla linea 33 ritorniamo al programma chiamante restituendo il valore n degli elementi caricati effettivamente. Attenzione In linguaggio C i vettori sono passati alle funzioni sempre per riferimento.

La funzione stampa_vettore prende in input un vettore a di interi e due indici p e u che indicheranno il primo e ultimo elemento del vettore da stampare. A livello locale si usa un indice i. Il codice delle linee 38-40 serve per stampare gli elementi sulla stessa riga; esso stampa a partire dalla posizione p e arriva fino alla posizione u compresa: questo ci permette di stampare anche solo una parte del vettore; quando gli elementi sono esauriti, si invia un carattere newline per andare a capo.

Questa funzione prende in input tre parametri: come al solito il vettore a di interi è passato per riferimento, il secondo il terzo parametro sono indici che puntano agli elementi da scambiare. Si crea una variabile locale chiamata temp in cui andiamo a copiare il contenuto di a[x]; in a[x] si copia a[y] e infine in a[y] si copia temp. Lo scambio fra le due celle del vettore è effettuato.

La funzione colora() è intenzionalmente tralasciata poiché non funzionale all'algoritmo del Quicksort

La funzione partiziona() è il vero nucleo dell'intero algoritmo. Esso prende in input il vettore a e due indici sx e dx che delimitano la porzione di vettore da prendere in considerazione. Si incomincia con salvare una copia dei due indici dx e sx (linee 92-93). Alla linea 95 si dà inizio ad un ciclo iterativo che verrà ripetuto fintantoché sx é minore di dx. Si noti che, poiché sx si muove verso destra e dx si muove verso sinistra, questi due indici convergono e finiranno per diventare uguali: sarà quello il momento in cui il ciclo avrà termine e il perno si sarà stabilizzato nella sua posizione finale. Nelle linee 96-101 si sceglie come perno l'elemento puntato da sx e poi si incomincia a decrementare dx continuando fino a quando non risulta vera la condizione a[dx]<a[p]. Quando ciò si verifica si scambiano gli elementi puntati da p e da dx (linea 103).

Specularmente, nelle linee 107-112, si sceglie come perno l'elemento puntato da dx e poi si incomincia a incrementare sx continuando fino a quando non risulta vera la condizione a[sx]>a[p]. Quando ciò si verifica si scambiano gli elementi puntati da p e da sx (linea 114). Si ricomincia dalla linea 95 se sx e dx sono diversi, altrimenti il procedimento termina perché il perno ha raggiunto la posizione che gli compete. L'indice di tale posizione viene restituita alla funzione chiamante (linea 118).

Questa funzione prende in input il vettore a e due indici primo e ultimo che puntano alla porzione di vettore da considerare effettivamente. Per la condizione posta sulla linea 128 la funzione opera solo se primo e ultimo sono diversi, cioè se il vettore ha almeno due elementi: In tal caso si richiama la funzione a partiziona(...) indicando la porzione di vettore da ordinare.

La funzione partiziona() restituirà l'indice del perno all'interno del (sub)vettore considerato, dopo aver posto a sinistra del perno tutti gli elementi minori di a[p] e a destra del perno tutti gli elementi maggiori di a[p]. Nella figura accanto il perno è mostrato in rosso, l'altro elemento di confronto in verde (cioè a[dx] se il perno sta a sinistra oppure a[sx] se il perno sta a destra). Le righe contrassegnate da << sono quelle in cui avviene lo scambio di posizione tra a[p] e l'altro elemento. Si noti come gli elementi colorati si avvicinano fino a quando il perno iniziale 52 non trova la sua posizione stabile: a quel punto il partizionamento è fatto con tutti gli elementi più piccoli di 52 alla sua sinistra e tutti gli elementi più grandi alla sua destra.

Perciò sarà possibile richiamare la funzione quicksort() con le 2 porzioni di vettore in cui è stato diviso il (sub)vettore iniziale.

Attenzione La funzione quicksort() è un esempio di funzione ricorsiva, cioè una funzione che richiama se stessa; la condizione (primo < ultimo) della linea 128 è di fondamentale importanza per evitare la ricorsione infinita: quando primo diventa uguale a ultimo, cioè quando il (sub)vettore è ridotto ad un solo elemento, il processo di ricorsione termina.