Le Tri par Insertion en C : Guide Complet

Dans cet article, nous allons explorer en détail comment implémenter le tri par insertion en C.

💡 Le tri par insertion est l’un des algorithmes de tri les plus simples et les plus intuitifs. Il consiste à parcourir un tableau d’éléments et à insérer chaque élément à sa place appropriée dans la partie triée du tableau. Bien que cet algorithme ne soit pas aussi efficace que certains autres, comme le tri rapide ou le tri fusion, il reste néanmoins intéressant à comprendre en raison de sa simplicité et de sa facilité de mise en œuvre.

Comprendre le Tri par Insertion

L’idée fondamentale du tri par insertion est de diviser le tableau en deux parties : une partie triée et une partie non triée. Au début, la partie triée est vide, tandis que la partie non triée contient tous les éléments du tableau. L’algorithme parcourt ensuite chaque élément de la partie non triée et l’insère à sa place correcte dans la partie triée. À chaque itération, la partie triée s’étend d’un élément supplémentaire, et la partie non triée diminue d’un élément. Ce processus se répète jusqu’à ce que tous les éléments soient triés.

Implémentation en C

Voici une implémentation simple du tri par insertion en langage C :

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /* Déplace les éléments du tableau arr[0..i-1], qui sont
           plus grands que la clé, vers une position en avant
           de leur position actuelle */        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Tableau trié : \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Dans cette implémentation, la fonction insertionSort trie le tableau passé en paramètre en utilisant le tri par insertion. La fonction main illustre son utilisation en triant un tableau d’entiers et en affichant le résultat trié.

Analyse de la Complexité

La complexité temporelle du tri par insertion dépend de la disposition initiale des éléments dans le tableau. Dans le pire des cas, lorsque le tableau est inversément trié, la complexité temporelle est quadratique, soit ( O(n^2) ). Cependant, dans le meilleur des cas, lorsque le tableau est déjà trié, la complexité temporelle est linéaire, soit ( O(n) ). En moyenne, le tri par insertion a une complexité temporelle de ( O(n^2) ).

La complexité spatiale du tri par insertion est linéaire, soit ( O(n) ), car elle nécessite un espace supplémentaire proportionnel à la taille du tableau pour stocker les éléments.

Voici quelques exemples pratiques illustrant l’utilisation du tri par insertion en C :

Exemple 1 : Tri de Nombres Entiers

Supposons que vous ayez un tableau d’entiers non trié et que vous vouliez le trier en utilisant le tri par insertion. Voici comment vous pourriez le faire en C :

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Tableau trié : \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Exemple 2 : Tri de Chaînes de Caractères

Supposons maintenant que vous ayez un tableau de chaînes de caractères et que vous souhaitiez les trier par ordre alphabétique en utilisant le tri par insertion :

#include <stdio.h>
#include <string.h>

void insertionSort(char *arr[], int n) {
    int i, j;
    char *key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && strcmp(arr[j], key) > 0) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    char *arr[] = {"orange", "apple", "banana", "grape", "kiwi"};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Tableau trié : \n");
    for (int i = 0; i < n; i++)
        printf("%s ", arr[i]);
    printf("\n");
    return 0;
}

Ces exemples montrent comment vous pouvez utiliser le tri par insertion en C pour trier différents types de données, qu’il s’agisse de nombres entiers, de chaînes de caractères ou même d’autres types de données personnalisés.

Voici une version révisée avec des exemples de code pour chaque cas particulier :

Cas Particulier 1 : Tableau Déjà Trié

Si le tableau est déjà trié ou presque trié, le tri par insertion offre de bonnes performances. Voici un exemple de code :

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Tableau trié : \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Cas Particulier 2 : Taille du Tableau

Le tri par insertion peut être inefficace pour les grands tableaux. Voici un exemple illustrant son utilisation avec un grand tableau :

// Supposons un tableau de 10000 éléments
int arr[10000];

// Initialisez et remplissez le tableau ici...

// Tri par insertion
insertionSort(arr, 10000);

Cas Particulier 3 : Éléments Dupliqués

Le tri par insertion conserve l’ordre relatif des éléments dupliqués. Voici un exemple :

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Tableau trié : \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Cas Particulier 4 : Espace Mémoire Supplémentaire

Le tri par insertion n’a pas besoin d’espace mémoire supplémentaire pour trier les éléments. Voici un exemple :

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    // Utilisation d'un tableau existant
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    // Le tri est effectué dans le tableau existant, pas de mémoire supplémentaire nécessaire
    return 0;
}

Cas Particulier 5 : Performance en Moyenne

Le tri par insertion peut être plus efficace dans certains cas que d’autres algorithmes de tri. Voici un exemple où il est utilisé pour trier un petit tableau presque trié :

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    // Tableau presque trié
    int arr[] = {2, 4, 3, 6, 5, 8, 7, 10, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Tableau trié : \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Ces exemples illustrent différentes situations où le tri par insertion peut être utilisé en fonction des caractéristiques des données et des exigences de performance.

Voici comment nous pourrions illustrer le bon code versus le mauvais code pour chaque erreur technique à éviter lors de l’implémentation du tri par insertion en C :

Erreur 1 : Mauvaise Initialisation des Variables

Mauvais Code :

int i, j; // Non initialisées

Bon Code :

int i = 0, j = 0; // Initialisées à zéro

Erreur 2 : Utilisation d’indices incorrects

Mauvais Code :

while (arr[j] > key && j >= 0) { // Utilisation de j avant de vérifier s'il est supérieur ou égal à zéro

Bon Code :

while (j >= 0 && arr[j] > key) { // Vérification de j avant son utilisation

Erreur 3 : Mauvaise Manipulation des Limites du Tableau

Mauvais Code :

for (i = 0; i <= n; i++) { // Utilisation de <= n au lieu de < n

Bon Code :

for (i = 0; i < n; i++) { // Utilisation de < n pour rester dans les limites du tableau

Erreur 4 : Mauvaise Logique de Boucle

Mauvais Code :

for (i = n - 1; i >= 0; i++) { // Utilisation incorrecte de l'opérateur d'incrémentation

Bon Code :

for (i = n - 1; i >= 0; i--) { // Utilisation correcte de l'opérateur de décrémentation

Erreur 5 : Comparaisons Incorrectes

Mauvais Code :

while (arr[j] < key) { // Comparaison incorrecte (utilisation de < au lieu de >)

Bon Code :

while (arr[j] > key) { // Comparaison correcte (éléments triés en ordre croissant)

Erreur 6 : Oubli de l’Instruction de Tri

Mauvais Code :

while (j >= 0 && arr[j] > key) {
    // Instructions manquantes pour déplacer les éléments
}

Bon Code :

while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j];
    j--;
}
arr[j + 1] = key; // Instruction de tri

Erreur 7 : Oubli de la Condition de Boucle

Mauvais Code :

while (true) {
    // Boucle infinie sans condition de sortie
}

Bon Code :

while (j >= 0 && arr[j] > key) {
    // Condition de sortie définie à l'intérieur de la boucle
}

En respectant ces bonnes pratiques de codage, vous pouvez éviter les erreurs techniques courantes et assurer que votre implémentation du tri par insertion en C fonctionne correctement et produit les résultats attendus.