Outils pour utilisateurs

Outils du site


les_exposes:trier_des_donnees

Ceci est une ancienne révision du document !


LECOEUR Nolwenn

Comment trier des données ?

I) Introduction

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 générale un ordre total). Les ordres les plus utilisés sont l’ordre numérique et l'ordre lexicographique (dictionnaire).

De plus, tous les algorithmes ne sont pas identiques, il existe plusieurs critères qui permettent des les différencier afin de choisir celui le plus adapté pour un cas. Les principales caractéristiques qui permettent de différencier les algorithmes de tri sont :

  • La complexité algorithmique
  • Les ressources nécessaires (espace mémoire utilisée)
  • Le caractère stable

Un algorithme est dit stable s'il garde l'ordre relatif des quantités égales pour la relation d'ordre.

II) Différents types d'algorithmes de tri.

Tris par comparaison

Algorithmes lents :

  • Tri par sélection : L’algorithme de tri par sélection est volontiers utilisé pour trier des objets, comme des cartes à jouer, des livres, etc. à la main.

On commence par chercher, parmi les objets à trier, un élément plus petit que tous les autres. Cet élément sera le premier du tableau trié. On cherche ensuite,parmi ceux qui restent, un élément plus petit que tous les autres, qui sera le deuxième du tableau trié, etc.

* Tri à bulles
* Tri par insertion

Algorithmes rapides :

  • Tri fusion : Les algorithmes de tri par sélection, par insertion ou à bulles sont très lents.L’algorithme de tri par fusion fait la même chose que ces trois algorithmes, mais beaucoup plus rapidement.

Le principe de cet algorithme est le suivant :

  1. On découpe les données à trier en deux parties plus ou moins égales
  2. On trie les 2 sous-parties ainsi déterminées
  3. On fusionne les deux sous-parties pour retrouver les données de départ
  • Tri rapide
  • Tri de Shell

Tris utilisant la structure des données

  • Tri comptage ou Tri par dénombrement : Nécessite l'utilisation d'une seconde liste de même longueur que la liste à trier. Son utilisation relève de la condition que les valeurs à trier sont des entiers naturels dont on connaît les extrema .
  • Tri par base : Nécessite aussi l'utilisation d'une seconde liste de même longueur que la liste à trier .
  • Tri par paquets: Part de l'hypothèse que les données à trier sont réparties de manière uniforme sur un intervalle réel [a, b[.

Tri volumineux

Les algorithmes de tri doivent aussi être adaptés en fonction des configurations informatiques sur lesquels ils sont utilisés. Dans les exemples cités plus haut, on suppose que toutes les données sont présentes en mémoire centrale (ou accessibles en mémoire virtuelle). La situation se complexifie si l'on veut trier des volumes de données supérieurs à la mémoire centrale disponible (ou si l'on cherche à améliorer le tri en optimisant l'utilisation de la hiérarchie de mémoire).

Ces algorithmes sont souvent basés sur une approche assez voisine de celle du tri fusion. Le principe est le suivant :

  1. On découpe le volume de données à trier en sous-ensembles de taille inférieure à la mémoire rapide disponible ;
  2. On trie chaque sous-ensemble en mémoire centrale pour former des « monotonies » (sous-ensembles triés) ;
  3. On interclasse ces monotonies.
les_exposes/trier_des_donnees.1456997094.txt.gz · Dernière modification: 03/03/2016 10:24 par lecoeur