TP3/tp3.c

   1 #include <stdio.h>
   2 #if __BSD_VISIBLE
   3 #undef __BSD_VISIBLE
   4 #define __BSD_VISIBLE
   5 #endif
   6 #include <stdlib.h>
   7
   8 void AfficheTab(int T[], int n) {
   9     for (int i = 0; i < n; i++) {
  10         printf("T[%d]=%d\n", i, T[i]);
  11     }
  12 }
  13
  14 void TriFusion(int T[], int n) {
  15     int i = 0, j = 0, k = 0;
  16     int milieu = n/2;
  17     int* T1;
  18     int* T2;
  19
  20     if (n > 1) {
  21         T1 = malloc(milieu*sizeof(int));
  22         T2 = malloc(((n - milieu)*sizeof(int)));
  23         for (int i = 0; i < milieu; i++) {
  24             T1[i] = T[i];
  25         }
  26         for (int i = milieu; i < n; i++) {
  27             T2[i - milieu] = T[i];
  28         }
  29         TriFusion(T1, milieu);
  30         TriFusion(T2, n - milieu);
  31         while (k < milieu && j < (n - milieu)) {
  32             if (T1[k] <= T2[j]) {
  33                 T[i] = T1[k];
  34                 i++;
  35                 k++;
  36             } else {
  37                 T[i] = T2[j];
  38                 i++;
  39                 j++;
  40             }
  41         }
  42         while (k < milieu) {
  43             T[i] = T1[k];
  44             i++;
  45             k++;
  46         }
  47         while (j < n - milieu) {
  48             T[i] = T2[j];
  49             i++;
  50             j++;
  51         }
  52         free(T1);
  53         free(T2);
  54     }
  55 }
  56
  57 int main() {
  58     //int T[] = {2, 7, 2, 3, 4, 1, 5, 5};
  59     int T[] = {6, 2, 3, 1, 9, 10, 15, 13, 12, 17};
  60     int tabSize = sizeof(T)/sizeof(T[0]);
  61
  62     AfficheTab(T, tabSize);
  63
  64     TriFusion(T, tabSize);
  65
  66     AfficheTab(T, tabSize);
  67
  68     return 0;
  69 }