Tri faire-valoir

Complexité en temps
Problème lié	Algorithme de tri
Structure des données	Tableau
Pire cas
Pire cas

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[modifier | modifier le code]

Le principe du tri faire-valoir est le suivant :

On échange le premier et le dernier élément du tableau à trier s'ils ne sont pas dans le bon ordre.
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[modifier | modifier le code]

 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[modifier | modifier le code]

↑ ^{a et b} https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-22/18-sorting1-bogo-stooge-bubble.pdf
↑ (en) Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction à l'algorithmique, Paris, Dunod, 2002, xxix+1146 (ISBN 978-2-10-003922-7, SUDOC 068254024), chap. 7 (« Tri rapide »)

Portail de l'informatique théorique

[:0-1] {a et b} https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-22/18-sorting1-bogo-stooge-bubble.pdf

[Cormen7-2] (en) Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction à l'algorithmique, Paris, Dunod, 2002, xxix+1146 (ISBN 978-2-10-003922-7, SUDOC 068254024), chap. 7 (« Tri rapide »)

[1]

[2]