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