Tri faire-valoir

Tri faire-valoir

Visualisation du tri faire-valoir (qui ne montre que les échanges).

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	${\displaystyle O(n^{log{3}/log{1.5}})}$

Complexité en espace

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

modifier - modifier le code - modifier Wikidata

En informatique, le tri faire-valoir est un algorithme de tri récursif. Il est appelé stooge sort en anglais, nom inspiré des Trois Stooges^[1]. Il est présenté en exercice dans le livre Introduction à l'algorithmique de Cormen, Leiserson, Rivest et Stein ^[2].

Principe

Le principe du tri faire-valoir est le suivant :

1. On échange le premier et le dernier élément du tableau à trier s'ils ne sont pas dans le bon ordre.
2. Si le tableau contient plus de trois éléments :
   • on trie le premier 2/3 du tableau ;
   • on trie le dernier 2/3 du tableau ;
   • on retrie le premier 2/3 du tableau à nouveau.

Sa complexité temporelle est O(n^{log 3 / log 1,5} ) = O(n^2,7095...)^[1], ainsi cet algorithme est particulièrement inefficace en comparaison avec le tri rapide ou le tri à bulles.

Implémentation

 function stoogesort(A, i, j)
     if A[i] > A[j] then
         échanger A[i] et A[j]
     if (j - i + 1) > 2 then
         t = (j - i + 1) / 3
         stoogesort(A, i  , j-t)
         stoogesort(A, i+t, j  )
         stoogesort(A, i  , j-t)
     return A

Notes et références

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