Sorting: bubble, selection, and insertion
Mettre un tableau en ordre
- Trier réorganise un tableau pour que les éléments aillent du plus petit au plus grand.
- Nous trions in place : nous déplaçons des éléments à l'intérieur du même tableau, sans valeur de retour.
- Trois méthodes classiques font cela : le tri par bulle, insertion, et sélection.
Échanger deux éléments
- Tout tri a besoin d'échanger deux éléments. Sauvegardez-en un dans un temporaire, puis écrasez-le.
int t = a[i]; a[i] = a[j]; a[j] = t;échange les positionsietj.- Oublier le temporaire fait perdre l'une des valeurs — gardez-le toujours.
Tri bulle
- Passez en revue le tableau et comparez chaque paire de voisins :
a[j]eta[j + 1]. - S'ils sont dans le mauvais ordre, échangez-les. La plus grande valeur "remonte" vers la fin.
- Répétez les passes jusqu'à ce que tout le tableau soit en ordre.
Tri par insertion
- Considérez la partie gauche du tableau comme déjà triée, et agrandissez-la d'un élément à la fois.
- Prenez l'élément suivant comme clé, décalez les éléments triés plus grands vers la droite, puis insérez la clé dans le vide.
- C'est ainsi que beaucoup de gens trient des cartes à jouer dans leur main.
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
Erreurs courantes
- Bubble, selection et insertion sort sont tous en O(n²).
- Tracez un petit tableau à la main pour vérifier votre tri.
À vous maintenant
- Triez ascendant (plus petit d'abord), in place, sans valeur de retour.
- Le vérificateur teste plusieurs tableaux, y compris des négatifs et un déjà trié.
- N'écrivez pas de
main— le vérificateur en fournit une.
Regardez un tri s'exécuter
Bubble / selection / insertion all compare and swap into order.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete void swap(int a[], int i, int j) so it exchanges the items at index i et j, in place (no return). Do non write a main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do non write a main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Complete void insertion_sort(int a[], int n) so it sorts the array ascending, in place, using insertion sort (take each item as a key and shift bigger items right). Do non write a main.
Cliquez sur Exécuter pour voir le résultat ici.