TP2/exo3/exo3.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 void permuter(int T[], int i1, int i2) {
   5     int tmp = T[i1];
   6     T[i1] = T[i2];
   7     T[i2] = tmp;
   8 }
   9
  10 void AfficheTab(int T[], int n) {
  11     for (int i = 0; i < n; i++) {
  12         printf("T[%d]=%d\n", i, T[i]);
  13     }
  14 }
  15
  16 void TriRapide(int T[], int n) {
  17     // The optimal pivot choice is the median value in the tab
  18     int index_pivot = arc4random_uniform(n);
  19     int pivot = T[index_pivot];
  20     int TP[n];
  21     int TG[n];
  22     int np = 0;
  23     int ng = 0;
  24
  25     if (n == 1) {;}
  26     else if (n == 2) {
  27         if (T[0] > T[1]) { permuter(T, 0, 1); }
  28     }
  29     else if (n > 2) {
  30         for (int i = 1; i < n; i++) {
  31             if (T[i] < pivot) {
  32                 TP[np] = T[i];
  33                 np++;
  34             } else {
  35                 TG[ng] = T[i];
  36                 ng++;
  37             }
  38         }
  39         TriRapide(TP, np);
  40         TriRapide(TG, ng);
  41         for (int i = 0; i < np; i++) {
  42             T[i] = TP[i];
  43         }
  44         T[np] = pivot;
  45         for (int i = 0; i < ng; i++) {
  46             T[np + 1 + i] = TG[i];
  47         }
  48     }
  49 }
  50
  51 int main() {
  52     int T[7] = {4, 2, 7, 3, 8, 6, 5};
  53
  54     AfficheTab(T, 7);
  55
  56     TriRapide(T, 7);
  57
  58     AfficheTab(T, 7);
  59
  60     return 0;
  61 }