Tri par sélection

Tri par sélection

Le tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Il est particulièrement simple, mais inefficace sur de grandes entrées, car il s'exécute en temps quadratique en le nombre d'éléments à trier.

Sommaire

Description

Animation représentant le tri par sélection

Sur un tableau de n éléments (numérotés de 1 à n), le principe du tri par sélection est le suivant :

  • rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ;
  • rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 2 ;
  • continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.

En pseudo-code, l'algorithme s'écrit ainsi :

  procédure tri_selection(tableau t, entier n)
      pour i de 1 à n - 1
          min ← i
          pour j de i + 1 à n - 1
              si t[j] < t[min], alors min ← j
          si min ≠ i, alors échanger t[i] et t[min]

L'invariant de boucle suivant permet de prouver la correction de l'algorithme : à la fin de l'étape i, le tableau est une permutation du tableau initial et les i premiers éléments du tableau coïncident avec les i premiers éléments du tableau trié.

Une variante consiste à procéder de façon symétrique, en plaçant d'abord le plus grand élément à la fin, puis le second plus grand élément en avant-dernière position, etc.

Le tri par sélection peut aussi être utilisé sur des listes. Le principe est identique, mais au lieu de déplacer les éléments par échanges, on réalise des suppressions et insertions dans la liste.

Propriétés

Appliqué à un tableau, le tri par sélection est un tri sur place (les éléments sont triés dans la structure) mais n'est pas un tri stable (l'ordre d'apparition des éléments égaux n'est pas préservé).

Appliqué à une liste, le tri par sélection est stable à condition de déplacer la première occurrence du plus petit élément à chaque étape.

Complexité

Dans tous les cas, pour trier n éléments, le tri par sélection effectue n(n-1)/2 comparaisons. Sa complexité est donc Θ(n2). De ce point de vue, il est inefficace puisque les meilleurs algorithmes[1] s'exécutent en temps O(n\,\log n). Il est même moins bon que le tri par insertion ou le tri à bulles, qui sont aussi quadratiques dans le pire cas mais peuvent être plus rapides sur certaines entrées particulières.

Par contre, le tri par sélection n'effectue que peu d'échanges :

  • n-1 échanges dans le pire cas, qui est atteint par exemple lorsqu'on trie la séquence 2,3,…,n,1 ;
  • n - (1/2+\dots+1/n) \simeq n - \ln n en moyenne[2], c'est-à-dire si les éléments sont deux à deux distincts et que toutes leurs permutations sont équiprobables (en effet, l'espérance du nombre d'échanges à l'étape i est (n − i) / (n − i + 1)) ;
  • aucun si l'entrée est déjà triée.

Ce tri est donc intéressant lorsque les éléments sont aisément comparables, mais coûteux à déplacer dans la structure.

Voir aussi

Références

  1. ↑ Voir par exemple tri fusion, tri rapide et tri par tas
  2. ↑ (en) Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley 1973, (ISBN 978-0-201-03803-3) (section 5.2.3, p. 157, exercice 4)
v · Algorithmes de tri

à bulle • par sélection • par insertion • par tas • par base • par paquets • rapide • smoothsort • fusion • comptage • de Shell

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Tri par sélection de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Tri par selection — Tri par sélection Le tri par sélection (ou tri par extraction) est un des algorithmes de tri les plus triviaux. 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… …   Wikipédia en Français

  • Tri par dénombrement — Tri comptage Le tri comptage (appelé aussi tri casier) est un algorithme de tri qui s applique sur des valeurs entières. Sommaire 1 Définition 2 Exemple 3 Algorithme 4 Implémentation …   Wikipédia en Français

  • Tri par insertion — Exemple du tri par insertion utilisant une liste de nombres aléatoires Le tri par insertion est un algorithme de tri classique dont le principe est très simple. C est le tri que la plupart des personnes utilisent naturellement pour trier des… …   Wikipédia en Français

  • Tri par base — Le tri par base (ou tri radix) est, en informatique, un algorithme de tri rapide et stable qui peut être utilisé pour ordonner des éléments identifiés par une clef unique. Chaque clef est une chaîne de caractères ou un nombre que le tri par base… …   Wikipédia en Français

  • Tri par tas — Une exécution de l algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l …   Wikipédia en Français

  • Tri par paquets — Le tri par paquets est un algorithme de tri qui fonctionne sur des nombres réels appartenant à un intervalle borné fixé à l avance. Le principe de ce tri consiste à diviser l intervalle d entrée en petits sous intervalles identiques et à répartir …   Wikipédia en Français

  • Tri rapide — Le tri rapide (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961[1] et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes.… …   Wikipédia en Français

  • Tri stable — Algorithme de tri Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d organiser une collection d objets selon un ordre déterminé. Les objets à trier font donc partie d un ensemble muni d une relation d ordre… …   Wikipédia en Français

  • Selection naturelle — Sélection naturelle Les mécanismes de l évolution biologique Mécanismes non aléatoires: sélection naturelle sélection utilitaire sélection sexuelle sélection de parentèle sélection de groupe s …   Wikipédia en Français

  • Séléction naturelle — Sélection naturelle Les mécanismes de l évolution biologique Mécanismes non aléatoires: sélection naturelle sélection utilitaire sélection sexuelle sélection de parentèle sélection de groupe s …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”