quicksort_part.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;
}

// Partition du tableau <array> autour d'une valeur pivot:
// compléter le code
int partition(int size,int array[size],int first,int last) {
   int pivot = array[last];
   int i = first-1,j = last;
   while (true) {
      // à compléter pour <i>: do {...} while (...);
      // à compléter pour <j>: do {...} while (...);
      if (i >= j) {
         break;
      }
      // à compléter: échanger cases <i> et <j> du tableau <array>
   }
   // à compléter: échanger cases <i> et <last> du tableau <array>
   return i;
}

// Tri rapide récursif
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);
      }
   }
}

// Test si le tableau <array> est ordonné croissant
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");
   }
}