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 | ||
7287cc55 | 10 | /** This quick sort implementation only work with 2^n array size */ |
a7c59b01 JB |
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)); | |
7287cc55 | 17 | T2 = malloc(n/2*sizeof(int)); |
a7c59b01 JB |
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() { | |
7287cc55 | 53 | int T[] = {2, 7, 2, 3, 4, 1, 5, 5}; |
a7c59b01 JB |
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 | } |