1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
| #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TAILLE_CHAINES 10
#define NB_ELEMS(t) ( sizeof (t) / sizeof *(t) )
static void copie_chaine(char *dest, char const *src, size_t taille_dest);
static void echanger_chaines(char table[][TAILLE_CHAINES], int gauche, int droite);
static void tri(char table[][TAILLE_CHAINES], size_t nelems);
static void tri_bis(char table[][TAILLE_CHAINES], int debut, int fin);
static int placement_pivot(char table[][TAILLE_CHAINES], int debut, int fin);
static void afficher_tableau(char table[][TAILLE_CHAINES], size_t taille);
int main(void)
{
char tableau[][TAILLE_CHAINES] =
{
"thierry",
"evelyne",
"zoe",
"daniel",
"nadine",
"paul",
"sylvain"
};
afficher_tableau(tableau, NB_ELEMS(tableau));
tri(tableau, NB_ELEMS(tableau));
afficher_tableau(tableau, NB_ELEMS(tableau));
return EXIT_SUCCESS;
}
/* Copie la chaine src dans la chaine dest de maniere securisee */
static void copie_chaine(char *dest, char const *src, size_t taille_dest)
{
if (dest != NULL && src != NULL && taille_dest && taille_dest > 0)
{
*dest = 0;
strncat(dest, src, taille_dest - 1);
}
}
/* Trie un tableau de nelems chaines de caracteres de longueur TAILLE_CHAINES */
static void tri(char table[][TAILLE_CHAINES], size_t nelems)
{
tri_bis(table, 0, nelems - 1);
}
/* Echange les elements d'indices gauche et droite du tableau table */
static void echanger_chaines(char table[][TAILLE_CHAINES], int gauche, int droite)
{
if (table != NULL && gauche != droite)
{
char tampon[TAILLE_CHAINES] = "";
copie_chaine(tampon, table[gauche], TAILLE_CHAINES);
copie_chaine(table[gauche], table[droite], TAILLE_CHAINES);
copie_chaine(table[droite], tampon, TAILLE_CHAINES);
}
}
/* Effectue le tri des caractere a l'aide de l'algorithme du tri rapide */
static void tri_bis(char table[][TAILLE_CHAINES], int debut, int fin)
{
int pivot;
if (debut < fin)
{
pivot = placement_pivot(table, debut, fin);
tri_bis (table, debut, pivot - 1);
tri_bis (table, pivot + 1, fin);
}
}
/* Placement de l'element pivot utilise dans le contexte de l'algorithme du
* tri rapide.
*/
static int placement_pivot(char table[][TAILLE_CHAINES], int debut, int fin)
{
/* On choisit le premier element du tableau comme element pivot */
char const *val_pivot = table[debut]; /* Valeur de l'element pivot */
int i = debut + 1; /* Indice pour le balayage par la gauche */
int j = fin; /* Indice pour le balayage par la droite */
do
{
/* On recherche depuis la gauche le premier element du tableau plus
grand que l'element pivot */
for ( ;i <= fin && strcmp(table[i], val_pivot) < 0; i++)
{
}
/* On recherche depuis la droite le premier element du tableau plus
petit que l'element pivot */
for ( ; strcmp(val_pivot, table[j]) < 0; j--)
{
}
/* Les elements d'indices i, j du tableau echanger leur place pour se
situer dans le bon sous-tableau par rapport à l'élément pivot */
if (i < j)
{
echanger_chaines(table, i, j);
}
} while (i < j);
/* On place l'element pivot au bon endroit */
echanger_chaines(table, debut, j);
return j;
}
/* Affiche un tableau de chaine de caracteres sur le flux de sortie standard */
static void afficher_tableau(char table[][TAILLE_CHAINES], size_t taille)
{
if (table != NULL && taille > 0)
{
size_t i;
for (i = 0; i < taille; i++)
{
printf("%s\n", table[i]);
}
printf("\n");
}
} |
