00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <time.h> 
00004 #include <limits.h>
00005 
00006 #define TAB_SIZE 10
00007 
00008 void randtab(int tab[], int n, int lim) {
00009     int i;
00010     for (i=0; i<n; i++) 
00011         tab[i] = (int) (((double) lim+1) * rand() / (RAND_MAX+1.0));
00012 }
00013 
00014 void printtab(int tab[], int n) {
00015     int i;
00016     for (i=0; i<n; i++) 
00017         printf("tab[%d] = %d\n",i,tab[i]);
00018 }
00019 
00020 void swap(int tab[], int i, int j) {
00021     int tmp = tab[i];
00022     tab[i] = tab[j]; 
00023     tab[j] = tmp;
00024 }
00025 
00026 int partition(int tab[], int inf, int sup) {
00027     int idx_pivot = (inf + sup)/2; // choix d'un pivot (ici, le milieu)
00028     int i, j = inf; // j : index du pivot final
00029     swap(tab,inf,idx_pivot); // // On met le pivot en première position
00030     for (i = inf + 1; i <= sup; i++)
00031         if (tab[i] < tab[inf]) swap(tab,++j,i); // + petit éléments à gauche
00032     swap(tab,inf,j); // on remet le pivot au bon endroit dans le tableau
00033     return j;
00034 }
00035 
00036 void quicksort_rec(int tab[], int idx_g, int idx_d) {
00037     if (idx_g < idx_d) { // inutile de trier les tableau d'un élément
00038         int idx_pivot = partition(tab, idx_g, idx_d); 
00039         quicksort_rec(tab, idx_g, idx_pivot-1);
00040         quicksort_rec(tab, idx_pivot + 1, idx_d);
00041     }
00042 }
00043 
00044 int compar(const void * a, const void * b) { // pour qsort
00045     int c = * (int *) a;
00046     int d = * (int *) b;
00047     return (c < d) ? -1 : (c > d) ? 1 : 0;
00048 }
00049 
00050 void quicksort(int tab[], int n) {
00051     quicksort_rec(tab, 0, n-1);
00052 }
00053 
00054 int main() 
00055 {
00056     int tab[TAB_SIZE]; 
00057     srand(time(NULL)); // Initialisation du générateur de nombres pseudo-aléatoire
00058     randtab(tab, TAB_SIZE, 10);
00059     printtab(tab, TAB_SIZE);
00060     quicksort(tab, TAB_SIZE);
00061     //qsort(tab, TAB_SIZE, sizeof(int), compar);
00062     printf("----\n");
00063     printtab(tab, TAB_SIZE);
00064     return 0;
00065 }
00066 
00067 
00068