Commit | Line | Data |
---|---|---|
8bfd43bc JB |
1 | #include <stdio.h> |
2 | ||
3 | void permuter(int T[], int i1, int i2) { | |
4 | int tmp = T[i1]; | |
5 | T[i1] = T[i2]; | |
6 | T[i2] = tmp; | |
7 | } | |
8 | ||
9 | void AfficheTab(int T[], int n) { | |
10 | for (int i = 0; i < n; i++) { | |
11 | printf("T[%d]=%d\n", i, T[i]); | |
12 | } | |
13 | } | |
14 | ||
15 | void TriRapide(int T[], int n) { | |
ab72462d | 16 | // The optimal pivot choice is the median value in the tab |
8bfd43bc JB |
17 | int pivot = T[0]; |
18 | int TP[n]; | |
19 | int TG[n]; | |
20 | int np = 0; | |
21 | int ng = 0; | |
22 | ||
23 | if (n == 1) {;} | |
24 | else if (n == 2) { | |
25 | if (T[0] > T[1]) { permuter(T, 0, 1); } | |
26 | } | |
27 | else if (n > 2) { | |
28 | for (int i = 1; i < n; i++) { | |
29 | if (T[i] < pivot) { | |
30 | TP[np] = T[i]; | |
31 | np++; | |
32 | } else { | |
33 | TG[ng] = T[i]; | |
34 | ng++; | |
35 | } | |
36 | } | |
37 | TriRapide(TP, np); | |
38 | TriRapide(TG, ng); | |
39 | for (int i = 0; i < np; i++) { | |
40 | T[i] = TP[i]; | |
41 | } | |
42 | T[np] = pivot; | |
43 | for (int i = 0; i < ng; i++) { | |
44 | T[np + 1 + i] = TG[i]; | |
45 | } | |
46 | } | |
47 | } | |
48 | ||
49 | int main() { | |
50 | int T[7] = {4, 2, 7, 3, 8, 6, 5}; | |
51 | ||
52 | AfficheTab(T, 7); | |
53 | ||
54 | TriRapide(T, 7); | |
55 | ||
56 | AfficheTab(T, 7); | |
57 | ||
58 | return 0; | |
59 | } |