précédent | suivant | table des matières

Le schéma des algorithmes de tri par comparaisons.

Les algorithmes de tri par comparaisons ont tous le même schéma qui procède du principe "diviser pour régner" :

void trier(ensemble  E){
   if( nbElements(E) > 1){
       diviser(E, E1, E2);
       trier(E1); trier(E2);
       recombiner(E1, E2, E);
   }
}

Si la complexité des opérations diviser et recombiner est dans l'ordre de n, et que les deux parties E₁ et E₂ sont de tailles égales, la complexité de la procédure trier est dans l'ordre de .

Dans les algorithmes que nous allons étudier, l'accent est mis soit sur l'opération de division, et dans ce cas l'opération recombiner est réduite à néant, soit sur l'opération recombiner, et c'est l'opération diviser qui est inexistante ou presque.

Les premiers algorithmes sont les algorithmes de tri par partition, les seconds sont les algorithmes de tri par fusion.