Tri par base

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 trie selon un ordre lexical.

Le temps d'exécution est O(nk) où n est le nombre d'objets et k la taille moyenne des clefs. Cet algorithme était utilisé pour trier des cartes perforées en plusieurs passages.

Le tri par base a été réutilisé comme une alternative à des algorithmes de tri plus puissants (comme les tris rapides, par tas et par fusion) qui demandent O(n log n) comparaisons où n est le nombre d'objets à trier. Ces algorithmes sont plus efficaces pour trier des données selon un ordre qui n'est pas lexical, mais c'est de peu d'importance pour les applications pratiques.

Si la taille de l'espace possible de clefs est proportionnel au nombre d'éléments, alors chaque clef aura une taille de log n caractères et le tri par base s'effectuera en un temps O(n log n) dans ce cas.

En pratique, si les clefs utilisées sont de petits entiers, le tri peut être réalisé en deux temps, les comparaisons peuvent alors être faites avec quelques opérations qui opèrent en un temps constant. Dans ce cas, le tri par base s'exécutera en O(n) et en pratique il s'avérera plus rapide que d'autres algorithmes de tri.

Le plus grand désavantage du tri par base est qu'il nécessite O(n) espace mémoire supplémentaire et il requiert une analyse de chaque caractère des clefs de la liste d'entrée, il peut donc être très lent pour des clefs longues.

L'ordre de tri est typiquement le suivant : les clefs courtes viennent avant les clefs longues, les clefs de même taille sont triées selon un ordre lexical. Cette méthode correspond à l'ordre naturel des nombres s'ils sont représentés par des chaînes de chiffres.

Son mode opératoire est :

  1. prend le chiffre (ou groupe de bits) le moins significatif de chaque clef,
  2. trie la liste des éléments selon ce chiffre, mais conserve l'ordre des éléments ayant le même chiffre (ce qui est un tri stable).
  3. répète le tri avec chaque chiffre plus significatif.

Exemple

Trier la liste : 170, 45, 75, 90, 2, 24, 802, 66

  1. tri par le chiffre le moins significatif (unités) :

170, 90, 2, 802, 24, 45, 75, 66

  1. tri par le chiffre suivant (dizaines) :

2, 802, 24, 45, 66, 170, 75, 90

  1. tri par le chiffre le plus significatif (centaines) :

2, 24, 45, 66, 75, 90, 170, 802

Lien externe


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 base de Wikipédia en français (auteurs)

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

Regardez d'autres dictionnaires:

  • 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 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´tite|ly — tri|par|tite «try PAHR tyt», adjective. 1. divided into or composed of three parts; threefold; triple. 2. involving division into three parts. 3. Botany. divided into three parts nearly to the base: »a tripartite leaf. 4. having three… …   Useful english dictionary

  • tri|par|tite — «try PAHR tyt», adjective. 1. divided into or composed of three parts; threefold; triple. 2. involving division into three parts. 3. Botany. divided into three parts nearly to the base: »a tripartite leaf. 4. having three corresponding parts or… …   Useful english dictionary

  • 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 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 cartes — Le tri par cartes[1] est une méthode utilisée en ergonomie informatique (voir aussi Conception centrée sur l utilisateur) où un groupe de participants experts ou utilisateurs d un produit de type logiciel ou site web, est accompagné dans la… …   Wikipédia en Français

  • 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 1… …   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 radix — 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… …   Wikipédia en Français

Share the article and excerpts

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