TP2/exo3/exo3.c

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