Insertion dichotomique dans un fichier numérique trié

ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Insertion dichotomique dans un fichier numérique trié
» Insertion dichotomique dans un fichier alphanumérique trié | » Recherche dichotomique dans un fichier trié
» Liens analogiques Tri à bulles , Tri par insertion | Résolution dichotomique de l'équation f(x) = 0
» Pas de théorie, je veux utiliser le programme JavaScript

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 une série de nombres. Il est facilement adaptable à des chaînes de caractères alphanumériques. Il s'agit alors de l'ordre lexicographique (celui du dictionnaire) que JavaScript connaît fort bien.

Algorithme :

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

entrer les données triées table[1], table[2], ..., table[n]; entrer l'élément x à insérer;
initialisation : a = 1, b = n, flag = 0;
Le drapeau (flag) mis à 1 indiquera que l'élément à insérer est déjà présent (le programme accepte les doublons)
Tant que b - a > 1 faire (si b = a + 1, le nombre sera placé entre a et b.) :
   t = partie entière de (a + b)/2;
    si table[t] = x, alors flag = 1 (cas particulier : on décale tous les éléments à partir de t et x prend le rang t)
     sinon : si x < table[t] alors b = t sinon a = t;
    fin si
fin tant que
Décaler tous les éléments d'un rang à partir du rang b;
Insérer x au rang a + 1;

<SCRIPT LANGUAGE=JavaScript>
var table=new Array(),n=1000000,k=504.3
function classement()
{
for(i=1;i<=n;i++){table[i]=i};
k=eval(prompt("Cette table contient tous les entiers de 1 à 1 000 000"+"\n"+"Quelle nombre voulez-vous insérer ? ",k))
if(k==null){return}
a=1;b=n;ok=0; // programme insertion dichotomique
while(b-a>1) // lorsque b-a = 1, le nombre sera placé entre a et b.
{
t=Math.floor((a+b)/2)
if(table[t]==k){ok=1;break} // k existe déjà, on traite à part
else {if(k<table[t]){b=t} else {a=t}}
}
if (ok==1){decal=t+1} else {decal=b+1}
for(i=n+1;i>=decal;i--){table[i]=table[i-1]}; table[decal-1]=k; // décalage d'un rang vers la droite et insertion de k

affiche()
} // fin classement()

function affiche()
{
ap1=a+1;dbl=" ";
if(ok==1){ap1=t+1;a=t;decal=decal+1;dbl=" en doublon ";alert("Le nombre donné était déjà dans la table")}
alert("Le nombre "+k+" a été inséré"+dbl+"en place "+ap1+"\n"+"entre "+table[a]+" et "+table[decal])
}
</SCRIPT>