Tri par tas

1. Algorithme de tri par tas
2. Exemple de tri du tas
3. Implémentation d’algorithme de tri de tas
4. Complexité de l’algorithme de tri par tas

Le tri par tas est un algorithme de tri basé sur la comparaison. Il tire son nom de la structure de données du tas utilisée dans l’algorithme. Le tas est une structure de données spéciale basée sur un arbre binaire. Il possède les deux propriétés suivantes :

• C’est un arbre binaire complet avec tous les niveaux remplis sauf le dernier. Le dernier peut être partiellement rempli, mais tous les nœuds sont aussi loin que possible à gauche.
• Tous les nœuds parents sont plus petits/plus grands que leurs deux nœuds enfants. S’ils sont plus petits, le tas est appelé min-heap, et s’ils sont plus grands, alors le tas est appelé max-heap. Pour un indice donné i, le parent est donné par (i-1)/2, l’enfant gauche est donné par (2*i+1) et l’enfant droit est donné par (2*i+2).

Le tri par tas fonctionne d’une manière assez similaire au tri par sélection. Il sélectionne l’élément maximum du tableau en utilisant max-heap et le met à sa place à l’arrière du tableau. Il utilise une procédure appelée heapify() pour construire le tas.

Algorithme de tri par tas

Supposons que nous ayons un tableau non trié A[] contenant n éléments.

HeapSort()

Heapify()

Exemple de tri du tas

Supposons que nous ayons le tableau : (5, 3, 4, 2, 1, 6). Nous allons le trier en utilisant l’algorithme de tri par tas.

Après avoir construit le tas, nous obtenons le tableau comme : (6 3 5 2 1 4).

• Première itération :

• Deuxième tour :

• Troisième tour :

• Quatrième itération :

• Cinquième itération :

• Sixième tour :

Nous obtenons le tableau trié comme : (1,2,3,4,5,6)

Implémentation d’algorithme de tri de tas

#include <bits/stdc++.h>
using namespace std;

void heapify(int arr[], int n, int i) {
  int parent = i;
  int leftChild = 2 * i + 1;
  int rightChild = 2 * i + 2;

  if (leftChild < n && arr[leftChild] > arr[parent]) parent = leftChild;

  if (rightChild < n && arr[rightChild] > arr[parent]) parent = rightChild;

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

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);
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  heapSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complexité de l’algorithme de tri par tas

Complexité temporelle

• Cas moyen

La hauteur d’un arbre binaire complet avec des éléments n est au maximum logn. Ainsi, la fonction heapify() peut avoir un maximum de comparaisons logn lorsqu’un élément se déplace de la racine à la feuille. La fonction build heap est appelée pour n/2 éléments, ce qui rend la complexité temporelle totale pour la première étape n/2*logn ou T(n) = nlogn.

HeapSort() prend le pire temps de log pour chaque élément, et n éléments rendent sa complexité temporelle également nlogn. La complexité temporelle pour la construction du tas et le tri du tas est ajoutée et nous donne la complexité résultante en tant que nlogn. Ainsi, la complexité temporelle totale est de l’ordre de [Big Theta] : O(nlogn).

• Pire cas

La complexité temporelle dans le pire des cas est [Big O] : O(nlogn).

• Meilleur cas

Le meilleur exemple de complexité temporelle est [Big Omega] : O(nlogn). C’est la même chose que la complexité temporelle dans le pire des cas.

Complexité spatiale

La complexité spatiale de l’algorithme de tri par tas est O(1) car aucune mémoire supplémentaire autre que des variables temporaires n’est nécessaire.