TP 2 exo3: randomly choose the pivot in quick sort
[Algorithmic_C.git] / TP2 / exo3 / exo3.c
CommitLineData
8bfd43bc 1#include <stdio.h>
569df90a 2#include <stdlib.h>
8bfd43bc
JB
3
4void permuter(int T[], int i1, int i2) {
5 int tmp = T[i1];
6 T[i1] = T[i2];
7 T[i2] = tmp;
8}
9
10void 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
16void 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
51int 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}