Recherche du k-ième plus petit élément d'un tableau A non trié de n éléments indexés de 1 à n.

Simple, surtout pour ceux qui ont vu l'algorithme Tri Rapide (Quicksort) et se rappellent comment ça marche. ¹⁾.

Un de ses ingrédients (le principal?) est la fonction suivante vue l'année dernière :

Procédure Pivot (A[p..r])
  x <- A[p]; i <- p; j <- r;
  tant que i < j faire
      tant que A[j] > x faire j <- j - 1;
      tant que A[i] =< x faire i <- i + 1;
      échanger A[i], A[j];
  renvoyer j;
 

Il y a bien d'autres manières de faire la même chose, dont certaines équivalentes en complexité de calcul mais pas forcément en effets de bord (ils ne laissent pas tous les éléments du tableau aux mêmes positions).

Il est aussi possible de réaliser le travail plus bêtement. Par exemple :

Procédure PivotCher (A[p..r])
   x <- A[p]; i <- p 
   pour k de i+1 à j faire
     si A[k] < x alors
       t <- A[k]
       pour r de k à i par pas de -1
           A[r] <- A[r-1]
       fin pour
           A[i] <- t
     fin si
  fin pour
  

Que fait cet algorithme?

1. Il stock le pivot, A[p], dans x
2. Il parcourt le tableau de gauche à droite et
   1. s'il trouve un élément plus petit que x,
      1. il le sort du tableau
      2. il décale d'une position à droite tous les éléments du pivot (pivot compris) jusqu'à l'emplacement de l'élément trouvé
      3. il met l'élément dans la position jusqu'alors occupée par le pivot, et
      4. il ajuste le pointeur du pivot (+1)

Il fait beaucoup de décalage inutiles : inutiles car le tableau n'est pas trié! Il suffit de répartir les éléments de part et d'autre.

Une variante de l'algorithme donnée en premier, basé sur les remarques d'un camarade de classe, est la suivante :

 Procédure Pivot (A[p..r])
   x <- A[p]; i <- p; j <- r
   tant que i < j faire
     si A[i]>A[i+1] faire
         échanger A[i] et A[i+1]
         i <- i+1
     sinon
         échanger A[i+1] et A[j]
         j <- j - 1
     fin si
  fin tant que
  renvoyer i

Cet algorithme se résume ainsi :

• si le pivot rencontre plus petit que lui, il le dépasse (et ajuste son adresse)
• s'il rencontre plus grand, il l'envoie dans le tas “plus grand et vu” et avance un pas-encore-vu, tant qu'il y en a.

L'important est que les premier et dernier algorithmes ne font pas plus de n=r-p échanges (réaffectations de position) tandis que PivotCher déplace beaucoup plus d'éléments (si A[p] est le maximum de A[p..r], par exemple, mais pas seulement dans ce cas). PivotCher a une complexité qui peut être, dans certains cas, proportionnelle à n² et non seulement à n

Comme nous avons vu, l'algorithme (mais pas PivotCher) parcourt le tableau une fois, et ne fait que un test et un changement de pointeur à chaque pas. Sa complexité est donc O(n).

Muni de Pivot (A[p..q]) une solution serait

Cherche (A[p..q],k)
  si k>(q-p+1) renvoyer erreur
  l <- Pivot(A[p..q])
  si l = k renvoyer A[l]
  sinon
      si l < k renvoyer Cherche(A[l+1..q],k-l)
      sinon renvoyer Cherche(A[p..l-1],k)
      fin si
  fin si

L'appel initial est Cherche(A[1..n],k).

Pivot(A[p..q]) retourne l, la position de l'élément qui est plus grand que l-1 éléments (à sa gauche) et plus petit (ou égal à) tous les autres, à sa droite. Si k = l, le k-ième plus petit est trouvé. Sinon, de deux choses l'une :

• soit l est plus grand que k est le k-ième plus petit figure parmi les l-1 plus petits que A[l], donc on appelle Cherche(A[p..l-1], k)
• soit l est plus petit que k, il faut donc chercher le (k-l)-ième plus petit parmi les plus grands que A[l] qui sont A[l+1..q] : on appelle Cherche(A[l+1..q], k-l).

Chaque appel récursif fait appel à Pivot(A[i..j]), O(n=j-i), et autrement ne fait qu'un test ou deux, et un seul appel récursif au plus. Dans le schéma “a*f(n/b)”, a=1, mais b peut être proche de 1 : il se peut qu'on divise très peu à chaque appel.

Au pire, on réduit la taille du sous-tableau de seulement un élément à chaque appel, et ce tant qu'on peut sans diminuer k' : c'est le cas où les éléments était triés par ordre décroissant initialement. On appellera

1. Cherche(A[p..q], k) qui renverra q
2. Cherche(A[p..q-1], k) qui renverra q-1
3. etc.

Soit n-1 appels récursifs avec coûts dégressifs n-2, n-3, … \sum_{i=1}^{n-1} (i-1) \approx \frac{n^2 - n}{2} \rightarrow O\left(n^2\right)