Aller au contenu
Topos Uranos
Français

Rechercher et trier

Résumé

Rechercher et trier sont les deux problèmes fondamentaux sur les collections, et il y a entre eux un compromis : trier une fois coûte, mais rend moins chère chaque recherche ultérieure. La leçon écrit à la main la recherche linéaire et la recherche dichotomique, qui, sur des données triées, écarte la moitié à chaque étape ; elle justifie la dichotomique par son invariant, prouve qu’elle termine, compte ses itérations et étudie les trois erreurs qui la ruinent. Suivent le tri par sélection et le tri par insertion, avec leurs invariants et le décompte exact de leurs comparaisons ; ensuite, les mêmes problèmes avec la bibliothèque de ranges, et le calcul qui décide quand il convient de trier avant de rechercher.

Objectifs d’apprentissage

  1. Implémenter la recherche linéaire et la recherche dichotomique, et justifier la dichotomique par son invariant (« si la valeur est présente, elle est entre low et high »), avec la preuve qu’elle termine.
  2. Implémenter le tri par sélection et le tri par insertion, énoncer l’invariant de chacun et compter leurs comparaisons dans le meilleur et dans le pire cas.
  3. Utiliser std::ranges::sort, std::ranges::contains, std::ranges::find, std::ranges::binary_search et std::ranges::lower_bound à la place des versions écrites à la main quand il le faut, en respectant leurs préconditions.
  4. Décider, selon le nombre de recherches prévues, s’il convient de trier les données avant d’y rechercher, et justifier la décision par le décompte des comparaisons.

Recherche linéaire

Rechercher, c’est répondre, étant donné une collection et une valeur, si la valeur est présente et où. Sans information sur l’ordre des données, il n’y a pas d’autre stratégie que de les regarder une par une : c’est la recherche linéaire. Quand la valeur est absente, ce cours renvoie values.size(), la première position qui n’appartient pas au vecteur : ce n’est pas un indice valide, de sorte qu’on ne le confond pas avec une réponse, et c’est la même convention que suit la bibliothèque, comme on le verra dans la cinquième section.

Programme en C++
#include <cstddef>#include <print>#include <vector>​// Précondition : aucune.// Postcondition : renvoie le plus petit indice i tel que values[i] == target,// ou values.size() si target est absent.std::size_t linearSearch(const std::vector<int>& values, int target){    // Invariant : target n’est pas dans values[0], ..., values[i - 1].    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{} : absent", target);        } else {            std::println("{} : position {}", target, pos);        }    }}
Sortie
207 : position 3112 : position 1999 : absent

L’invariant de la ligne 10 donne la correction. Au départ, avec i égal à 0, il affirme quelque chose sur une tranche vide et il est vrai. S’il est vrai au début d’une itération et que values[i] n’est pas la valeur cherchée, il est vrai à la fin de celle-ci avec un élément de plus. Or la boucle a deux sorties : si return i; s’exécute, values[i] est la valeur cherchée et, d’après l’invariant, aucun élément antérieur ne l’était, d’où i est la première occurrence (c’est pourquoi le 112, qui apparaît deux fois, est signalé à la position 1) ; si la boucle se termine par la condition, i vaut values.size() et l’invariant dit que la valeur n’est nulle part. Le return à l’intérieur de la boucle termine la fonction, et avec elle la boucle, et épargne un drapeau.

Le coût, au sens de la leçon Le coût d’un algorithme, se mesure par les comparaisons values[i] == target. Si la valeur est absente, on en fait exactement nn, une par élément : c’est le pire cas. Si elle est à la position pp, on en fait p+1p + 1. La recherche linéaire est donc O(n)O(n) : avec deux fois plus de données, deux fois plus de travail. Sans information supplémentaire, on ne peut pas faire mieux : un algorithme qui négligerait de regarder un élément ne saurait pas si la valeur s’y trouvait.