MÉTHODE DE TRI RAPIDE ( QUICK-SORT )

Messages postés
52
Date d'inscription
vendredi 26 avril 2002
Statut
Membre
Dernière intervention
28 octobre 2003
- - Dernière réponse : speletux
Messages postés
31
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

Afficher la suite 
balgrim
Messages postés
52
Date d'inscription
vendredi 26 avril 2002
Statut
Membre
Dernière intervention
28 octobre 2003
-
ok, mais imaginont que ton array soit un array de type record, et que tu cherche à trier qu'une des valeur... g beau me creuser la tete je vois pas comment faire :s
cs_DeeJay
Messages postés
23
Date d'inscription
mercredi 17 avril 2002
Statut
Membre
Dernière intervention
23 décembre 2003
-
En voici la solution balgrim, ici on trie par le nombre de points un tableau de TJoueurInfo.
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.
Andy_24DB
Messages postés
4
Date d'inscription
samedi 8 mai 2004
Statut
Membre
Dernière intervention
27 décembre 2005
-
Mon prof de programmation théorique nous à même dit que c'était une variante du quicksort (mais basé sur le même principe)qui était utilisé par le moteur de recherche Google.

Merci
speletux
Messages postés
31
Date d'inscription
jeudi 31 mars 2005
Statut
Membre
Dernière intervention
6 février 2014
-
On peut même utiliser cet algo pour un fichier:
(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;