Algorithme de tri par tas (Heap Sort) en C++ | Tableaux dynamiques

Introduction

Dans ce laboratoire, vous allez apprendre à implémenter l'algorithme de tri par tas (heap sort) à l'aide de tableaux dynamiques en C++. Le tri par tas est un algorithme de tri basé sur des comparaisons qui fonctionne en divisant l'entrée en une région triée et une région non triée, puis en réduisant itérativement la région non triée en extrayant l'élément le plus grand ou le plus petit et en le déplaçant dans la région triée.

Création du tableau dynamique

Nous allons créer un nouveau fichier nommé main.cpp dans le répertoire ~/project en utilisant la commande suivante :

touch ~/project/main.cpp

Tout d'abord, nous allons créer un tableau dynamique pour stocker les éléments. Nous allons utiliser l'opérateur new pour allouer dynamiquement de la mémoire pendant l'exécution du programme.

int* arr;
arr = new int[size];

Fonction de transformation en tas

Ensuite, nous allons créer la fonction heapify() pour réordonner les éléments dans le tableau. Le but de la fonction heapify() est de maintenir la propriété du tas, ce qui signifie que chaque nœud est supérieur ou égal à ses enfants.

void heapify(int* arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest!= i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

Fonction de tri par tas

Après avoir implémenté la fonction heapify(), nous allons créer la fonction heapSort() pour trier le tableau par ordre croissant.

void heapSort(int* arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Fonction principale

Enfin, nous allons créer la fonction main() pour lire les éléments saisis par l'utilisateur et afficher le tableau trié à l'aide de l'algorithme de tri par tas (heap sort).

int main() {
    int size;
    cout << "Entrez le nombre d'éléments : ";
    cin >> size;

    int* arr;
    arr = new int[size];

    cout << "Entrez les éléments : ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }

    heapSort(arr, size);

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

    delete[] arr;
    return 0;
}

Résumé

Dans ce laboratoire, vous avez appris à implémenter l'algorithme de tri par tas (Heap Sort) à l'aide de tableaux dynamiques en C++. Vous avez également appris à créer un tableau dynamique, à transformer le tableau en tas et à trier le tableau pour afficher le tableau trié par ordre croissant. Suivez les instructions pour exécuter le code d'exemple et pratiquer l'implémentation de l'algorithme de tri par tas (Heap Sort).

Tri par tas (Heap Sort) utilisant un tableau dynamique