Tri d'un tableau numérique

De nombreux algorithmes ont été proposés et étudiés pour résoudre le problème du tri, qui se présente fréquemment dans les problèmes de gestion de données : par exemple, on dispose d'un annuaire alphabétique des abonnés au téléphone, et on veut produire un annuaire classé par adresses. On présentera seulement deux algorithmes : le tri par insertion, de type incrémental, et plus loin le tri rapide, de type << diviser pour régner >>.

Le tri par insertion procède de façon incrémentale, à la manière d'un joueur de carte qui range les cartes, au fur et à mesure qu'il les reçoit, à leur place parmi les précédentes.

void tri_insertion(int n, int t[]) {
  int j;

  for (j=1; j<n; j++) {
    int x = t[j];
    int i = j-1;

    // x doit être inséré dans le tableau ordonné 0..j-1
    while (i>=0 && t[i]>x) {
      t[i+1] = t[i];
      i = i-1;
    }
    t[i+1] = x;
  }
}

La complexité de cet algorithme est en $\Theta(n^2)$. S'il est facilement utilisable pour des tableaux de taille réduite ($\le 100$), cette complexité est prohibitive pour une utilisation sur de grandes bases de données.