quicksort.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

void print(int size,int tab[size]) {
   for (int i=0;i<size;i++) printf("%d ",tab[i]);
}

void random_tab(int size,int tab[size],int inf,int sup) {
   assert(sup > inf);
   for (int i=0;i<size;i++) tab[i] = inf+rand()%(sup-inf);
}

void swap(int* p_a,int* p_b) { 
   int tmp = *p_a;
   *p_a = *p_b;
   *p_b = tmp;
}

int partition(int size,int array[size],int first,int last) {
   int pivot = array[last];
   int i = first-1,j = last;
   while (true) {
      do {
         i++;
      } while (array[i] < pivot && i<j);
      do {
         j--;
      } while(array[j] > pivot && i<j);
      if (i >= j) break;
      swap(&array[i],&array[j]);
   }
   swap(&array[i],&array[last]);
   return i;
}

void quicksort(int size,int array[size],int first,int last) {
   if (first < last) {
      int midpoint = partition(size,array,first,last);
      if (first < midpoint-1) quicksort(size,array,first,midpoint-1);
      if (midpoint+1 < last) quicksort(size,array,midpoint+1,last);
   }
}

void test_ordre(int size,int array[size]) {
   for (int i=0;i<size-1;i++) 
      if (array[i] > array[i+1]) {
         printf("erreur");
         return;
      }
   printf("ok");
}

int main(int argc,char** argv) {
   int size = atoi(argv[1]);
   int seed = atoi(argv[2]);
   srand(seed);
   int* res = (int*)malloc(size*sizeof(int));
   for (int k=0;k<20;k++) {
      random_tab(size,res,0,100);
      print(size,res);
      printf("\n");
      quicksort(size,res,0,size-1);
      print(size,res);
      test_ordre(size,res);
      printf("\n================\n");
   }
}