MÉTHODE DE TRI RAPIDE ( QUICK-SORT )
balgrim
Messages postés
52
Date d'inscription
vendredi 26 avril 2002
Statut
Membre
Dernière intervention
28 octobre 2003
-
11 nov. 2002 à 07:25
speletux Messages postés 30 Date d'inscription jeudi 31 mars 2005 Statut Membre Dernière intervention 6 février 2014 - 15 déc. 2005 à 22:52
speletux Messages postés 30 Date d'inscription jeudi 31 mars 2005 Statut Membre Dernière intervention 6 février 2014 - 15 déc. 2005 à 22:52
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/12212-methode-de-tri-rapide-quick-sort
https://codes-sources.commentcamarche.net/source/12212-methode-de-tri-rapide-quick-sort
15 déc. 2005 à 22:52
(extrait d'un logiciel de spéléo)
TSynclinalDatabase: objet correpondant au gestionnaire de BD du logiciel
GetCavite(Index): Extrait de la base de données la cavité numéro Index
PutCavite(Index, Cavite): Ecrit dans la base de données l'enregistrement Cavité à la position Index
Dans la ligne:
if (bidon1=ridx) then Exit;
mid:=(lidx+ridx) div 2;
Buffer:=GetCavite(lidx);
PutCavite(lidx, GetCavite(mid));
PutCavite(mid, Buffer);
e:=lidx;
for k:=1+lidx to ridx do begin
C1:=GetCavite(k);
C2:=GetCavite(lidx);
// tri sur les clés
bidon1:=C1.IDCavite;
bidon2:=C2.IDCavite;
if (bidon1<bidon2) then begin
Inc(e);
Buffer:=GetCavite(e);
PutCavite(e, GetCavite(k));
PutCavite(k, buffer);
end;
end;
Buffer:=GetCavite(lidx);
PutCavite(lidx, GetCavite(e));
PutCavite(e, Buffer);
QSortByKey(lidx, e-1);
QSortByKey(e+1, ridx);
end;
begin
AfficherMessage('Tri de la base');
if NbCavites=0 then Exit;
QSortByKey(0, NbCavites-1);
end;
17 mai 2004 à 12:38
Merci
12 nov. 2002 à 06:51
TJoueurInfo = record
Nickname: string;
Points : word;
end;
-------------------------
Procedure TJoueursList.TrieTab(VAR T : array of TJoueurInfo; Inf, Sup: WORD);
Procedure Swap(VAR S1, S2 : TJoueurInfo);
VAR Tmp: TJoueurInfo;
BEGIN
Tmp := S1 ;
S1 := S2 ;
S2 := Tmp ;
END;
VAR i,j:WORD;
BEGIN
IF Inf >= Sup THEN
ELSE BEGIN
i := Inf + 1 ;
j := Sup ;
While Not (i >= j) Do //i=j pour le cas où Sup=Inf+1
Begin
While Not (( T[i].Points > T[Inf].Points ) Or (i = j)) Do INC(i) ; //on cherche le 1er élément > T[Inf] à partir de la gauche
While Not (( T[j].Points < T[Inf].Points ) Or (j = i-1)) Do DEC(j) ; //on cherche le 1er élément < T[Inf] à partir de la droite
If i < j Then Swap(T[i], T[j]) ; //on les intervertit. Cette instruction pourrait être placée sans test juste après le WHILE
End;
If T[j].Points < T[Inf].Points Then Swap(T[Inf], T[j]) ; //on a donc ts les T<T[Inf] à gauche et les autres à droite
if j <> 0 then
TrieTab (T, Inf, j-1); //reste à trier la partie gauche
TrieTab (T, j+1, Sup) //et la partie droite
End;
END;
----------------------------------
Le paramètre Inf et Sup correspond à l'interval qui sera trié. Pour effectuer un trie complet on appelle donc la fonction avec ces paramètres:
TrieTab(UnTableau, 0, Count - 1);
L'algorithme utilisé est biensûr QuickSort mais présenté d'une autre manière.
11 nov. 2002 à 07:25