Dans cet article, nous allons discuter des propriétés importantes de différentes techniques de tri, y compris leur complexité, leur stabilité et les contraintes de mémoire. Avant de comprendre cet article, vous devez comprendre les bases des différentes techniques de tri (Voir : Techniques de tri).
Analyse de la complexité temporelle –
Nous avons discuté de la meilleure, moyenne et pire complexité des différentes techniques de tri avec des scénarios possibles.
Tri basé sur la comparaison –
Dans le tri basé sur la comparaison, les éléments d’un tableau sont comparés entre eux pour trouver le tableau trié.
- Tri à bulles et tri par insertion –
Complexité temporelle moyenne et dans le pire des cas : n^2
Complexité temporelle dans le meilleur des cas : n lorsque le tableau est déjà trié.
Plus mauvais cas : lorsque le tableau est trié à l’envers. - Tri par sélection –
Meilleure, moyenne et pire complexité temporelle : n^2 qui est indépendant de la distribution des données. - Tri par fusion –
Meilleure, moyenne et pire complexité en temps : nlogn qui est indépendant de la distribution des données. - Tri par tas –
Meilleure, moyenne et pire complexité en temps : nlogn qui est indépendant de la distribution des données. - Tri rapide –
C’est une approche de type diviser pour régner avec une relation de récurrence:T(n) = T(k) + T(n-k-1) + cn
Plus mauvais cas : lorsque le tableau est trié ou trié à l’envers, l’algorithme de partition divise le tableau en deux sous tableaux avec 0 et n-1 éléments. Par conséquent,
T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)
Le meilleur cas et le cas moyen : En moyenne, l’algorithme de partition divise le tableau en deux sous-réseaux de taille égale. Par conséquent,
T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)
Tri basé sur la non-comparaison –
Dans le tri basé sur la non-comparaison, les éléments du tableau ne sont pas comparés entre eux pour trouver le tableau trié.
- Tri Radix –
Meilleure, moyenne et pire complexité temporelle : nk où k est le nombre maximum de chiffres dans les éléments du tableau. - Tri Count –
Meilleure, moyenne et pire complexité temporelle : n+k où k est la taille du tableau count. - Tri par godets –
Meilleure et moyenne complexité temporelle : n+k où k est le nombre de godets.
Meilleure complexité temporelle dans le pire des cas : n^2 si tous les éléments appartiennent au même godet.
Technique in-place/outplace –
Une technique de tri est inplace si elle n’utilise pas de mémoire supplémentaire pour trier le tableau.
Parmi les techniques basées sur la comparaison discutées, seul le tri par fusion est une technique outplace car il nécessite un tableau supplémentaire pour fusionner les sous-réseaux triés.
Parmi les techniques non basées sur la comparaison discutées, toutes sont des techniques outplace. Le tri par comptage utilise un tableau de comptage et le tri par seau utilise une table de hachage pour trier le tableau.
Technique en ligne/hors ligne –
Une technique de tri est considérée comme en ligne si elle peut accepter de nouvelles données pendant que la procédure est en cours c’est-à-dire que des données complètes ne sont pas nécessaires pour commencer l’opération de tri.
Parmi les techniques basées sur la comparaison discutées, seul Insertion Sort remplit cette condition en raison de l’algorithme sous-jacent qu’il utilise c’est-à-dire. il traite le tableau (pas seulement les éléments) de gauche à droite et si de nouveaux éléments sont ajoutés à droite, cela n’a pas d’impact sur l’opération en cours.
Technique stable/Instable –
Une technique de tri est stable si elle ne change pas l’ordre des éléments ayant la même valeur.
Parmi les techniques basées sur la comparaison, le tri à bulles, le tri par insertion et le tri par fusion sont des techniques stables. Le tri par sélection est instable car il peut changer l’ordre des éléments ayant la même valeur. Par exemple, considérons le tableau 4, 4, 1, 3.
Dans la première itération, l’élément minimum trouvé est 1 et il est échangé avec 4 en 0ème position. Par conséquent, l’ordre de 4 par rapport à 4 à la 1ère position va changer. De même, le tri rapide et le tri par tas sont également instables.
Parmi les techniques non basées sur la comparaison, le tri par comptage et le tri par seau sont des techniques de tri stables alors que la stabilité du tri radix dépend de l’algorithme sous-jacent utilisé pour le tri.
Analyse des techniques de tri :
- Lorsque le tableau est presque trié, le tri par insertion peut être préféré.
- Lorsque l’ordre d’entrée n’est pas connu, le tri par fusion est préféré car il a une complexité temporelle de nlogn dans le pire des cas et il est également stable.
- Lorsque le tableau est trié, le tri par insertion et par bulle donne une complexité de n mais le tri rapide donne une complexité de n^2.
Que – 1. Quel algorithme de tri prendra le moins de temps lorsque tous les éléments du tableau d’entrée sont identiques ? Considérer les implémentations typiques des algorithmes de tri.
(A) Tri par insertion
(B) Tri par tas
(C) Tri par fusion
(D) Tri par sélection
Solution : Comme discuté, le tri par insertion aura la complexité de n lorsque le tableau d’entrée est déjà trié.
Que – 2. Considérons l’algorithme Quicksort. Supposons qu’il existe une procédure pour trouver un élément pivot qui divise la liste en deux sous-listes dont chacune contient au moins un cinquième des éléments. Soit T(n) le nombre de comparaisons nécessaires pour trier n éléments. Alors, (GATE-CS-2012)
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) <= 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
Solution : La complexité du tri rapide peut s’écrire comme:
T(n) = T(k) + T(n-k-1) + cn
Comme donné dans la question, une liste contient 1/5ème des éléments totaux. Par conséquent, une autre liste aura 4/5ème des éléments totaux. En mettant les valeurs, on obtient :
T(n) = T(n/5) + T(4n/5) + cn, ce qui correspond à l’option (B).
Tableau de comparaison des complexités temporelles et spatiales :
| Algorithme de tri | Complexité temporelle | Complexité spatiale | ||
|---|---|---|---|---|
| Meilleur cas | Cas moyen. Cas | Cas le plus défavorable | Cas le plus défavorable | |
| Tri à bulles | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Tri par sélection | Ω(N2) | Θ(N2) | O(N2) | O(1) |
| Tri par insertion | Ω(N) | Θ(N2) | O(N2) | O(1) |
| Tri par fusion | Ω(N log N) | Θ(N log N) | O(N log N) | O(N) |
| Tri par tas | Ω(N log N) | Θ(N log N) | O(N log N) | O(1) |
| Tri rapide | Ω(N log N) | Θ(N log N) | O(N2) | O(N log N) |
| Tri Radix | Ω(N k) | Θ(N k) | O(N k) | O(N + k) |
| Tri de comptage | Ω(N + k) | Θ(N + k) | O(N + k) | O(k) |
| Tri de godets | Ω(N + k) | Θ(N + k) | O(N2) | O(N) |
