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 /** This quick sort implementation only work with 2^n array size */
  11 void TriFusion(int T[], int n) {
  12     int i = 0, j = 0, k = 0;
  13     int* T1;
  14     int* T2;
  15
  16     T1 = malloc(n/2*sizeof(int));
  17     T2 = malloc(n/2*sizeof(int));
  18
  19     if (n > 1) {
  20         for (int i = 0; i < n/2; i++) {
  21             T1[i] = T[i];
  22             T2[i] = T[i + n/2];
  23         }
  24     TriFusion(T1, n/2);
  25     TriFusion(T2, n/2);
  26     while (k < n/2 && j < n/2) {
  27         if (T1[k] <= T2[j]) {
  28             T[i] = T1[k];
  29             i++;
  30             k++;
  31         } else {
  32             T[i] = T2[j];
  33             i++;
  34             j++;
  35         }
  36     }
  37     while (k < n/2) {
  38         T[i] = T1[k];
  39         i++;
  40         k++;
  41     }
  42     while (j < n/2) {
  43         T[i] = T2[j];
  44         i++;
  45         j++;
  46     }
  47     free(T1);
  48     free(T2);
  49     }
  50 }
  51
  52 int main() {
  53     int T[] = {2, 7, 2, 3, 4, 1, 5, 5};
  54     int tabSize = sizeof(T)/sizeof(T[0]);
  55
  56     AfficheTab(T, tabSize);
  57
  58     TriFusion(T,tabSize);
  59
  60     AfficheTab(T, tabSize);
  61
  62     return 0;
  63 }