TP3: Implement the generic merge sort algorithm.
[Algorithmic_C.git] / TP3 / tp3.c
CommitLineData
a7c59b01
JB
1#include <stdio.h>
2#include <stdlib.h>
3
4void 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
10void TriFusion(int T[], int n) {
11 int i = 0, j = 0, k = 0;
8c44116a 12 int milieu = n/2;
a7c59b01
JB
13 int* T1;
14 int* T2;
a7c59b01
JB
15
16 if (n > 1) {
8c44116a
JB
17 T1 = malloc(milieu*sizeof(int));
18 T2 = malloc(((n - milieu)*sizeof(int)));
19 for (int i = 0; i < milieu; i++) {
a7c59b01 20 T1[i] = T[i];
a7c59b01 21 }
8c44116a
JB
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)) {
4c872c23
JB
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 }
8c44116a 38 while (k < milieu) {
a7c59b01
JB
39 T[i] = T1[k];
40 i++;
41 k++;
4c872c23 42 }
8c44116a 43 while (j < n - milieu) {
a7c59b01
JB
44 T[i] = T2[j];
45 i++;
46 j++;
4c872c23
JB
47 }
48 free(T1);
49 free(T2);
a7c59b01
JB
50 }
51}
52
53int main() {
8c44116a
JB
54 //int T[] = {2, 7, 2, 3, 4, 1, 5, 5};
55 int T[] = {6, 2, 3, 1, 9, 10, 15, 13, 12, 17};
a7c59b01
JB
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}