Programmation Delphi algorithmes obligatoires

Tri par insertion

 Version itérative
1 procedure triInsertionI(var liste:TListBox); 2 var i,j:integer; 3 candidat:string; 4 termine:boolean; 5 begin 6 for i:=1 to liste.Items.Count−1 do begin 7 candidat:=liste.Items[i]; 8 j:=i; 9 termine:=false; 10 while (not termine) and (j>0) do 11 if liste.Items[j−1] > candidat then begin 12 liste.Items[j]:=liste.Items[j−1]; 13 j:=j−1 14 end 15 else termine:=true; 16 if j0 then begin 7 triInsertionR(liste,fin−1); 8 candidat:=liste.Items[fin]; 9 j:=fin; 10 termine:=false; 11 while (not termine) and (j>0) do 12 if liste.Items[j−1] > candidat then begin 13 liste.Items[j]:=liste.Items[j−1]; 14 j:=j−1 15 end 16 else termine:=true; 17 if j Dans l’algorithme précédent, l’appel récursif a lieu au début (ligne 7) du bloc d’instructions, avant les manipulations de la liste. Cela diffère de l’algorithme 3.1.2, où l’appel récursif a lieu à la fin du bloc d’instructions. On peut évidemment aussi implémenter le tri par insertion avec un appel récursif à la fin du bloc, comme l’illustre le code alternatif suivant :
1 procedure triInsertionR(var liste:TListBox; indiceCandidat:integer); 2 var j:integer; 3 candidat:string; 4 termine:boolean; 5 begin 6 if indiceCandidat0) do 11 if liste.Items[j−1] > candidat then begin 12 liste.Items[j]:=liste.Items[j−1]; 13 j:=j−1 14 end 15 else termine:=true; 16 if j 0 de la ligne 10, l’algorithme fonctionnerait même si l’on passe comme deuxième argument la valeur 0, mais il effectuerait alors quelques instructions superflues.)
3.3 Tri rapide (Quicksort) 3.3.1 Version récursive 1 procedure triRapide(var liste:TListBox; g,d:integer); 2 var i:integer; 3 begin 4 if g

Fonction auxiliaire « division »

1 function division(var liste:TListBox; g,d:integer):integer; 2 var i,j:integer; 3 pivot:string; 4 begin 5 pivot:=liste.Items[d]; 6 j:=d−1; 7 i:=g; 8 while i<=j do 9 if liste.Items[i]pivot then 12 j:=j−1 13 else begin 14 echange(liste,i,j); 15 i:=i+1; 16 j:=j−1 17 end; 18 echange(liste,i,d); 19 division:=i 20 end; La durée d’exécution du corps de la boucle while n’est pas optimale : lorsque l’indice j doit être diminué successivement plusieurs fois (ligne 12), le test à la ligne 9 est évalué chaque fois avant qu’on ne passe au test significatif de la ligne 11, alors que l’indice i n’a pas changé. Nous proposons au lecteur intéressé une version alternative de la fonction «division» : ? Onchoisitd’abordl’élémentdumilieudelalistecommepivotqu’onplaceàlaposition g. Cette première étape est facultative, mais elle permet quelquefois d’obtenir un pivot plus équilibré,surtoutlorsquelalisteàtrierestdéjàpresquetriée,outriéedansl’ordreinverse. ? Ensuite on examine tous les éléments de la liste depuis g +1 jusqu’à d en veillant à ce que les valeurs strictement inférieures au pivot soient toujours placées avant les valeurs supérieures ou égales au pivot. L’indice j indique constamment la position de la dernière valeur strictement inférieure au pivot dans la partie déjà traitée de la liste (ou j = g lorsqu’une telle valeur n’a pas encore été trouvée). ? Après la boucle, il suffit d’échanger le pivot avec l’élément à la position j pour placer le pivot au bon endroit.
function division(var liste:TListBox; g,d:integer):integer; 2 var i,j:integer; 3 pivot:string; 4 begin 5 echange(liste,g,(g+d) div 2); 6 pivot:=liste.Items[g]; 7 j:=g; 8 for i:=g+1 to d do 9 if liste.Items[i]i then echange(liste,j,i) 12 end; 13 if g<>j then echange(liste,g,j); 14 division:=j 15 end; Pour les listes à taille faible (d−g < 20), le tri par insertion devient généralement plus rapide que le tri rapide.

Algorithme de recherche

Par convention, les algorithmes de recherche suivants renvoient tous l’indice −1, lorsque la clé cherchée n’a pas été trouvée.
 Recherche séquentielle 1 function rechercheSeq(liste:TListBox; cle:string):integer; 2 var i:integer; 3 trouve:boolean; 4 begin 5 i:=0; 6 trouve:=false; 7 while (not trouve) and (i<liste.Items.Count) do 8 if liste.Items[i]=cle then 9 trouve:=true 10 else 11 i:=i+1; 12 if trouve then 13 rechercheSeq:=i 14 else 15 rechercheSeq:=−1 16 end;
 Recherche dichotomique
Version itérative 1 function rechDichoI(liste:TListBox; cle:string):integer; 2 var milieu,g,d:integer; 3 begin 4 g:=0; 5 d:=liste.Items.Count−1; 6 milieu:=(g+d) div 2; 7 while (cle<>liste.Items[milieu]) and (g<=d) do begin 8 if cle<liste.Items[milieu] then 9 d:=milieu−1 10 else 11 g:=milieu+1; 12 milieu:=(g+d) div 2 13 end; 14 if cle=liste.Items[milieu] then 15 rechDichoI:=milieu 16 else 17 rechDichoI:=−1 18 end; 4.2.2 Version récursive 1 function rechDichoR(liste:TListBox; cle:string; g,d:integer):integer; 2 var milieu:integer; 3 begin 4 if g>d then 5 rechDichoR:=−1 6 else begin 7 milieu:=(g+d) div 2; 8 if liste.Items[milieu]=cle then 9 rechDichoR:=milieu 10 else if cle<liste.Items[milieu] then 11 rechDichoR:=rechDichoR(liste,cle,g,milieu−1) 12 else 13 rechDichoR:=rechDichoR(liste,cle,milieu+1,d) 14 end 15 end; Appel de la fonction, pour rechercher dans toute la liste : … rechDichoR(liste, cle, 0, liste.Items.Count−1)…

Cours gratuitTélécharger le cours complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *