Add information on the pivot choice for quick sort.
[Algorithmic_C.git] / TP2 / exo3 / exo3.c
CommitLineData
8bfd43bc
JB
1#include <stdio.h>
2
3void permuter(int T[], int i1, int i2) {
4 int tmp = T[i1];
5 T[i1] = T[i2];
6 T[i2] = tmp;
7}
8
9void 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
15void 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
49int 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}