Insertion dichotomique dans un fichier alphanumérique trié

L'ajout d'un élément dans un fichier trié ne doit pas obliger l'utilisateur à trier de nouveau ce dernier, surtout si ce fichier est important. On étudie ici une méthode rapide de d'insertion par dichotomie. Dans son principe, la méthode est semblable à celle présentée dans le recherche dichotomique d'un élément dans un fichier trié. Dans un fichier de 1 000 000 d'éléments, la place cherchée est trouvée au bout d'au plus n essais, n vérifiant 2ⁿ ≤ 10⁶, c'est à dire n × log₁₀

2 ≤ 6, soit n ≤ 20.

Le programme ci-dessous traite un fichier élèves de 25 fiches. JavaScript utilise l'ordre lexicographique (celui du dictionnaire). L'algorithme ne diffère que très peu du cas numérique. Le fichier est déclaré en entrée en tant que liste (instruction new Array).

En JavaScript, une liste commence au rang 0. Par convention, afin de gérer les début et fin de fichier, on note "AA" et "ZZ" les bornes inf (rang 0) et sup du fichier élève :

➔ Si, par exemple, on veut insérer un élève nommé Ali Baba, l'ordre lexicographique le placera en début de fichier entre "AA" et "Aymé Marcel"; le programme repère ce cas particulier et déclarera Ali Baba en tête de fichier.

L'algorithme d'insertion d'un élément x dans un fichier trié par ordre alphabétique croissant de n éléments noms[1], noms[2], ..., noms[n] consiste à rechercher un encadrement de ce dernier entre deux éléments consécutifs du fichier. On peut le résumer ainsi :

➔ Respecter les majuscules des noms : les lettres minuscules sont codées "après" les lettres majuscules : Dupont Jean sera inséré en place 10 alors que dupont Jean sera placé en fin de fichier !

<SCRIPT LANGUAGE=JavaScript>
var noms=new Array("AA","Aymé Marcel","AlTusi Mohamed","Balan Séverine","Baltard Victor","Bellini Amandine",
Cage Nicolas","Chamson André","Cournan Pauline","Darel Romain","Dusseaux René","Ferreau Manon","Ferré Léo",
"Gramme Frédéric","Han Mactu","Lavalette Marco","Merry Alicia","Napier John","Othon Marc","Ponge Francis",
"Radowsky Paulette","Rochelle Jean","Schubert Etienne","Soulié Mireille","Viard Corinne","ZZ")

var k="Morin Mathias",eff=noms.length
function ajout()
{
k=prompt("Quelle nom voulez-vous insérer ? ",k)
if(k==null){return}
a=0;b=eff;ok=0; // programme insertion dichotomique
while(b-a>1) // lorsque b-a = 1, le nom sera placé entre les rangs a et b.
{
t=Math.floor((a+b)/2)
if(k<noms[t]){b=t} else {a=t}
}
decal=b+1
for(i=eff+1;i>=decal;i--){noms[i]=noms[i-1]}; // décalage
noms[decal-1]=k;

affiche()
} // fin rech()

function affiche()
{
ap1=a+1;
if(ok==1){alert("Ce nom est déjà dans la table");return}
if(noms[a]=="AA"){alert("L'élève "+k+" a été inséré en première place");return}
if(noms[decal]=="ZZ"){alert("L'élève "+k+" a été inséré en dernière place");return}
alert("L'élève "+k+" a été inséré en place "+ap1+"\n"+"entre "+noms[a]+" et "+noms[decal]+".")
}
</SCRIPT>