Édition pédagogique en français

Tri à bulles en C

Échangez les voisins mal ordonnés et observez le maximum avancer vers la fin.

À chaque passage, comparez les éléments adjacents et échangez-les si nécessaire. Le plus grand de la partie restante arrive à la fin ; le passage suivant peut donc être plus court.

Un indicateur permet d’arrêter si aucun échange n’a eu lieu. Avec cette optimisation, une entrée déjà triée coûte O(N), mais les cas général et défavorable restent en O(N²). L’espace auxiliaire est O(1).

N’utilisez pas arr[j + 1] quand j est déjà le dernier indice. Testez doublons et ordre inverse. Échanger seulement si la gauche est strictement supérieure conserve l’ordre des valeurs égales.

Code source

#include <stdio.h>
#include <stdbool.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; // Array is already sorted
    }
}

void print_array(const int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void) {
    int data[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(data) / sizeof(data[0]);

    printf("Original array: ");
    print_array(data, n);

    bubble_sort(data, n);

    printf("Sorted array:   ");
    print_array(data, n);
    return 0;
}

Ouvrir dans le compilateur

Résultat attendu

Original array: 64 34 25 12 22 11 90 
Sorted array:   11 12 22 25 34 64 90

Questions fréquentes

Pourquoi le code et certains résultats restent-ils en anglais ?

Les mots-clés C, les identifiants, les commentaires du programme et les sorties attendues restent ceux de la version originale pour conserver un code exécutable et des tests cohérents. Les explications et les consignes sont traduites.