TP3/tp3.c

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