Tri binaire

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

Le tri binaire est un algorithme de tri par comparaison de types. Il s’agit d’une modification de l’algorithme de tri par insertion (/fr/tutorial/algorithm/insertion-sort/). Dans cet algorithme, nous maintenons également un sous-tableau trié et un sous-tableau non trié. La seule différence est que nous trouvons la position correcte d’un élément en utilisant la recherche binaire au lieu de la recherche linéaire. Cela permet de fixer l’algorithme de tri en réduisant le nombre de comparaisons nécessaires.

Algorithme de tri binaire

Supposons que nous ayons un tableau non trié A[] contenant n éléments. Le premier élément, A[0], est déjà trié et se trouve dans le sous-tableau trié.

Exemple de tri binaire

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

• Premier tour

Clé : A[1] = 3

Recherche binaire : renvoie la position de 3 comme index 0. Décalage à droite du reste des éléments dans le tableau trié.

• Deuxième tour

Clé : A[2] = 4

Recherche binaire : renvoie la position de 4 comme index 1. Décalage à droite du reste des éléments dans le tableau trié.

• Troisième tour

Clé : A[3] = 2

Recherche binaire : renvoie la position de 2 comme index 0. Décalage à droite du reste des éléments dans le tableau trié.

• Quatrième tour

Clé : A[4] = 1

Recherche binaire : renvoie la position de 1 comme index 0. Décalage à droite du reste des éléments dans le tableau trié.

• Cinquième tour

Clé : A[5] = 6

Recherche binaire : renvoie la position de 6 comme index 5. Il n’y a pas d’éléments sur la droite.

Nous obtenons le tableau trié après la quatrième itération - (1 2 3 4 5 6).

Implémentation d’algorithme de tri binaire

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

int binarySearch(int a[], int x, int low, int high) {
  if (high <= low) return (x > a[low]) ? (low + 1) : low;

  int mid = (low + high) / 2;

  if (x == a[mid]) return mid + 1;

  if (x > a[mid]) return binarySearch(a, x, mid + 1, high);
  return binarySearch(a, x, low, mid - 1);
}

void binarySort(int a[], int n) {
  for (int i = 1; i < n; ++i) {
    int j = i - 1;
    int key = a[i];
    int pos = binarySearch(a, key, 0, j);
    while (j >= pos) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}

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

Complexité de l’algorithme de tri binaire

Complexité temporelle

• Cas moyen

La recherche binaire a une complexité logarithmique logn par rapport à la complexité linéaire n de la recherche linéaire utilisée dans le tri par insertion. Nous utilisons le tri binaire pour les éléments n, ce qui nous donne la complexité temporelle nlogn. Ainsi, la complexité temporelle est de l’ordre de [Big Theta] : O(nlogn).

• Pire cas

Le cas le plus défavorable se produit lorsque le tableau est trié à l’envers, et que le nombre maximum d’équipes est nécessaire. La complexité temporelle du pire cas est [Big O] : O(nlogn).

• Meilleur cas

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

Complexité spatiale

La complexité spatiale de l’algorithme de tri binaire est O(n) car aucune mémoire supplémentaire autre qu’une variable temporaire n’est nécessaire.