Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ANNEE ACADEMIQUE 2021-2022 EXPOSE DE STRUCTURES DE DONNEES THEME : LE TRI PAR P

ANNEE ACADEMIQUE 2021-2022 EXPOSE DE STRUCTURES DE DONNEES THEME : LE TRI PAR PAQUETS Présenté par :  AKAFFOU Marcel  DUANDUE Archange  FORTINET Saul  N’CHO Marlène  SOKOUA Jean Charles Anderson  Chargé de cours : M. OUATTARA Soma 1 SOMMAIRE GENERALITES .......................................................................................................... 2 I. LES DIFFERENTS TYPES D’ALGORITHMES DE TRI ................................... 3 II. LE TRI PAR PAQUETS ................................................................................ 4 1. Définition ................................................................................................... 4 a. Particularité .............................................................................................. 4 b. Principe de fonctionnement .................................................................... 4 2. Illustration 1 du tri par paquets ............................................................... 5 3. Illustration 2 du tri par paquets ............................................................... 6 CONCLUSION ........................................................................................................... 7 2 GENERALITES Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée. Les objets à trier sont des éléments d'un ensemble muni d'un ordre total. Il est par exemple fréquent de trier des entiers selon la relation d'ordre usuelle « est inférieur ou égal à ». Les algorithmes de tri sont utilisés dans de très nombreuses situations. Ils sont en particulier utiles à de nombreux algorithmes plus complexes dont certains algorithmes de recherche, comme la recherche dichotomique. Ils peuvent également servir pour mettre des données sous forme canonique ou les rendre plus lisibles pour l'utilisateur. 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. 3 I. LES DIFFERENTS TYPES D’ALGORITHMES DE TRI Bon nombre d'algorithmes de tri procèdent par comparaisons successives, et peuvent donc être définis indépendamment de l'ensemble auquel appartiennent les éléments et de la relation d’ordre associée. Un même algorithme peut par exemple être utilisé pour trier des réels selon la relation d'ordre usuelle « est inférieur ou égal à » et des chaînes de caractères selon l'ordre lexicographique. Ces algorithmes se prêtent naturellement à une implémentation polymorphe. Nous pouvons citer entre autre :  Le tri par tas ;  Le tri par sélection ;  Le tri à bulles ;  Le tri par insertion  Le tri rapide. Cependant dans une autre catégorie d’algorithme nous avons les tris en temps linéaire. Ces algorithmes ont en commun une propriété intéressante : le tri qu’ils effectuent repose uniquement sur des comparaisons entre les éléments d’entrée. Ces algorithmes de tri sont appelés tris par comparaison. Tous les algorithmes de tri étudiés jusqu’ici sont des tris par comparaison. Ce sont :  Le tri par dénombrement ;  Le tri par base ;  Le tri par paquets. 4 II. LE TRI PAR PAQUETS 1. Définition Tri par paquets est un algorithme de tri de type comparaison. Il trie les éléments en les répartissant dans des paquets ou des bacs et en utilisant un algorithme différent (généralement le tri par insertion) pour trier le contenu de chaque paquet. Les paquets individuels triés sont ensuite ajoutés ensemble pour obtenir le tableau trié final. Cette approche de l’algorithme de tri est également connue sous le nom d’approche de collecte par dispersion. Elle est principalement utilisée lorsque l’entrée est uniformément distribuée sur une plage comme les flotteurs allant de 0.00 à 1.00. a. Particularité Le tri par paquets s’exécute en temps linéaire quand l’entrée suit une distribution uniforme. À l’instar du tri par dénombrement, le tri par paquets est rapide car il fait des hypothèses sur l’entrée. Là où le tri par dénombrement suppose que l’entrée se compose d’entiers appartenant à un petit intervalle, le tri par paquets suppose que l’entrée a été générée par un processus aléatoire qui distribue les éléments de manière uniforme sur l’intervalle [0, 1) b. Principe de fonctionnement Le principe de ce tri consiste à partitionner régulièrement l'intervalle d'entrée en autant de sous-intervalles que l'entrée comporte d'éléments à trier, et à distribuer les données selon leur valeurs en autant de paquets correspondant à ces sous-intervalles. Les paquets sont alors triés séparément à l'aide d'un autre algorithme de tri. Si les nombres en entrée sont uniformément distribués dans l'intervalle initial, alors la complexité temporelle moyenne du tri par paquets est linéaire, et ce quel que soit l'algorithme de tri auxiliaire utilisé. 5 2. Illustration 1 du tri par paquets Supposons que nous ayons un tableau non trié A [] contenant n éléments.  Créez k (idéalement k est n) des bacs ou des paquets vides en divisant la plage d’entrée en parties égales. Pour chaque élément A[i]présent dans le tableau A, faites ce qui suit :  Insérez A[i] dans le paquet indexé n*A[i].  Triez les différents compartiments à l’aide de l’algorithme de tri par insertion.  Vérifiez l’ordre des godets et concaténez les godets triés pour former le tableau trié final Supposons que nous ayons le tableau : (0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31). Nous allons le trier en utilisant l’algorithme de tri par paquet.  Faites 10 godets de la plage 0.1. Paquet 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0  Après avoir inséré des éléments dans des paquets, on obtient : Paquet 0 1 2 3 4 5 6 7 8 9 0.1 0.22,0.21 0.33,0.38,0.31 0.45 0.55 0 0 0 0  Trier les paquets individuels à obtenir : Paquet 0 1 2 3 4 5 6 7 8 9 0.1 0.21,0.22 0.31,0.33,0.38 0.45 0.55 0 0 0 0 En additionnant tous les résultats, on obtient le tableau final trié comme suit (0.1,0.21,0.22,0.31,0.33,0.38,0.45,0.55). 6 3. Illustration 2 du tri par paquets Notre code du tri par paquets suppose que l’entrée est un tableau à n éléments A et que chaque élément A[i] du tableau satisfait à 0 ≤ A[i] < 1. Le code exige un tableau auxiliaire B [0 . . n − 1] de listes chaînées (paquets) et suppose qu’il existe un mécanisme pour la gestion de ce genre de listes. TRI-PAQUETS(A) :  1 n ← longueur[A]  2 pour i ← 1 à n  3 faire insérer A[i] dans liste B[ nA[i] ]  4 pour i ← 0 à n − 1  5 faire trier liste B[i] via tri par insertion  6 concaténer les listes B[0], B[1],..., B[n − 1] dans l’ordre ILLUSTRATION : Le tableau en entrée A[1 . . 10]. Le tableau B[0 . . 9] de listes (paquets) triées. 7 Le paquet i contient des valeurs appartenant à l’intervalle semi-ouvert [i/10,(i + 1)/10). Le tableau trié consiste en une concaténation ordonnée des listes B[0], B[1],..., B[9]. CONCLUSION Le tri par paquets est assez intéressant à utiliser car nous constatons qu’il y a une phase de regroupement des éléments à trier dans des paquets qui seront ensuite mis en ordre avec le tri par insertion. Nous avons été ravi enrichi quant à l’apprentissage de cet algorithme de tri. uploads/s3/ expose-tri-par-paquets.pdf