En informatique, le tri faire-valoir est un algorithme de tri récursif. Il est appelé stooge sort en anglais, nom inspiré des Trois Stoogeshttps://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-22/18-sorting1-bogo-stooge-bubble.pdf. Il est présenté en exercice dans le livre Introduction à l'algorithmique de Cormen, Leiserson, Rivest et Stein .
Principe 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 , 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
Faire-valoir