Timsort

1. Algorithme de Timsort
2. Exemple de Timsort
3. Implémentation de l’algorithme Timsort
4. Complexité de l’algorithme de tri temporel

Tim sort est un algorithme de tri hybride stable. Il s’agit d’un algorithme hybride dérivé du tri par insertion et du tri par fusion. Il utilise d’abord des sous-réseaux utilisant le tri par insertion ; ces petits sous-réseaux triés sont appelés natural runs. Ces passages sont ensuite fusionnés en utilisant le tri par fusion pour produire des tableaux triés finaux. Il a été conçu en tenant compte des performances optimales de l’algorithme sur des données réelles. Il utilise le fait que le tri par insertion fonctionne très bien sur des sous-réseaux de petite taille. Il s’agit de l’algorithme de tri standard utilisé par Array.sort() de Java et sorted() et sort() de Python.

Algorithme de Timsort

Supposons que nous ayons un tableau non trié A[] contenant n éléments. Nous considérerons que la taille de l’exécution est de 32. Il peut s’agir de n’importe quelle puissance de 2 car la fusion est plus efficace lorsque les nombres sont de puissances de 2.

TimSort()

Merge()

Exemple de Timsort

Supposons que nous ayons le tableau : (3, 5, 2, 8, 1, 7, 6, 4). Nous allons le trier en utilisant l’algorithme de tri de Tim. Pour simplifier l’illustration, considérons que la taille de l’exécution est de 4.

Divisez le tableau en deux sous-tableaux : (3, 5, 2, 8) et (1, 7, 6, 4).

Le premier sous-tableau : (3, 5, 2, 8)

• Premier tour

Clé : A[1] = 5

• Deuxième tour

Clé : A[2] = 4

• Troisième tour

Clé : A[3] = 2

Le deuxième sous-réseau : (1,7,6,4).

• Premier tour

Clé : A[1] = 7

• Deuxième tour

Clé : A[2] = 6

• Troisième tour

Clé : A[3] = 4

Fusionner les deux sous-réseaux triés pour obtenir le sous-réseau final en tant que : (1, 2, 3, 4, 5, 6, 7, 8)

Implémentation de l’algorithme Timsort

#include <bits/stdc++.h>
using namespace std;
const int RUN = 32;

void insertionSort(int arr[], int left, int right) {
  for (int i = left + 1; i <= right; i++) {
    int temp = arr[i];
    int j = i - 1;
    while (j >= left && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
}

void merge(int arr[], int beg, int mid, int end) {
  int output[end - beg + 1];
  int i = beg, j = mid + 1, k = 0;
  // add smaller of both elements to the output
  while (i <= mid && j <= end) {
    if (arr[i] <= arr[j]) {
      output[k] = arr[i];
      k += 1;
      i += 1;
    } else {
      output[k] = arr[j];
      k += 1;
      j += 1;
    }
  }
  // remaining elements from first array
  while (i <= mid) {
    output[k] = arr[i];
    k += 1;
    i += 1;
  }
  // remaining elements from the second array
  while (j <= end) {
    output[k] = arr[j];
    k += 1;
    j += 1;
  }
  // copy output to the original array
  for (i = beg; i <= end; i += 1) {
    arr[i] = output[i - beg];
  }
}
void timSort(int arr[], int n) {
  for (int i = 0; i < n; i += RUN)
    insertionSort(arr, i, min((i + 31), (n - 1)));

  for (int size = RUN; size < n; size = 2 * size) {
    for (int left = 0; left < n; left += 2 * size) {
      int mid = left + size - 1;
      int right = min((left + 2 * size - 1), (n - 1));

      merge(arr, left, mid, right);
    }
  }
}

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";
  timSort(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 temporel

Complexité temporelle

• Cas moyen

L’algorithme nécessite des comparaisons O(nlogn) pour trier un tableau de n éléments. Par conséquent, la complexité temporelle est de l’ordre de [Big Theta] : O(nlogn).

• Pire cas

Dans le pire des cas, des comparaisons nlogn sont nécessaires. La complexité temporelle dans le pire des cas est [Big O] : O(nlogn). C’est la même chose que la complexité temporelle moyenne.

• Meilleur cas

Dans le meilleur des cas, le tableau est déjà trié et aucun échange n’est nécessaire. Le meilleur cas de complexité temporelle est [Big Omega] : O(n).

Complexité spatiale

La complexité de l’espace pour cet algorithme est O(n) parce que l’espace auxiliaire supplémentaire de O(n) est requis par l’algorithme de tri par fusion.