Trier un tableau
Ranger les valeurs dans l'ordre avec un algorithme simple, et profiter d'un tableau trié.
Ce que tu vas apprendre
- Comprendre le principe d'un tri par sélection
- Échanger deux cases d'un tableau
- Utiliser l'ordre d'un tableau trié (médiane, insertion, doublons)
Le tri par sélection
Idée : on cherche la plus petite valeur et on la place en première position, puis la plus petite parmi les restantes en deuxième position, et ainsi de suite.
Il faut deux boucles imbriquées : la boucle extérieure choisit la case à remplir i, la boucle intérieure cherche l'indice du minimum entre i et n - 1, puis on échange.
Il existe d'autres tris simples (à bulles, par insertion) : le tri à bulles fait l'objet d'un exercice de ce module. Pour 100 valeurs, tous sont instantanés.
Profiter d'un tableau trié
Une fois le tableau trié, beaucoup de problèmes deviennent simples : la médiane est au milieu, les valeurs égales sont côte à côte, le k-ième plus petit est en t[k - 1].
Pour trier dans l'ordre décroissant, il suffit d'inverser la comparaison.
Exemples commentés
1.Tri par sélection
#include <stdio.h>
int main(void) {
int t[100], n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &t[i]);
}
for (int i = 0; i < n - 1; i++) {
int imin = i; // indice du plus petit
for (int j = i + 1; j < n; j++) {
if (t[j] < t[imin]) {
imin = j;
}
}
int tmp = t[i]; // échange t[i] et t[imin]
t[i] = t[imin];
t[imin] = tmp;
}
for (int i = 0; i < n; i++) {
printf(i > 0 ? " %d" : "%d", t[i]);
}
printf("\n");
return 0;
}Entrée
5 4 1 3 9 2
Sortie
1 2 3 4 9
Après le tour i, les cases 0 à i contiennent les plus petites valeurs, dans l'ordre.
2.Insérer dans un tableau trié
#include <stdio.h>
int main(void) {
int t[101], n, v;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &t[i]);
}
scanf("%d", &v);
int i = n - 1;
while (i >= 0 && t[i] > v) { // on décale les plus grandes
t[i + 1] = t[i];
i--;
}
t[i + 1] = v; // la place libérée
n++;
for (int k = 0; k < n; k++) {
printf(k > 0 ? " %d" : "%d", t[k]);
}
printf("\n");
return 0;
}Entrée
4 1 3 5 7 4
Sortie
1 3 4 5 7
On décale vers la droite toutes les valeurs plus grandes que v, puis on place v dans le trou. C'est le cœur du tri par insertion.
Chaque exemple est compilé et exécuté automatiquement pour garantir la sortie affichée.
Erreurs fréquentes
Échanger sans variable temporaire
À éviter
t[i] = t[j]; t[j] = t[i];
À préférer
int tmp = t[i]; t[i] = t[j]; t[j] = tmp;
Comme pour deux variables : sans tmp, l'une des deux valeurs est perdue.
Se tromper dans les bornes
La boucle intérieure commence à i + 1 et va jusqu'à n - 1. Vérifie sur un tableau de 2 cases que le tri fonctionne.
Entraîne-toi
5 questions variées pour fixer la leçon : choix, résultat à prévoir, ligne à compléter, code à remettre dans l'ordre, erreur à trouver.
À toi de jouer !
7 exercices pour mettre cette leçon en pratique, du plus simple au plus avancé.