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");
}
} |
Partager