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); // plus petits é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 tableaux 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 int * a, const int * b)  { // Pour qsort.
00045     return (*a < *b) ? -1 : (*a > *b) ? 1 : 0;
00046 }
00047 
00048 void quicksort(int tab[], int n) {
00049     quicksort_rec(tab, 0, n-1);
00050 }
00051 
00052 int main() 
00053 {
00054     int tab[TAB_SIZE]; 
00055     srand(time(NULL)); // Initialisation du générateur de nombres pseudo-aléatoire.
00056     randtab(tab, TAB_SIZE, 10);
00057     printtab(tab, TAB_SIZE);
00058     quicksort(tab, TAB_SIZE);
00059     //qsort(tab, TAB_SIZE, sizeof(int), compar);
00060     printf("----\n");
00061     printtab(tab, TAB_SIZE);
00062     return 0;
00063 }
00064 
00065 
00066