Tri radix

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 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'effectura 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 faite 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


Ce document provient de « Tri par base ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • 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

  • 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

  • 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 (de manière… …   Wikipédia en Français

  • Méthode de tri — 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

  • 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 (de manière… …   Wikipédia en Français

  • НЕРВЫ ЧЕЛОВЕКА — НЕРВЫ ЧЕЛОВЕКА. [Анатомия, физиология и патология нерва см. ст. Нервы в томе XX; там же (ст. 667 782) рисунки Нервы человека]. Ниже приведена таблица нервов, освещающая в систематическом порядке важнейшие моменты анатомии и физиологии каждого… …   Большая медицинская энциклопедия

  • Positional notation — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese …   Wikipedia

  • Liste Des Algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique …   Wikipédia en Français

  • Liste des algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique …   Wikipédia en Français

  • Список праиндоевропейских корней — Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное …   Википедия

Share the article and excerpts

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