next up previous contents index
suivant: Tableaux pluridimensionnels monter: main précédent: Tableaux de taille inconnue   Table des matières   Index


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.



R Lalement