Commit | Line | Data |
---|---|---|
a7c59b01 JB |
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; | |
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 | ||
53 | int 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 | } |