Tri faire-valoir

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Tri faire-valoir
Image illustrative de l’article Tri faire-valoir
Visualisation du tri faire-valoir (qui ne montre que les échanges).

Problème lié Algorithme de tri
Structure des données liste ou tableau
Temps d'exécution pire-cas O(nlog 3 /log 1.5
Complexité algorithmique spatiale O(n)

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

Principe[modifier | modifier le code]

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 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(nlog 3 / log 1.5 ) = O(n2.7095...)[1].

Implementation[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]