1.Présentation

Le tri rapide permute sur place les éléments d'un tableau spécifié pour les ranger dans l'ordre croissant d'une relation d'ordre spécifiée. Pour un tableau de n éléments, sa complexité au pire est en n² mais sa complexité moyenne en nlog(n).

Nous voulons écrire une définition de la fonction qs : ('a -> 'a -> bool) -> 'a vect -> unit telle que [qs inf t] trie sur place, suivant l'ordre croissant de la relation d'ordre [inf], les éléments du tableau [t].

Je vous propose d'écrire deux versions simples de l'algorithme, variantes de la même technique.

2.Première version

La fonction qs est définie à l'aide de deux fonctions auxiliaires internes :

une fonction récursive qsr : int * int -> unit et
une pseudo-fonction place : int * int -> int

disposant dans leur environnement global de la relation d'ordre [inf] et du tableau [t], paramètres de la fonction [qs].

2.1.La fonction place (i, j)

Elle est appelée (par qsr) seulement avec i < j.
Elle n'a le droit de ne modifier que les éléments du tableau [t] d'indices compris entre i et j inclus.
Plus précisément elle n'effectue que des permutations de deux éléments (distincts ou confondus) du tableau [t] d'indices (différents ou égaux) compris entre i et j inclus.
Elle n'effectue pas un tri mais réordonne partiellement les éléments du tableau ; plus précisément elle retourne un indice k tel que

i <= k <= j,
pour tout n compris entre i inclus et k exclu, inf t.(n) t.(k)
pour tout n compris entre k exclu et j inclus, not (inf t.(n) t.(k)).

Pour établir cette dernière propriété, on choisit comme élément "pivot" l'élément t.(i) que l'on nomme p.

On définit une boucle utilisant deux indices l et k, boucle construite sur l'invarient suivant :

tous les éléments x, d'indice compris entre i+1 et l-1 inclus, vérifient inf x p,
aucun des éléments x, d'indice compris entre l et k inclus, n'a été modifié ni testé,
tous les éléments x, d'indice compris entre k+1 et j inclus, vérifient not (inf x p)
avec i < l <= k+1 <= j+1

2.1.1.initialisation

Écrire la déclaration locale multiple permettant d'initialiser cette boucle.

2.1.2.Corps de la boucle

On compare le premier élément non testé t.(l) à p :

que doit-on faire pour retrouver l'invarient de boucle si inf x p ?
sinon, on permute les éléments t.(l) et t.(k) et l'on décrémente k.

2.1.3.Poursuite de la boucle

Quelle propriété sur l et k permet de vérifier qu'il reste encore des éléments à tester ? L'écrire comme condition de la boucle while.

2.1.4.Fin de la boucle

Lorsque tous les éléments, d'indice compris entre i+1 et j inclus ont été testés (et éventuellement permutés), il ne reste plus qu'à permuter l'élément p d'indice i et l'élément d'indice k et retourner la valeur de l'indice k.

2.2.La fonction récursive qsr (i, j)

Elle doit trier sur place les seuls éléments du tableau t compris entre les indices i et j inclus sans modifier le reste du tableau.

2.2.1.Dans le cas général

Pour effectuer le tri des éléments de l'intervalle d'indice i..j,

on appelle la prodédure place (i, j) qui retourne l'indice nommé k tel que
i <= k <= j,
tous les éléments x de l'intervalle d'indices i..k-1 vérifient inf x t.(k) et
tous les éléments x de l'intervalle d'indices k+1..j vérifient not (inf x t.(k))
puis on appelle récursivemant qsr sur les deux intervalles d'indices i..k-1 et k+1..j ce qui termine le tri du tableau par hypothèse de récurrence.

2.2.2.Arrêt de la récursivité

Dans quels cas doit-on arrêter la récursivité ?

Écrire une déclaration de la fonction qsr.

2.3.La fonction qs

Écrire sa définition pour réaliser le tri de l'ensemble du tableau.

2.4.Tester cette définition

3.Seconde version

On modifie la seule fonction place pour la rendre un peu plus efficace. La modification porte sur le corps de la boucle décrit au paragraphe 2.1.2. Dans la partie sinon, avant d'effectuer la permutation des éléments t.(l) et t.(k), on décrémente l'indice k tant que l'élément t.(k) vérifie not (inf t.(k) p) et donc peut rester en place. Quelles précautions prendre et quelles actions effectuer pour pour rétablir l'invarient de boucle ?

Écrire et tester cette version finale.