Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Tri par sélection

Le tri par sélection est un des algorithmes de tri le plus trivial. Il consiste en la recherche soit du plus grand élément (ou le plus petit) que l'on va replacer à sa position finale c'est-à-dire en dernière position (ou en première), puis on recherche le second plus grand élement (ou le second plus petit) que l'on va replacer également à sa position finale c'est-à-dire en avant-dernière position (ou en seconde), etc., jusqu'à ce que le tableau soit entierement trié.

Il est plus efficace que le tri par insertion, pour trier des données où l'insertion ne se fait pas en temps constant (O(1)) et aussi efficace sinon. Mais, contrairement au tri par insertion, le nombre de comparaisons ne varie pas selon l'état d'ordre des données.(ie. même si les données sont presque triées le nombre de comparaison sera toujours du même ordre.).

Propriétés

1. Le nombre de comparaisons nécessaires pour un tri est de N(N-1)/2 (où N est la quantité de donnée à trier).
2. Le nombre d'échanges, lui, est de l'ordre de N.