Tri d'un tableau

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 trois algorithmes : le tri par insertion, de type incrémental, puis le tri par fusion et le tri rapide, tous deux 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.

  static void triInsertion(int[] t) {
    for (int j=1; j<t.length; 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.