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 [05/03/2016 16:51]
lecoeur
les_exposes:trier_des_donnees [15/04/2016 11:14] (Version actuelle)
lecoeur
Ligne 52: Ligne 52:
   * **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 taille. L'​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 autres, puis 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.   * **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 taille. L'​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 autres, puis 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 |}} {{ :​les_exposes:​tri_insertion.jpg?​200 |}}
 +
 +**Autres exemples d’algorithmes lents :**
 +  * Tri à bulles
 +  * Tri cocktail
 +  * Tri pair-impair ​
 +  * Tri stupide
 +
 +
 +
 +=== 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 |}}
 +  ​
 + Le principe de cet algorithme est le suivant :
 + 
 +  -     On découpe les données à trier en deux parties plus ou moins égales
 +  -     On trie les 2 sous-parties ainsi déterminées
 +  -     On fusionne les deux sous-parties pour retrouver les données de départ
 +
 +
 +**Autres exemples d’algorithmes rapides :**
 +  * Tri de Shell
 +  * Tri rapide
 +  * Tri par tas
 +  * Introsort
 +  * Tri arborescent ​
 +  * Smoothsort
 +  * Tri à peigne
 +
 +
 +
 +==== 2) 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[.
 +
 +
 +
 +==== 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).
 +
 +Ces algorithmes sont souvent basés sur une approche assez voisine de celle du tri fusion. Le principe est le suivant :
 +
 +   ​- ​ On découpe le volume de données à trier en sous-ensembles de taille inférieure à la mémoire rapide disponible ;
 +  -   On trie chaque sous-ensemble en mémoire centrale pour former des « monotonies » (sous-ensembles triés) ;
 +  -   On interclasse ces monotonies.
les_exposes/trier_des_donnees.1457193062.txt.gz · Dernière modification: 05/03/2016 16:51 par lecoeur