Une introduction à l'algorithme de tri à bulles

Le tri est l'une des opérations les plus élémentaires que vous puissiez appliquer aux données. Vous pouvez trier des éléments dans différents langages de programmation à l'aide de divers algorithmes de tri tels que le tri rapide, le tri à bulles, le tri par fusion, le tri par insertion, etc. Bubble Sort est l'algorithme le plus simple parmi tous ceux-ci.

Dans cet article, vous découvrirez le fonctionnement de l'algorithme Bubble Sort, le pseudocode du Bubble Sort algorithme, sa complexité temporelle et spatiale, et son implémentation dans divers langages de programmation tels que C++, Python, C et JavaScript.

Comment fonctionne l'algorithme de tri à bulles ?

Bubble Sort est l'algorithme de tri le plus simple qui parcourt la liste à plusieurs reprises, compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Ce concept peut être expliqué plus efficacement à l'aide d'un exemple. Considérons un tableau non trié avec les éléments suivants: {16, 12, 15, 13, 19}.

Exemple:

Ici, les éléments adjacents sont comparés et s'ils ne sont pas dans l'ordre croissant, ils sont échangés.

Pseudocode de l'algorithme de tri à bulles

En pseudo-code, l'algorithme de tri à bulles peut être exprimé sous la forme:

bubbleSort (Arr[], taille)
// boucle pour accéder à chaque élément du tableau
pour i=0 à taille-1 faire :
// boucle pour comparer les éléments du tableau
pour j=0 à taille-i-1 faire :
// comparer les éléments adjacents
si Arr[j] > Arr[j+1] alors
// les échanger
échanger (Arr[j], Arr[j+1])
fin si
fin pour
fin pour
finir

L'algorithme ci-dessus traite toutes les comparaisons même si le tableau est déjà trié. Il peut être optimisé davantage en arrêtant l'algorithme si la boucle interne n'a provoqué aucun échange. Cela réduira le temps d'exécution de l'algorithme.

Ainsi, le pseudocode de l'algorithme de Bubble Sort optimisé peut être exprimé sous la forme:

bubbleSort (Arr[], taille)
// boucle pour accéder à chaque élément du tableau
pour i=0 à taille-1 faire :
// vérifie si l'échange se produit
échangé = faux
// boucle pour comparer les éléments du tableau
pour j=0 à taille-i-1 faire :
// comparer les éléments adjacents
si Arr[j] > Arr[j+1] alors
// les échanger
échanger (Arr[j], Arr[j+1])
échangé = vrai
fin si
fin pour
// si aucun élément n'a été échangé, cela signifie que le tableau est trié maintenant, alors rompez la boucle.
si (non échangé) alors
Pause
fin si
fin pour
finir

Complexité temporelle et espace auxiliaire de l'algorithme de tri à bulles

La complexité temporelle dans le pire des cas de l'algorithme de tri à bulles est O(n^2). Cela se produit lorsque le tableau est en ordre décroissant et que vous souhaitez le trier par ordre croissant ou vice-versa.

La complexité temporelle dans le meilleur des cas de l'algorithme de tri à bulles est O(n). Cela se produit lorsque le tableau est déjà trié.

En rapport: Qu'est-ce que la notation Big-O ?

La complexité temporelle moyenne de l'algorithme de tri à bulles est O(n^2). Cela se produit lorsque les éléments du tableau sont dans un ordre brouillé.

L'espace auxiliaire requis pour l'algorithme de tri à bulles est O(1).

Implémentation en C++ de l'algorithme de tri à bulles

Vous trouverez ci-dessous l'implémentation C++ de l'algorithme Bubble Sort:

// Implémentation en C++ du
// algorithme de tri à bulles optimisé
#inclure 
en utilisant l'espace de noms std ;
// Fonction pour effectuer un tri à bulles
void bubbleSort (int arr[], int size) {
// Boucle pour accéder à chaque élément du tableau
pour (entier i=0; i// Variable pour vérifier si l'échange se produit
bool échangé = faux ;
// boucle pour comparer deux éléments adjacents du tableau
pour (int j = 0; j < (taille-i-1); j++) {
// Comparaison de deux éléments de tableau adjacents
si (arr[j] > arr[j + 1]) {
// Échange les deux éléments s'ils sont
// pas dans le bon ordre
int temp = arr[j];
arr[j] = arr[j + 1] ;
arr[j + 1] = temp;
échangé = vrai;
}
}
// Si aucun élément n'a été échangé, cela signifie que le tableau est trié maintenant,
// puis rompt la boucle.
if (permuté == faux) {
Pause;
}
}
}
// Imprime les éléments du tableau
void printArray (int arr[], int size) {
pour (entier i = 0; je < taille; i++) {
cout << arr[i] << " " ;
}
cout << endl;
}
int main() {
int arr[] = {16, 12, 15, 13, 19} ;
// Recherche de la longueur du tableau
int size = sizeof (arr) / sizeof (arr[0]);
// Impression du tableau non trié donné
cout << " Tableau non trié: " << endl;
printArray (arr, taille);
// Appel de la fonction bubbleSort()
bubbleSort (arr, taille);
// Impression du tableau trié
cout << "Tableau trié dans l'ordre croissant :" << endl;
printArray (arr, taille);
renvoie 0 ;
}

Production:

Tableau non trié: 
16 12 15 13 19 
Tableau trié par ordre croissant :
12 13 15 16 19

Implémentation Python de l'algorithme de tri à bulles

Vous trouverez ci-dessous l'implémentation Python de l'algorithme Bubble Sort:

# Implémentation Python du
# algorithme de tri à bulles optimisé
# Fonction pour effectuer le tri à bulles
def bubbleSort (arr, taille):
# Boucle pour accéder à chaque élément de la liste
pour i dans la gamme (taille-1) :
# Variable pour vérifier si l'échange se produit
échangé = Faux
# boucle pour comparer deux éléments adjacents de la liste
pour j dans la plage (taille-i-1) :
# Comparaison de deux éléments de liste adjacents
si arr[j] > arr[j+1] :
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
échangé = vrai
# Si aucun élément n'a été échangé, cela signifie que la liste est triée maintenant,
# puis rompre la boucle.
si permuté == Faux :
Pause
# Imprime les éléments de la liste
def printArray (arr):
pour l'élément dans arr :
print (élément, fin=" ")
imprimer("")
arr = [16, 12, 15, 13, 19]
# Trouver la longueur de la liste
taille = len (arr)
# Impression de la liste non triée donnée
print("Liste non triée :")
tableau d'impression (arr)
# Appel de la fonction bubbleSort()
bubbleSort (arr, taille)
# Impression de la liste triée
print("Liste triée par ordre croissant :")
tableau d'impression (arr)

Production:

Liste non triée :
16 12 15 13 19 
Liste triée par ordre croissant :
12 13 15 16 19

En rapport: Comment utiliser les boucles For en Python

C Implémentation de l'algorithme de tri à bulles

Vous trouverez ci-dessous l'implémentation en C de l'algorithme Bubble Sort:

// Implémentation en C du
// algorithme de tri à bulles optimisé
#inclure 
#inclure 
// Fonction pour effectuer un tri à bulles
void bubbleSort (int arr[], int size) {
// Boucle pour accéder à chaque élément du tableau
pour (entier i=0; i// Variable pour vérifier si l'échange se produit
bool échangé = faux ;
// boucle pour comparer deux éléments adjacents du tableau
pour (int j = 0; j < (taille-i-1); j++) {
// Comparaison de deux éléments de tableau adjacents
si (arr[j] > arr[j + 1]) {
// Échange les deux éléments s'ils sont
// pas dans le bon ordre
int temp = arr[j];
arr[j] = arr[j + 1] ;
arr[j + 1] = temp;
échangé = vrai;
}
}
// Si aucun élément n'a été échangé, cela signifie que le tableau est trié maintenant,
// puis rompt la boucle.
if (permuté == faux) {
Pause;
}
}
}
// Imprime les éléments du tableau
void printArray (int arr[], int size) {
pour (entier i = 0; je < taille; i++) {
printf("%d ", arr[i]);
}
printf(" \⁠n ");
}
int main() {
int arr[] = {16, 12, 15, 13, 19} ;
// Recherche de la longueur du tableau
int size = sizeof (arr) / sizeof (arr[0]);
// Impression du tableau non trié donné
printf("Tableau non trié: \⁠n");
printArray (arr, taille);
// Appel de la fonction bubbleSort()
bubbleSort (arr, taille);
// Impression du tableau trié
printf("Tableau trié par ordre croissant: \⁠n");
printArray (arr, taille);
renvoie 0 ;
}

Production:

Tableau non trié: 
16 12 15 13 19 
Tableau trié par ordre croissant: 
12 13 15 16 19

Implémentation JavaScript de l'algorithme de tri à bulles

Vous trouverez ci-dessous l'implémentation JavaScript de l'algorithme Bubble Sort:

// Implémentation JavaScript du
// algorithme de tri à bulles optimisé
// Fonction pour effectuer un tri à bulles
fonction bubbleSort (arr, taille) {
// Boucle pour accéder à chaque élément du tableau
pour (soit i=0; je// Variable pour vérifier si l'échange se produit
var permuté = faux ;
// boucle pour comparer deux éléments adjacents du tableau
pour (soit j=0; j// Comparaison de deux éléments de tableau adjacents
si (arr[j] > arr[j+1]) {
// Échange les deux éléments s'ils sont
// pas dans le bon ordre
laissez temp = arr[j];
arr[j] = arr[j+1] ;
arr[j+1] = temp;
échangé = vrai;
}
// Si aucun élément n'a été échangé, cela signifie que le tableau est trié maintenant,
// puis rompt la boucle.
if (permuté == faux) {
Pause;
}
}
}
}
// Imprime les éléments du tableau
function tableau_impression (tableau, taille) {
pour (soit i=0; jedocument.write (arr[i] + " ");
}
document.write("
")
}
var arr = [16, 12, 15, 13, 19];
// Recherche de la longueur du tableau
var taille = arr.longueur;
// Impression du tableau non trié donné
document.write("Tableau non trié: 
");
printArray (arr, taille);
// Appel de la fonction bubbleSort()
bubbleSort (arr, taille);
// Impression du tableau trié
document.write("Tableau trié par ordre croissant: 
");
printArray (arr, taille);

Production:

Tableau non trié :
16 12 15 13 19
Tableau trié par ordre croissant :
12 15 13 16 19

Vous comprenez maintenant le fonctionnement de l'algorithme de tri à bulles

Bubble Sort est l'algorithme de tri le plus simple et est principalement utilisé pour comprendre les fondements du tri. Le tri à bulles peut également être implémenté de manière récursive, mais cela n'offre aucun avantage supplémentaire.

En utilisant Python, vous pouvez facilement implémenter l'algorithme Bubble Sort. Si vous n'êtes pas familier avec Python et que vous souhaitez démarrer votre voyage, commencer par un script "Hello World" est un excellent choix.

Comment démarrer avec Python à l'aide d'un script "Hello World"

Python est l'un des langages de programmation les plus utilisés aujourd'hui. Suivez ce tutoriel pour commencer avec votre tout premier script Python.

Lire la suite

A propos de l'auteur