Tri à bulles en C

Le tri est un concept nécessaire que nous devons apprendre dans n'importe quel langage de programmation. La plupart du temps, le tri est effectué sur des tableaux impliquant des nombres et constitue un tremplin pour maîtriser l'art des techniques permettant de parcourir et d'accéder aux données des tableaux.
Le type de technique de tri dont nous allons parler dans l'article d'aujourd'hui sera le Bubble Sort.

Tri à bulles

Le tri par bulles est un algorithme de tri simple qui fonctionne en échangeant à plusieurs reprises les éléments adjacents s'ils sont dans le mauvais ordre. Cette méthode de tri d'un tableau ne convient pas aux grands ensembles de données car la complexité temporelle des scénarios moyens et pires est très élevée.

Algorithme de tri à bulles :

1. Bubble Sort organise un tableau en le triant en plusieurs passes.
2. Premier passage : le plus grand élément se déplace vers la dernière position, sa place correcte.
3. Deuxième passe : le deuxième plus grand élément se déplace vers l'avant-dernière position, et cela continue pour les passes suivantes.
4. À chaque passage, seule la partie non triée du tableau est traitée.
5. Après k passes, les k éléments les plus grands sont dans leurs positions correctes dans les k derniers emplacements.
6. Lors de chaque passage :
   • Comparez les éléments adjacents dans la section non triée.
   • Échangez les éléments si le plus grand apparaît avant le plus petit.
   • À la fin du passage, le plus gros élément non trié se déplace vers sa position correcte. Ce processus se répète jusqu'à ce que l'ensemble du tableau soit trié.

Comment fonctionne le tri à bulles ?

Ci-dessous, la mise en œuvre du tri à bulles. Il peut être optimisé en arrêtant l'algorithme si la boucle interne n'a provoqué aucun échange.

// Easy implementation of Bubble sort
#include <stdio.h>
int main(){
    int i, j, size, temp, count=0, a[100];
    //Asking the user for size of array
    printf("Enter the size of array you want to enter = \t");
    scanf("%d", &size);
    //taking the input array through loop
    for (i=0;i<size;i++){
        printf("Enter the %dth element",i);
        scanf("%d",&a[i]);
    }
    //printing the unsorted list
    printf("The list you entered is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    //sorting the list
    for (i = 0; i < size - 1; i++) {
        count = 1;
        for (j = 0; j < size - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                //swapping elements
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                count = 1;
            }
        }

        // If no two elements were swapped by inner loop,
        // then break
        if (count == 1)
            break;
    }
    // printing the sorted list
    printf("\nThe sorted list is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    return 0;

}

Sortir :

**

Analyse de complexité du tri à bulles :

Complexité temporelle : O(n2)
Espace auxiliaire : O(1)

Avantages du tri à bulles :

• Le tri à bulles est facile à comprendre et à mettre en œuvre.
• Il ne nécessite aucun espace mémoire supplémentaire.
• Il s'agit d'un algorithme de tri stable, ce qui signifie que les éléments avec la même valeur clé conservent leur ordre relatif dans la sortie triée.

Inconvénients du tri à bulles :

• Le tri à bulles a une complexité temporelle de O(n2), ce qui le rend très lent pour les grands ensembles de données.
• Le tri à bulles est un algorithme de tri basé sur la comparaison, ce qui signifie qu'il nécessite un opérateur de comparaison pour déterminer l'ordre relatif des éléments dans l'ensemble de données d'entrée. Cela peut limiter l'efficacité de l'algorithme dans certains cas.

Commentez si vous avez des questions !!
Et toutes les discussions seront appréciées :)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!