Implémentation du tri d'un tableau
Maintenant que vous connaissez l'algorithme et que vous avez vu sur un exemple son fonctionnement, nous pouvons passer à son implémentation !
Mais avant cela, on remarque qu'il est possible de décomposer l'algorithme en plusieurs « sous-fonctions », ce qui facilitera notre travail :
- La recherche de l'élément le plus grand ;
- L'échange de deux éléments ;
- La réalisation du tri.
La fonction max()
Le fonctionnement de cette fonction (qui prend en paramètre un tableau et sa taille pour renvoyer l'indice de l'élément le plus grand) est simple : on se contente de parcourir l'intégralité du tableau pour à chaque fois comparer l'élément actuel avec le maximum provisoire.
J'ai choisi de ne conserver que l'indice du maximum provisoire, que je définis par défaut comme étant celui de la première valeur du tableau.
Le choix de cette valeur de départ est important ! En effet, si vous définissez directement une valeur telle que 0 et que votre tableau est du type {-6, -3, -2, -18}, votre algorithme renverra un maximum erroné !
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | /**
* Renvoie l'indice du plus grand élément du tableau
*
* int tab[] :: tableau dans lequel on effectue la recherche
* int taille :: taille du tableau
*
* return int l'indice du plus grand élément
**/
int max(int tab[], int taille)
{
// on considère que le plus grand élément est le premier
int i=0, indice_max=0;
while(i < taille)
{
if(tab[i] > tab[indice_max])
indice_max = i;
i++;
}
return indice_max;
}
|
La fonction echanger()
Le but ici est d'échanger deux éléments (dont on connait les indices) d'un tableau.
On agit de la même manière que lorsqu'on souhaite échanger le contenu de deux verres d'eau : on prend un troisième verre pour stocker temporairement un des contenus à échanger (l'image peut paraitre futile ou puérile, mais c'est exactement le comportement que reproduit cette petite fonction
).
Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | /**
* Échange deux éléments d'un tableau
*
* int tab[] :: tableau dans lequel on effectue l'échange
* int x :: indice du premier élément
* int y :: indice du second élément
*
* return void
**/
void echanger(int tab[], int x, int y)
{
int tmp;
tmp = tab[x];
tab[x] = tab[y];
tab[y] = tmp;
}
|
La fonction tri_selection()
Petit exo du jour, bonjour ! (Eh oui, je ne vais quand même pas tout faire ... si ?)
Aujourd'hui et de manière totalement inopinée, je vais vous demander d'implémenter un algorithme qui vous est totalement inconnu ! Il est le suivant :
- Tant que la taille du tableau est supérieure à 0 :
- Rechercher l'indice de l'élément le plus grand ;
- Échanger cet élément avec le dernier du tableau ;
- Décrémenter la taille.
Car oui, implémenter l'algorithme de tri par sélection n'est pas plus compliqué que cela. La preuve, même vous, zéros, allez y parvenir !
Secret (cliquez pour afficher)Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | /**
* Trie le tableau donné selon l'algorithme de tri par sélection
*
* int tab[] :: tableau à trier
* int taille :: taille du tableau
*
* return void
**/
void tri_selection(int tab[], int taille)
{
int indice_max;
// à chaque tour de boucle, on va déplacer le plus grand élément
// vers la fin du tableau, on diminue donc à chaque fois sa taille
// car le dernier élément est obligatoirement correctement
// placé (et n'a donc plus besoin d'être parcouru/déplacé)
for(; taille > 1 ; taille--) // tant qu'il reste des éléments non triés
{
indice_max = max(tab, taille);
echanger(tab, taille-1, indice_max); // on échange le dernier élément avec le plus grand
}
}
|
J'ai aussi codé une version récursive de ce tri (qui me parrait plus "naturelle", mais ne diffère en rien ou presque de la version itérative) :
Secret (cliquez pour afficher)Code : C 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | /**
* Trie le tableau donné selon l'algorithme de tri par sélection
*
* VERSION RÉCURSIVE
*
* int tab[] :: tableau à trier
* int taille :: taille du tableau
*
* return void
**/
void tri_selection_recursif(int tab[], int taille)
{
// un tableau d'un seul élément ou moins n'a pas besoin d'être trié
if(taille <= 1)
return;
echanger(tab, taille-1, max(tab, taille)); // on échange le dernier élément avec le plus grand
// on rappelle la fonction en diminuant la taille du tableau
// on peut faire cela car on est certain que le dernier élément
// est le plus grand (donc plus besoin de le déplacer)
return tri_selection_recursif(tab, taille-1);
}
|
Vous noterez que dans les deux versions du tri (récursive ou pas), aucune optimisation n'a été apportée. Je ne vérifie par exemple pas si j'ai effectivement besoin de réaliser l'échange (si max(...) == taille-1, pas besoin d'échanger quoi que ce soit) ... je laisse cela à votre charge ! =)
Pour vous entrainer, essayez de coder le tri par sélection en recherchant non plus l'élément le plus grand, mais l'élément le plus petit !
Implémentation du tri d'une liste
Eh oui, bien que je vous parle depuis le début du tutoriel du « cas particulier » des tableaux, il faut aussi savoir cet algorithme fonctionne parfaitement sur d'autres structures de données, dont les listes !
Cependant, bluestorm ayant déjà traité cette partie du sujet dans
son tutoriel sur l'algorithmique, je me contenterai de vous rediriger vers ce dernier (deux implémentations sont proposées : une en OCaml et l'autre en C).
Le tri par sélection
).
alatox
Trouvez une formation
I LOVE C 
Suggestions
Flux RSS News
Facebook
Google+