Quick Sort in C

Implementiamo il quick sort in C, un algoritmo di ordinamento che così come il merge sort segue il metodo divide et impera.
Il quick sort è un algoritmo che viene utilizzato per ordinare i dati in un vettore (array).

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.

Prima di risolvere l’algoritmo del quick sort in C, studiamo l’idea di base:

• 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.

Esempio del quick sort in C

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

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

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

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

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:

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

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

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 n².

Chiaramente quella presentata è 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