Refinements to quick 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 quick 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 T1 = malloc(n/2*sizeof(int));
17 T2 = malloc(n/2*sizeof(int));
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() {
53 int T[] = {2, 7, 2, 3, 4, 1, 5, 5};
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 }