TP3: Add merge sort implementation
[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;
12 int* T1;
13 int* T2;
14
15 T1 = malloc(n/2*sizeof(int));
16 T2 = malloc((n - n/2)*sizeof(int));
17
18 if (n > 1) {
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
51int main() {
52 int T[] = {4, 2, 7, 3, 8, 1, 6, 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}