Principe : Fabriquer une liste de repères sur la liste afin, lors d'une recherche, de pouvoir sauter très rapidement au début de la zone de recherche et restreindre ainsi la recherche effective à une petite partie de la liste.
Exemple : La liste triée d'entiers
4 ; 12 ; 34 ; 44 ; 46 ; 52 ; 55 ; 59 ; 74 ; 88 ; 125 ; 148
se verrait dotée, pour une fréquence de 10, d'une liste d'index
0 ; 1 ; -1 ; 2 ; 3 ; 5 ; -1 ; 8 ; 9 ; -1 ;-1 ;-1 ; 10 ;-1 ; 11
signifiant que les unités commencent à l'indice 0, les dizaines à l'indice 1,
qu'il n'y a pas de vingtaines, les trentaines commencent à l'indice 2, ., les
cinquantaines commencent à l'indice 5, .
|
/* Indexation (dans la liste index
de taille longueur_index)de la liste triée tab
de taille longueur selon une fréquence d'index de freq
*/
|
| /* La taille de l'index est fonction de l'entier maximum dans tab*/ |
| longueur_index <== tab[longueur-1] / freq + 1 |
| /* Initialisation du tableau des index à -1 */ |
| Répéter pour i allant de 0 à longueur_index -1 |
| index[i] <== -1 |
| /* Passage de l'index */ |
| Répéter pour i allant de 0 à longueur - 1 |
| quotient <== tab[i] / freq |
| /* si non encore indexé */ |
| si index[quotient] = -1 |
| alors index[quotient] = i |
| fin_de_répéter |
|
/* Recherche de la place d'insertion
de x dans une liste triée tab de taille longueur
possédant une liste d'index index de taille longueur_index
(fréquence d'index de freq) */
|
| /* Si x est plus grand que tous */ |
| si x >= tab[longueur-1] |
| alors rendre(longueur) |
| /* Endroit du début de la recherche*/ |
| quotient <== x / freq |
| i <== quotient |
| tant_que (index[i] = -1) ET (i >=0) |
| i <== i - 1 |
| fin_tant_que |
| si i = -1 /* uniquement des -1 en début de l'index */ |
| alors debut <== 0 |
| sinon debut <== index[i] |
| /* Endroit de fin de la recherche*/ |
| i <== quotient |
| tant_que index[i] = -1 |
| i <== i + 1 |
| fin_tant_que |
| fin <== index[i] |
| /* Recherche de x entre debut et fin (recherche SIMPLE mais on pourrait faire une DICHOTOMIE car tab est triée) */ |
| i <== debut |
| tant_que (tab[i] < x) ET (i <= fin) |
| i <== i + 1 |
| fin_tant_que |
| rendre(i) |