Quick sort

Il quick sort, ordinamento rapido, si basa sul paradigma divide et impera. Durante le prime istruzioni l'algoritmo si preoccupa di scegliere un elemento dell'array come pivot (perno) e partiziona la sequenza in due sottoinsiemi. Il primo sottoinsieme conterr à tutti gli elementi dell'array che sono minori o uguali al pivot scelto. Il secondo sottoinsieme, invece, conterrà tutti gli elementi dell'array che sono maggiori del pivot. A tale proposito una funzione per la partizione fa scorrere due indici (uno di questi parte dal primo elemento dell'array, il secondo dall'ultimo). Gli indici vengono incrementati (il primo) e decrementati (il secondo) fi nch è viene rispettata la condizione d'ordine nei confronti del pivot.Non appena ciò non è possibile, è evidente che è necessario scambiare i due elementi puntati dai rispettivi indici. Quando i due indici, a seguito dei rispettivi incrementi e decrementi, si incrociano la procedura per la partizione si arresta e va allora richiamata, ricorsivamente sul primo sottoinsieme e sul secondo, fino a ordinare l'intero vettore. Di seguito propongo una realizzazione dell'algoritmo in linguaggio C:

/* quicksort */
#include <stdio.h>

#define LENGTH 10

void quickSort (int *array, int left, int right);
void swap(int *x, int *y);

int main (void) {
   int i,array[LENGTH]={1,8,4,0,2,5,6,3,7,9};
   quickSort(array,0,LENGTH-1);
   printf("array: ");
   for (i=0;i<LENGTH;i++)
      printf("%d, ",array[i]);
   printf("\b\b;\n");
}

void quickSort (int *array, int left, int right) {
   int i=left, j=right;
   int pivot=array[(left+right)/2];
   do {
      while (array[i]<pivot) i++;
      while (array[j]>pivot) j--;
      if (i<=j) {
         swap(&array[i],&array[j]);
         i++; j--;
      }
   } while (i<=j);
   if (left<j) quickSort(array,left,j);
   if (i<right) quickSort(array,i,right);
}

void swap(int *x, int *y) {
   int temp=*x;
   *x=*y;
   *y=temp;
}