Le problème d’accès à un élément d’un ensemble, classique en gestion, est formulé habituellement de deux manières:
- Soit on connait la position de l’élément à trouver, on recherche , depuis le début de l’ensemble jusqu’au ixième élément.
- Soit on ne connait pas la position de l’ élément et l’on recherche le premier élément dont la valeur est la valeur donnée.
On distingue donc deux types de recherche dans une file séquentielle:
- Un accès par position
- Un accès par valeur ou associatif
Accès Associatif
On veut parcourir un ensemble depuis le début pour trouver le plus petit index d’une élément dont on cherche une valeur égale à une valeur donnée. Le schéma de programme est un prédicat délivrant Vrai si la valeur choisie appartient à l’ensemble des valeurs de la file, Faux sinon.
Objectif: Recherche par valeur lors d'un parcours séquentiel d'un ensemble d'éléments non triés. Lecture de tous les éléments de l'ensemble Elément: L'élément valeur est de type Element Ensemble L'élément ensemble est de type Ensemble Remarque: L'ensemble n'est pas modifié Résultat: l'algorithme retourne Vrai si le valeur est trouvée Faux sinon
Algorithme générique de recherche dans un ensemble non trié:
rechercheParValeur ensemble Ensemble, valeur Element -> Bool existe <- Faux Premier(ensemble) Enumerer ensemble ET NON existe element >- Prendre(ensemble) existe <- Egal(valeur,element) Suivant(ensemble) Fin <- existe Fin
L’élément existe indique que l’on a trouvé une valeur correspondant à la condition de recherche. La cohérence du schéma est assurée par l’initialisation de existe à Faux avant le test d’itération. Ceci permet de ne pas entrer dans la boucle itérative si l’ensemble est vide. Par conséquent l’instruction Prendre ne sera exécutée que si la variable existe a la valeur Faux.
Si l’on considère une file dont les éléments sont munis d’une relation d’ordre, le schéma ci-dessus peut être optimisé. Les deux principales relation d’ordre couramment utilisées sont représentées par:
- une fonction croissante, l’ensemble est ordonné en ordre croissant
- une fonction décroissante, la file est ordonnée en ordre décroissant
Dans le cas de l’accès associatif la relation d’ordre permet d’éviter un énumération complète des éléments de l’ensemble pour trouver une occurrence de la valeur cherchée.
Note: Dans cette version l’instruction Prendre_Element rend l’élément courant et se positionne sur l’élément suivant. Cette instruction remplace Prendre et économise l’emploi de Suivant, intégré dans la fonction Prendre_Element.
rechercheParValeur ensemble Ensemble, valeur Element -> Bool existe <- Faux parcours <- Vrai Premier(ensemble) Enumerer ensemble ET NON existe ET parcours element >- Prendre_Element(ensemble) Si valeur < element parcours <-Faux Sinon existe <- valeur = element Fin <- existe Fin
Traduction proposée par le compilateur Schema pour le langage Swift:
func RechercheParValeur <Element>(_ ensemble: Ensemble<Element>,_ valeur: Element) -> Bool { var existe = false var parcours = true Premier(ensemble) while Enumeration(ensemble) && !existe && parcours { let element = Prendre_Element(ensemble) if valeur < element {parcours = false}else{existe = valeur == element} } return existe }
Les fonctions Premier, Enumeration, Prendre_Element sont codées en Swift, et sont intégrées dans la librairie du langage Schema
Article suivant: Cet article propose plusieurs algorithmes de recherche d’un élément dans un ensemble itérable, trié ou non trié
copyright A rchitectures A pplicatives A vancées A3-Soft