Cet article ne cite pas suffisamment ses sources (mai 2020).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Smoothsort

Smoothsort fonctionnant sur un réseau qui est presque en ordre. Les barres en haut montrent la structure de l'arbre.

Découvreur ou inventeur	Edsger W. Dijkstra
Date de découverte	1981
Problème lié	Algorithme de tri
Structure des données	Tableau
Basé sur	Tri par tas

Complexité en temps

Pire cas	${\displaystyle O(n\log n)}$
Moyenne	${\displaystyle O(n\log n)}$
Meilleur cas	${\displaystyle O(n)}$

Complexité en espace

Pire cas	${\displaystyle O(n)}$
Meilleur cas	${\displaystyle O(1)}$

modifier - modifier le code - modifier Wikidata

Smoothsort est un algorithme de tri par comparaison inventé en 1981 par Edsger Dijkstra. Tout comme le tri par tas, dont il est inspiré, c'est un tri par file de priorité et c'est un tri de complexité en ${\displaystyle O(n\log {n})}$. Mais si les données sont déjà presque triées, il est de complexité en ${\displaystyle O(n)}$. Ce tri est alors plus rapide que le tri par tas, ce qui est l'avantage majeur du smoothsort.

La transition entre les temps d'exécution entre les listes déjà triées et les listes mélangées ou à l'envers est progressive d'où le nom smoothsort, smooth signifiant doux, lisse. C'est un tri sur place, c'est-à-dire qu'il n'y a pas de zone mémoire allouée supplémentaire pour stocker les éléments.

Si l'algorithme smoothsort est plus rapide que le tri par tas pour des listes peu mélangées, il est légèrement plus lent que le tri par tas pour des listes qui sont plutôt dans le sens décroissant au départ. En effet, les données de départ sont alors plus proche de la structure de tas.

Le tri par tas a un inconvénient majeur, c'est que si les données sont déjà triées, elles vont être d'abord mélangées avant d'être de nouveau triées. Cela est dû au fait que les données intermédiaires sont un arbre binaire où les nœuds parents sont supérieurs aux nœuds enfants, les parents étant sur la gauche des enfants dans le tableau.

Ainsi, lors de cette phase du tri par tas, les premiers éléments du tableau sont les plus grands, alors qu'à la fin du tri, les plus grands éléments doivent être à la fin du tableau (on suppose qu'on trie par ordre croissant).

Pour pallier cet inconvénient, smoothsort utilise un arbre binaire dans l'autre sens, c'est-à-dire dont l'ordre partiel imposé aux nœuds de l'arbre est dans le même sens que l'ordre final voulu (les données de l'arbre et les données d'entrées sont stockées dans le même tableau, comme pour le tri par tas). Cela demande une réorganisation des données de l'arbre au fur et à mesure du tri. Mais comme l'arbre est construit dans le sens croissant, si le tableau est déjà trié, il n'y a rien à faire et les données ne sont pas mélangées.

La première étape consiste à transformer le tableau en un arbre binaire. Le premier élément est déjà trivialement bien ordonné, puis on ajoute un à un les éléments suivants. On réordonne chaque fois un peu les éléments si nécessaire pour qu'ils correspondent aux critères :

• Chaque nœud ne peut être supérieur à son nœud parent
• Le premier nœud enfant ne peut être supérieur au deuxième nœud enfant

NB : Ces critères imposent un ordre dans le même sens que le sens trié, d'où l'intérêt de cet algorithme.

La deuxième étape consiste à retransformer l'arbre binaire en tableau trié. Chaque élément en partant de la droite est laissé tel quel car il s'agit de la racine de l'arbre qui est déjà le plus grand élément, et l'arbre restant est réordonné si nécessaire. On fait ceci jusqu'à arriver à un tableau trié.

• Description de smoothsort par Dijkstra

v · m Algorithmes de tri
Tris par comparaisons	Sans hypothèse autre Complexité moyenne ${\displaystyle {\mathcal {O}}(n\log n)}$ Tri rapide Tri fusion Tri par tas Introsort Smoothsort Timsort Tri arborescent Tri à peigne (?) Tri de Shell (?) Complexité moyenne ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri à bulles Tri par insertion Tri par sélection Tri cocktail Complexité moyenne moins bonne que ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri spaghetti Tri stupide Tri faire-valoir Avec hypothèse supplémentaire Tri comptage Tri par base Tri par paquets Réseau de tri Tri bitonique Tri pair-impair
Tri utilisant d'autres opérations	Tri de crêpes Algorithme de tri externe Tri topologique
Applications	Problème du drapeau hollandais Recherche dichotomique

• Portail de l'informatique théorique