Quick Sort in C

In questo articolo studieremo l’implementazione del quick sort in C.
Il quick sort è un algoritmo che viene utilizzato per ordinare i dati in un vettore (array).
Esso utilizza, come il merge sort, il metodo divide et impera, è cioè basato su questa tecnica:

  • Divide: Si suddivide il problema in sotto-problemi più piccoli;
  • Impera: si risolvono i problemi in maniera ricorsiva (ovvero un algoritmo che richiama se stesso);
  • Combina: al fine di ottenere il risultato finale si combina l’output   ottenuto dalle precedenti chiamate ricorsive.

Il Quick Sort è infatti un algoritmo ricorsivo che ha, generalmente, prestazioni migliori tra quelli basati su confronto.

In questo algoritmo la ricorsione viene fatta non dividendo il vettore in base agli indici ma in base al suo contenuto.

Dunque l’idea base del quick sort è questa:

  • Si sceglie l’elemento centrale del vettore (detto pivot) e lo si memorizza in una variabile

  • a sinistra si mettono gli elementi >= pivot

  • a destra si mettono gli elementi < pivot

  • si ordina ricorsivamente la parte destra e la parte sinistra.

La procedura che divide in due parti il vettore si chiama partition. 

Chiaramente la scelta del pivot non è legata necessariamente al primo elemento, potrebbe anche essere l’ultimo o il mediano oppure essere un elemento random.

Spieghiamo con un esempio il funzionamento del quick sort.

Scegliamo come Pivot il primo elemento, dunque Pivot=4.

Dobbiamo avere a sinistra gli elementi minori di Pivot, a destra gli elementi maggiori.

Facciamo partire l’indice i da sinistra ovvero dal primo elemento e l’indice j da destra ovvero dall’ultimo elemento.

Per comodità ci riferiremo a primo e ultimo per vedere in dettaglio tutti i passaggi.

Dapprima avremo:

Pivot=4 (si trova in posizione i)

primo=4

ultimo=8

quicksort primo passo

Ci chiediamo Pivot è minore di ultimo? Cioè 4 è minore di 8?

Si, allora procedo e sposto l’indice j (perchè a destra devo avere gli elementi maggiori, quindi non devo scambiarli!)

Quindi avremo:

Pivot=4   (si trova in posizione i)

primo=4

ultimo=3

quicksort passo 2

Ci poniamo allora la domanda  Pivot è minore di ultimo?

No, allora sposto Pivot in posizione j, cioè in ultimo.

Quindi avrò il terzo passaggio:

Pivot=4 (si trova in posizione j)

primo=3

ultimo=4

quicksort terzo passo

Adesso Pivot è in posizione indicata dall’indice j, dunque sposto l’indice i.

Mi chiedo Pivot è maggiore di primo?

Si, allora sposto l’indice i. E continuo spostando l’indice i fino all’elemento 5.

Quindi avrò:

Pivot=4 (si trova in posizione j)

primo=5

ultimo=4

quicksort quarto passaggio

Mi chiedo ancora Pivot è maggiore di primo?

No, allora sostituisco Pivot nella posizione di primo.

Quindi avrò:

Pivot=4 (si trova in posizione i)

primo=4

ultimo=5

Come in figura sotto:

quicksort quinto passo


Adesso Pivot si trova in posizione i, facciamo muovere j.

Cioè Pivot è minore di ultimo? Si allora sposto l’indice j e avrò:

Pivot=4 (si trova in posizione i)

primo=4

ultimo=0

quicksort sesto passo

Pivot è minore di ultimo?

No allora li scambiamo. Avremo:

Pivot=4 (si trova in posizione j)

primo=0

ultimo=4

Quindi ci chiediamo Pivot è maggiore di primo?

Si, allora spostiamo l’indice i e avremo la situazione:

Pivot=4 (si trova in posizione i)

primo=4

ultimo=2

quicksort settimo passaggio

Adesso chiediamo: Pivot è minore di primo?

Si allora l’indice i coinciderà con j.

Adesso che abbiamo a destra gli elementi maggiori del Pivot e a sinistra gli elementi minori dobbiamo procedere con l’ordinamento dei due sotto-array procedendo allo stesso modo.

Sviluppo dell’algoritmo Quick Sort in C

#include<stdio.h>
#define MAX 100

int insert_array(int a[]) {
  int n, i;
  printf("Quanti elementi?: ");
  scanf("%d", &n);

  for (i=0; i<n; i++) {
  	 printf("elemento %d: ", i);
  	    scanf("%d", &a[i]);
  }
  return(n);
}

void stampa_array(int a[], int n) {
  int i;
  for (i=0; i<n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  return;
}

void quicksort(int a[MAX],int primo,int ultimo){
   int i, j, pivot, temp;
/*pivot -- inizialmente il pivot è il primo elemento
primo e ultimo sono le due variabili che servono per scorrere l'array
*/
   if(primo<ultimo){
      pivot=primo;
      i=primo;
      j=ultimo;     
      
      while(i<j){
         while(a[i]<=a[pivot]&&i<ultimo)
            i++;
         while(a[j]>a[pivot])
            j--;
         if(i<j){   
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
         }
      }

      temp=a[pivot];
      a[pivot]=a[j];
      a[j]=temp;
      quicksort(a,primo,j-1);
      quicksort(a,j+1,ultimo);
   }
}

int main(){
   int n, a[MAX],i;
   n = insert_array(a);
   printf("Array iniziale: "); 
   stampa_array(a,n);    
   quicksort(a,0,n-1);
   printf("Array ordinato con quick-sort: ");
   stampa_array(a,n);
   return 0;
}

Il tempo di esecuzione del quick sort è proporzionale a n log n dunque è molto inferiore a n2.

Chiaramente questo è solo un esempio di possibile implementazione del quick sort in C.

Alcuni link utili

Array o vettori

Selection sort in C

Merge sort in C

Insertion Sort in C

Autore dell'articolo: Cristina

Avatar per Coding Creativo

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *