Properly handle memory management for merge sort implementation.
[Algorithmic_C.git] / 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 merge 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 if (n > 1) {
17 T1 = malloc(n/2*sizeof(int));
18 T2 = malloc(n/2*sizeof(int));
19 for (int i = 0; i < n/2; i++) {
20 T1[i] = T[i];
21 T2[i] = T[i + n/2];
22 }
23 TriFusion(T1, n/2);
24 TriFusion(T2, n/2);
25 while (k < n/2 && j < n/2) {
26 if (T1[k] <= T2[j]) {
27 T[i] = T1[k];
28 i++;
29 k++;
30 } else {
31 T[i] = T2[j];
32 i++;
33 j++;
34 }
35 }
36 while (k < n/2) {
37 T[i] = T1[k];
38 i++;
39 k++;
40 }
41 while (j < n/2) {
42 T[i] = T2[j];
43 i++;
44 j++;
45 }
46 free(T1);
47 free(T2);
48 }
49 }
50
51 int main() {
52 int T[] = {2, 7, 2, 3, 4, 1, 5, 5};
53 int tabSize = sizeof(T)/sizeof(T[0]);
54
55 AfficheTab(T, tabSize);
56
57 TriFusion(T,tabSize);
58
59 AfficheTab(T, tabSize);
60
61 return 0;
62 }