Working of the Bubble Sort
Leçon 2 sur 11 du cours Tri à bulles de Coddy.
Le tri à bulles (Bubble sort) est un algorithme de tri simple qui parcourt les éléments d'une liste, compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre.
Le passage à travers la liste est répété jusqu'à ce que la liste soit triée.
Un exemple-
Nous devons trier une liste de 4 éléments : [3,4,2,1]
Premier passage :
Compare les deux premiers éléments
[3,4,2,1] -> [3,4,2,1] (Aucun changement, car ils sont déjà triés)
Compare les deux éléments suivants
[3,4,2,1] -> [3,2,4,1] (Échange les éléments pour les mettre dans l'ordre trié)
Compare les deux éléments suivants
[3,2,4,1] -> [3,2,1,4] (Échange les éléments pour les mettre dans l'ordre trié)
Premier passage terminé, qu'avez-vous observé ?
La liste est-elle triée ? Non, n'est-ce pas ?
Donc, nous devrons répéter le processus à nouveau.
Veuillez observer qu'avec le premier passage, nous avons l'élément maximum à la fin de la liste. Et c'est ce que nous essaierons d'obtenir lors des passages suivants.
Deuxième passage :
Compare les deux premiers éléments
[3,2,1,4] -> [2,3,1,4] (Échange les éléments pour les mettre dans l'ordre trié)
Compare les deux éléments suivants
[2,3,1,4] -> [2,1,3,4] (Échange les éléments pour les mettre dans l'ordre trié)
Compare les deux éléments suivants
[2,1,3,4] -> [2,1,3,4] (Aucun changement, car ils sont déjà triés)
Après le deuxième passage, remarquez que les deux derniers éléments sont triés.
Troisième passage :
Compare les deux premiers éléments
[2,1,3,4] -> [1,2,3,4] (Échange les éléments pour les mettre dans l'ordre trié)
Remarquez qu'après ce passage, nous avons obtenu la liste requise.
C'est ainsi que fonctionne le TRI À BULLES !
Maintenant, comprenons l'algorithme du tri à bulles dans la prochaine leçon.
Bon apprentissage !
Défi
FacileCréez une fonction nommée swap_list qui reçoit un tableau, la taille du tableau et deux indices. La fonction échange les éléments aux deux indices et renvoie la nouvelle liste.
Par exemple :
list=[1,2,3,4] (indexé à partir de 0)
n=4 (Nombre d'éléments dans la liste)
i=1 j=3 (indices à échanger)
[1,2,3,4] -> [1,4,3,2]
Retour : list= [1,4,3,2]
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
int* swap_list(int* arr, int arr_size, int n, int i, int j, int* returnSize) {
// Écrire le code ici
*returnSize = n;
return arr;
}
Toutes les leçons de Tri à bulles
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm