Algorithme de tri à bulles en C, Java et Python

Informatec Digital » Algorithmes » Algorithme de tri à bulles en C, Java et Python

L'algorithme de tri à bulles est l'un des algorithmes les plus simples et les plus basiques utilisés pour trier les éléments d'une liste. Sa simplicité en fait un excellent choix pour comprendre les concepts fondamentaux des algorithmes de tri. Cet algorithme est couramment utilisé dans les applications et les programmes où le nombre d'éléments à trier est faible.

Dans cet article, nous nous concentrerons sur la mise en œuvre l'algorithme Tri à bulles dans deux langages de programmation populaires : C et Java. Nous explorerons les étapes nécessaires à la mise en œuvre de cet algorithme dans chacun de ces langages, en analysant le code source et en fournissant des explications détaillées.

Algorithme de tri à bulles en C et Java

L'algorithme de tri à bulles, comme son nom l'indique, fonctionne en comparant des paires d'éléments adjacents dans une liste et en effectuant des échanges s'ils ne sont pas dans le bon ordre. Ce processus est répété jusqu'à ce que la liste soit complètement triée.

Comment fonctionne l'algorithme de tri à bulles en C et Java ?

L'algorithme de tri à bulles suit une approche simple mais efficace pour trier les éléments. Le fonctionnement général de l'algorithme est présenté ci-dessous :

1. Nous commençons avec une liste non ordonnée d’éléments.
2. Nous parcourons la liste en comparant chaque paire d’éléments adjacents.
3. Si les éléments ne sont pas dans le bon ordre, nous les échangeons.
4. Nous continuons à parcourir la liste jusqu’à ce qu’elle soit complètement triée.
5. Le processus d'itération est répété autant de fois que nécessaire jusqu'à ce qu'aucun autre échange ne soit effectué lors d'un passage complet.

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

Ensuite, nous présentons l’implémentation de l’algorithme de tri à bulles dans le langue C:

#include <stdio.h>

void bubbleSort(int array[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

int main() {
    int array[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(array) / sizeof(array[0]);
    bubbleSort(array, size);
    printf("Array ordenado: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

Dans ce code d'algorithme à bulles, nous avons défini une fonction appelée bubbleSort qui prend un tableau et sa taille comme paramètres. La fonction exécute l'algorithme de tri à bulles à l'aide de deux boucles for. La première boucle for itère sur les éléments du tableau et la deuxième boucle for faire les comparaisons et les échanges nécessaires.

Enfin, dans la fonction main, nous avons créé un exemple de tableau et calculé sa taille. Ensuite, nous appelons la fonction bubbleSort en passant le tableau et sa taille comme arguments. Enfin, nous imprimons le tableau trié à l’écran.

Implémentation de l'algorithme de tri à bulles en Java

Ci-dessous, nous présentons l'implémentation de l'algorithme de tri à bulles dans le langage Java :

import java.util.Arrays;

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int size = array.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(array);
        System.out.println("Array ordenado: " + Arrays.toString(array));
    }
}

Dans ce code, nous avons défini une classe appelée BubbleSort. Dans cette classe, nous avons déclaré une méthode statique appelée bubbleSort qui prend un tableau comme paramètre. La méthode bubbleSort exécute l'algorithme de tri à bulles à l'aide de deux boucles for, tout comme dans l'implémentation C.

dans la méthode main, nous avons créé un exemple de tableau et appelé la méthode bubbleSort en passant le tableau comme argument. Enfin, nous utilisons Arrays.toString(array) pour imprimer le tableau trié sur la console.

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

L'équivalent de l'algorithme de tri à bulles Python :

def bubble_sort(array):
    size = len(array)
    for i in range(size - 1):
        for j in range(size - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(array)
print("Array ordenado:", array)

 

Avantages de l'algorithme de tri à bulles

L'algorithme de tri à bulles présente certains avantages, tels que :

1. Facilité:L'algorithme de tri à bulles est facile à comprendre et à mettre en œuvre. Il ne nécessite pas de connaissances compliquées et convient aux débutants en programmation.
2. Faible complexité du code:Le code requis pour implémenter l’algorithme de tri à bulles est relativement court et concis. Cela en fait une option rapide pour trier un petit nombre d’éléments.

Inconvénients de l'algorithme de tri à bulles

Malgré sa simplicité, l’algorithme de tri à bulles présente également quelques inconvénients :

1. Inefficacité dans les grands ensembles de données:L'algorithme de tri à bulles n'est pas efficace en termes de temps d'exécution lorsqu'il s'agit de grands ensembles de données. Sa complexité temporelle est O(n^2), ce qui signifie que le temps d’exécution augmente rapidement à mesure que la taille de l’ensemble de données augmente.
2. Nombre de comparaisons:L'algorithme de tri à bulles effectue un grand nombre de comparaisons, même lorsque le tableau est déjà trié. Cela peut entraîner une perte inutile de performances et de ressources.

Alternatives à l'algorithme de tri à bulles

À mesure que les ensembles de données deviennent plus volumineux et plus complexes, il est important d’envisager des alternatives plus efficaces à l’algorithme de tri à bulles. Certaines des alternatives populaires incluent :

1. Algorithme de tri par insertion:Cet algorithme divise la liste en une partie ordonnée et une partie non ordonnée, et insère chaque élément de la partie non ordonnée dans la position correcte dans la partie ordonnée. Il a une complexité temporelle de O(n^2) dans le pire des cas, mais est plus efficace que l'algorithme de tri à bulles dans la plupart des cas.
2. Algorithme de tri de sélection:Cet algorithme divise la liste en une partie ordonnée et une partie non ordonnée, et sélectionne à plusieurs reprises le plus petit élément de la partie non ordonnée et le place à la fin de la partie ordonnée. Il a une complexité temporelle de O(n^2) dans le pire des cas, mais est également plus efficace que l'algorithme de tri à bulles dans la plupart des cas.

FAQ sur l'algorithme Bubble

1. Quelle est la complexité temporelle de l’algorithme de tri à bulles ?

L'algorithme de tri à bulles a une complexité temporelle de O(n^2), où « n » est le nombre d'éléments à trier. Cela signifie que le temps d’exécution de l’algorithme augmente de manière quadratique à mesure que la taille de la liste augmente.

2. Quand est-il approprié d’utiliser l’algorithme de tri à bulles ?

L'algorithme de tri à bulles est adapté lorsque la liste des éléments à trier est petite. En raison de sa complexité temporelle, son utilisation sur de grands ensembles de données n'est pas recommandée, car des algorithmes plus efficaces sont disponibles.

3. L’algorithme de tri à bulles est-il stable ?

Oui, l’algorithme de tri à bulles est un algorithme de tri stable. Cela signifie qu'il maintient l'ordre relatif des éléments avec des clés égales pendant le processus de tri.

4. Quelle est la meilleure alternative à l’algorithme de tri à bulles ?

Le choix de la meilleure alternative à l’algorithme de tri à bulles dépend du contexte et des exigences spécifiques du problème. Cependant, certains algorithmes plus efficaces, tels que l'algorithme de tri rapide et l'algorithme de tri par fusion (tri par fusion), sont largement utilisés en raison de leur moindre complexité temporelle.

5. L’algorithme de tri à bulles peut-il être amélioré ?

Oui, il existe des variantes et des optimisations de l’algorithme de tri à bulles, telles que le « tri à bulles bidirectionnel » et le « tri à bulles amélioré ». Ces optimisations réduisent le nombre de comparaisons et le nombre d'itérations nécessaires pour trier une liste.

6. Où puis-je trouver plus d’informations sur les algorithmes de tri ?

Vous pouvez trouver plus d’informations sur les algorithmes de tri dans des sources fiables telles que Wikipédia. Voici quelques liens utiles :

• Algorithmes de tri sur Wikipédia
• Tri à bulles sur Wikipédia

Conclusion

Dans cet article, nous avons exploré l'algorithme de tri à bulles dans les langages de programmation C et Java. Nous avons appris étape par étape comment fonctionne cet algorithme et nous avons vu sa mise en œuvre pratique dans les deux langages. Nous avons également discuté des avantages et des inconvénients de l’algorithme de tri à bulles et exploré des alternatives plus efficaces.

Bien que l’algorithme de tri à bulles soit simple et facile à mettre en œuvre, il est important de considérer son efficacité sur des ensembles de données plus volumineux. Dans de tels cas, il est conseillé d’envisager des algorithmes de tri plus efficaces, tels que le tri par insertion ou le tri par sélection.

Nous espérons que cet article vous a donné une solide compréhension de l’algorithme de tri à bulles.