Outils pour utilisateurs

Outils du site


les_exposes:trier_des_donnees

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision
Révision précédente
les_exposes:trier_des_donnees [09/04/2015 10:04]
haber [II) Différents types d'algorithmes de tri.]
les_exposes:trier_des_donnees [15/04/2016 11:14] (Version actuelle)
lecoeur
Ligne 1: Ligne 1:
-====== Comment trier des données ? ======+LECOEUR Nolwenn
  
 +====== Comment trier des données ? ======
    
  
-===== I) Introduction =====+----
  
 +===== 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).+Vous aurez sûrement remarqué qu’il ​est plus rapide et plus simple ​de trouver quelque chose lorsque ​les données dans lesquelles on cherche ​sont triées.
  
-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. +//C’est une chose que nous savons depuis qu’il existe des bibliothèques et des bibliothécaires : même si cela est long et fatigant, il vaut mieux ranger ​les livres d’une bibliothèque une fois pour toutes, par exemple dans l’ordre alphabétique,​ plutôt que les laisser en vrac et arpenter des kilomètres ​de rayonnages à chaque fois que l’on cherche un volume.//
-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.+Cela mène naturellement à un nouveau problème : **comment trier des données ?** Selon le dictionnaire,​ “trier” signifie “répartir en plusieurs classes selon certains critères”. De manière plus restrictive,​ le terme de “tri” en algorithmique ​est très souvent attaché au processus de classement d'un ensemble ​d'éléments dans un ordre donné.
  
 +//Par exemple, trier N entiers dans l'​ordre croissant, ou N noms dans l'​ordre alphabétique. Tout ensemble muni d'un ordre total peut fournir une suite d'​éléments à trier.//
  
-==== II) Différents types d'algorithmes de tri. ====+Ainsi, pour trier des données, on utilise généralement des **algorithmes de tri**. Ils sont fondamentaux dans certains domaines, comme l'​informatique de gestion où l'on tri de manière quasi-systématique des données avant de les utiliser.
  
-__**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.+ 
 +===== II- Algorithmes de tri : définition ===== 
 + 
 + 
 +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). 
 + 
 +La collection à trier est souvent donnée sous forme de tableau, afin de permettre l'​accès direct aux différents éléments de la collection, ou sous forme de liste, ce qui peut se révéler être plus adapté à certains algorithmes et à l'​usage de la programmation fonctionnelle. 
 + 
 +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é temporelle :** mesure le nombre d'​opérations élémentaires effectuées pour trier une collection d'​éléments. C'est un critère majeur pour comparer les algorithmes de tri, puisque c'est une estimation directe du temps d'​exécution de l'​algorithme. (=complexité algo) 
 + 
 +  * **La complexité spatiale :** représente la quantité de mémoire dont va avoir besoin l'​algorithme pour s'​exécuter.  
 +  
 +  * **Le caractère stable :** Un tri est stable s’il préserve l’ordre d’apparition des objets en cas d’égalité des clés.  
 + 
 + 
 +---- 
 + 
 + 
 +===== III- Différents types d’algorithmes de tri ===== 
 + 
 +==== 1) Tris par comparaison ==== 
 + 
 +=== a) Algorithmes lents === 
 + 
 +  * **Tri par sélection :** Il s'​agit,​ à chaque itération, d'​identifier le plus petit des éléments qui ne sont pas encore triés : on cherche d'​abord le plus petits des éléments non triés et on le place en premier dans le tableau trié. On cherche ensuite parmi ceux qui restent, le plus petit des éléments, qui sera le deuxième du tableau trié, etc... //L’algorithme de tri par sélection est volontiers utilisé pour trier des objets, comme des cartes à jouer, des livres, etc. à la main.//
  {{ :​les_exposes:​tri_selection.png?​200 |}}  {{ :​les_exposes:​tri_selection.png?​200 |}}
  
- 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 par insertion :** C'est le tri souvent utilisé naturellement pour trier des cartes à jouer : les valeurs sont insérées les unes après ​les autres ​dans une liste triée (initialement vide)C'est souvent ​le plus rapide et le plus utilisé pour trier des entrées de petite tailleL'​objectif d'une étape est d'​insérer le i-ème élément à sa place parmi ceux qui précèdent. Il faut pour cela trouver où l'​élément doit être inséré en le comparant aux autrespuis décaler les éléments afin de pouvoir effectuer l'​insertion. En pratique, ces deux actions sont fréquemment effectuées en une passe, qui consiste à faire « remonter » l'​élément au fur et à mesure jusqu'​à rencontrer ​un élément plus petit. 
-   +{{ :​les_exposes:​tri_insertion.jpg?​200 |}} 
-  + 
 +**Autres exemples d’algorithmes lents :**
   * Tri à bulles   * Tri à bulles
-  * Tri par insertion+  * Tri cocktail 
 +  * Tri pair-impair  
 +  * Tri stupide
  
-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.+ 
 +=== b) 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.
   ​   ​
 {{ :​les_exposes:​251906.png?​200 |}} {{ :​les_exposes:​251906.png?​200 |}}
Ligne 45: Ligne 74:
  
  
-  ​Tri rapide+**Autres exemples d’algorithmes rapides :**
   * Tri de Shell   * Tri de Shell
 +  * Tri rapide
 +  * Tri par tas
 +  * Introsort
 +  * Tri arborescent ​
 +  * Smoothsort
 +  * Tri à peigne
  
-__**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 . +==== 2) Tris utilisant ​la structure ​des données ​====
-  *     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**__ +  * **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[. 
 + 
 + 
 + 
 +==== 3) 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). 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).
Ligne 65: Ligne 103:
   -   On trie chaque sous-ensemble en mémoire centrale pour former des « monotonies » (sous-ensembles triés) ;   -   On trie chaque sous-ensemble en mémoire centrale pour former des « monotonies » (sous-ensembles triés) ;
   -   On interclasse ces monotonies.   -   On interclasse ces monotonies.
- 
- 
- 
les_exposes/trier_des_donnees.1428566649.txt.gz · Dernière modification: 09/04/2015 10:04 par haber