Please enable JavaScript.
Coggle requires JavaScript to display documents.
Les algorithmes de tri (Le tri rapide (‘’quicksort’’) (diviser pour…
Les algorithmes de tri
Tri par tas
:timer_clock: Θ(n log n) en pire cas; et Θ(n) en meilleur cas (lorsque les éléments sont identiques)
:card_file_box: Se fait sur place (dans le tableau)
N’est pas stable
Tri par arbre (construire arbre binaire et visiter les nœuds à l'aide du parcours en ordre)
:timer_clock: Θ(n log n) en pire cas et meilleur cas
:card_file_box: Ne se fait sur place (dans le tableau)
Peut être stable lorsque la structure de données
utilisée pour stocker les éléments de clés égales le permet (ex: liste)
Tri par sélection
Le tri rapide (‘’quicksort’’) (diviser pour régner)
:timer_clock: en Θ(n2) en pire cas, en O(n log n) en meilleur cas et en O(n log n) en cas moyen
:card_file_box: effectue le tri sur place
n'est pas stable
Démarche
l’idée de base est celle du tri du bijoutier
Trier les perles avec des tamis plus ou moins fins
Pour chaque tamis
on sépare les perles en deux sous-ensembles (celles qui passent et celles qui restent dans le tamis)
puis on trie celles qui sont passées avec un tamis plus fin et les autres avec un tamis plus gros
Approche diviser pour régner
1)
choisir un pivot p
(un bon choix partitionne le tableau en 2 parties égales)
:check: Un meilleur choix est la médiane des 3 éléments parmi le premier élément, l’élément du milieu et celui en fin du tableau.
:red_cross: Dernier élément? Mauvais choix pour une raison identique au 1er choix
:red_cross: Premier élément? Mauvais choix si les éléments sont (presque) triés
2)
partager le tableau en 2
sous-tableau de droite : éléments ≥ p
(l’élément pivot sera alors à sa
place définitive)
sous-tableau de gauche : éléments ≤ p
3)
appel récursif avec le sous-tableau de gauche
4)
appel récursif avec le sous-tableau de droit
Le tri fusion (‘’mergesort’’) (diviser pour régner)
:timer_clock:en Θ(n log n) en pire cas et en
meilleur cas
:card_file_box: mergesort() utilise alors Θ(n) cases mémoire additionnelles pour les fusions
des demi-tableaux
stable
Approche diviser pour régner
1)
Diviser
Diviser le tableau a[0,..,n-1] en 2 tableaux de tailles égales
(autant que faire se peut): a[0,… ⎣n/2⎦ -1] et a[⎣n/2⎦, …, n-1]
2)
Régner
Trier (récursivement) chacun de ces 2 tableaux
3)
Fusioner
Fusionner les 2 tableaux triés en un seul tableau trié
Le tri par insertion
:timer_clock: Θ(n) en meilleur cas et Θ(n2) en pire cas
:card_file_box: effectue le tri sur place (in situ) donc pas besoin d'espace mémoire additionnel
stable
Démarche
Pour p = 1, .., n-1, on s’assure que les éléments a[0,…, p-1] sont en ordre croissant (i.e.: a[0] ≤ a[1] ≤ … ≤ a[p-1]). C’est le cas, trivialement, à l’étape initiale p=1
Le tri de a[0,…,n-1] effectue n-1 étapes
On copie l’élément a[p] dans tmp
Pour j = p à 1: on copie a[j-1] dans a[j] tant que tmp < a[j-1]. On insère alors temp à la 1ière position j rencontrée telle que temp ≥ a[j-1]
Propriétés principales des algorithmes de tri
Utilisation de mémoire pour le tri
tri sur place (in situ) ou nécessité de stocker les éléments dans une
structure intermédiaire pour le tri
Stabilité
C’est stable si on conserve l'ordre original pour éléments de clés égales
Complexité du temps d’exécution
Pire cas, meilleur cas et cas moyen
Les tris dans la STL
Ils sont présents dans la bibliothèque <algorithm> et nécessitent l’utilisation de conteneurs possédant des itérateurs à accès direct (comme <vector> mais pas comme <list>)
sort()
Mais ne garanti pas la stabilité
Tri sur place
Garanti un temps moyen en O(n log n)
Le tri rapide (quicksort) le tri par tas (heapsort) répondent à ce critère
stable_sort()
Ne tri pas sur place et garanti O(n log n) en pire cas s’il y a
suffisamment de mémoire de disponible
Le tri fusion (mergesort) répond à ce critère
Garanti la stabilité