Sorting: bubble, selection, and insertion · Tri : bulle, sélection et insertion
Putting an array in order
- Sorting rearranges an array so the items go from smallest to largest.
- We sort in place: we move items around inside the same array, with no return value.
- Three classic methods do this: bubble, insertion, and selection sort.
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.
Swapping two elements
- Every sort needs to swap two items. Save one in a temporary, then overwrite.
int t = a[i]; a[i] = a[j]; a[j] = t;exchanges positionsiandj.- Forgetting the temporary loses one of the values — always keep it.
É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.
Bubble sort
- Go through the array and compare each pair of neighbours:
a[j]anda[j + 1]. - If they are in the wrong order, swap them. The biggest value "bubbles" to the end.
- Repeat the passes until the whole array is in order.
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.
Insertion sort
- Treat the left part of the array as already sorted, and grow it one item at a time.
- Take the next item as a key, shift bigger sorted items to the right, then drop the key into the gap.
- This is how many people sort playing cards in their hand.
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;
}
Common mistakes
- Bubble, selection and insertion sort are all O(n²).
- Trace a small array by hand to check your sort.
Erreurs courantes
- Bubble, selection et insertion sort sont tous en O(n²).
- Tracez un petit tableau à la main pour vérifier votre tri.
Now you try
- Sort ascending (smallest first), in place, with no return value.
- The checker tries several arrays, including negatives and an already-sorted one.
- Do not write a
main— the checker provides one.
À 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.
Watch a sort run · Regardez un tri s'exécuter
Bubble / selection / insertion all compare and swap into order. · Bulle / sélection / insertion comparent et échangent tous pour ordonner.
Complete void swap(int a[], int i, int j) so it exchanges the items at index i and · et j, in place (no return). Do not · non write a main. · Complétez void swap(int a[], int i, int j) pour qu'il échange les éléments aux indices i et j, in-place (sans retour). Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do not · non write a main. · Complétez void bubble_sort(int a[], int n) pour qu'il trie le tableau croissant, in-place, en utilisant le tri à bulles. Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
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 not · non write a main. · Complétez void insertion_sort(int a[], int n) pour qu'il trie le tableau croissant, in-place, en utilisant le tri par insertion (prenez chaque élément comme clé et décalez les éléments plus grands vers la droite). Ne pas écrire de main.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.