Sortare rapida (Quick sort)

Quicksort efectuează sortarea bazându-se pe o strategie divide et impera. Astfel, el împarte lista de sortat în două subliste mai uşor de sortat. Paşii algoritmului sunt:

1. Se alege un element al listei, denumit pivot.
   
2. Se reordonează lista astfel încât toate elementele mai mici decât pivotul să fie plasate înaintea pivotului şi toate elementele mai mari să fie după pivot. După această partiţionare, pivotul se află în poziţia sa finală.
3. Se sortează recursiv sublista de elemente mai mici decât pivotul şi sublista de elemente mai mari decât pivotul.

O listă de dimensiune 0 sau 1 este considerată sortată.

#include "stdlib.h"
#include "time.h"
#include "stdio.h"

int *x;

int poz (int s, int d) {

int i=s, j=d, di=0, dj=1, aux;
while(i < j)
{ if(x[i] > x[j])
{ aux=x[i];
x[i]=x[j];
x[j]=aux;
di=1-di;
dj=1-dj; }
i+=di;
j-=dj; }
return i;
}


void quick (int s, int d) {

if(s < d) { int k=poz(s,d);
quick(s,k-1);
quick(k+1,d); }
}

int main () {

srand(time(NULL));
int n;
scanf("%d",&n);
x=(int *)malloc(n*sizeof(int));

int i;
for(i=0; i < n ;i++)
x[i]=rand()%100;
for(i=0; i < n ;i++)
printf("%d ",x[i]);
quick(0,n-1);

printf("\n");
for(i=0; i < n ;i++)
printf("%d ",x[i]);
printf("\n");

return 0;
}