Maîtriser le tri par insertion avec des tableaux dynamiques

Introduction

Dans ce laboratoire, nous allons apprendre à implémenter l'algorithme de tri par insertion à l'aide de tableaux dynamiques en C++. Cet algorithme est un algorithme de tri simple qui fonctionne en divisant la liste en deux parties, triées et non triées, puis en insérant chaque élément de la liste non triée dans la liste triée à la bonne position.

Création d'un tableau dynamique

Tout d'abord, nous devons créer un tableau dynamique d'entiers dont la taille est déterminée par l'utilisateur, et le remplir avec des entiers aléatoires compris entre 1 et 100.

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int *arr;
    int size, i;

    cout << "Entrez la taille du tableau : ";
    cin >> size;

    // créer le tableau dynamique
    arr = new int[size];

    // remplir le tableau avec des entiers aléatoires compris entre 1 et 100
    for(i=0; i<size; i++) {
        arr[i] = rand() % 100 + 1;
    }

Affichage du tableau non trié

Ensuite, nous allons afficher le contenu du tableau non trié à l'utilisateur.

    // afficher le tableau non trié
    cout << "Tableau non trié : ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

Implémentation de l'algorithme de tri par insertion

Maintenant, nous allons implémenter l'algorithme de tri par insertion, qui triera le tableau par ordre croissant.

    // tri par insertion
    int j, temp;
    for(i=1; i<size; i++) {
        temp = arr[i];
        j = i - 1;
        while(j>=0 && arr[j]>temp) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }

Affichage du tableau trié

Nous allons afficher le contenu du tableau trié à l'utilisateur.

    // afficher le tableau trié
    cout << "Tableau trié : ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

Libération de la mémoire

Enfin, nous allons libérer la mémoire utilisée par le tableau dynamique.

    // libérer la mémoire
    delete [] arr;

    return 0;
}

Compiler et exécuter le programme

Enregistrez le fichier sous le nom "sort.cpp" dans le répertoire ~/project.

Compilez et exécutez le programme dans le terminal :

$ cd ~/project
$ g++ sort.cpp -o sort
$./sort

Résumé

Dans ce laboratoire, nous avons appris à implémenter l'algorithme de tri par insertion à l'aide de tableaux dynamiques en C++. Nous avons créé un tableau dynamique dont la taille est déterminée par l'utilisateur, l'avons rempli avec des entiers aléatoires, avons implémenté l'algorithme de tri par insertion et finalement affiché le tableau trié à l'utilisateur. Nous avons également appris à libérer la mémoire utilisée par le tableau dynamique.

Tri par insertion avec tableau dynamique