QuickSort algo lequel ?

Version imprimable

02/08/2005, 17h21
sony351

QuickSort algo lequel ?

bjr
j'essai de faire un tri de ma liste avec un algo QuickSort mais au final ma liste n'est pas bien rangée
j'ai utilisé ces algo là :
http://www.dailly.info/algorithmes-de-tri/rapide.php
ou
1: if r ≤ ℓ + 1 then
2: return Fini
3: end if
4: q ← ℓ, p ← r − 1
5: v ← a[r − 1].key
6: while p > q do
7: while a[p].key ≥ v and p > l do
8: p ← p − 1
9: end while
10: while a[q].key ≤ v and q < r − 1 do
11: q ← q + 1
12: end while
13: if p > q then
14: ´ Echanger a[p] et a[q]
15: end if
16: end while
17: Echanger a[q] et a[r − 1]
18: QuickSort(a, ℓ, q)
19: QuickSort(a, q + 1, r)

mais ça marche pas donc où récupérer le vrai quickSort ???
merci d'avance
02/08/2005, 19h12
Matthieu Brucher

Tu l'as fait dans quel langage et où est le code effectif que tu as utilisé ?

je développe sous borland c++ builder

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
bool MaClasse::QuickSort(int __fastcall Gauche, int __fastcall Droite)
{
  bool Fini = false;
 
  if(Droite > Gauche)
  {
    r = Droite;
    l = Gauche;
    q = l;
    p = r;
    AnsiString v = *((AnsiString *)Tableau->Items[r]);
    //AnsiString est un type qui permet de manipuler des chaines de caractères
    while(p > q)
    {
      while( (CompareText(*((AnsiString *)Tableau->Items[p]), v) >= 0) && (p > l) ) 
      //CompareText est une fonction de borland
      {
        p--;
      }
      while( (CompareText(*((AnsiString *)Tableau->Items[q]), v) <= 0) && (q < r) )
      {
        q++;
      }
 
      if(p > q)
      {
        Liste_Lignes->Exchange(p, q);
        //échange la position des pointeurs
      }
    }
    Tableau->Exchange(q, r);
    //échange la position des pointeurs
  }
  else
  {
    Fini = true;
  }
  return Fini;
}

ma liste n'est pas ordonée, bref je galère
merci beaucoup d'avance

03/08/2005, 17h20
Rafy
Tu devrai utiliser la librairie standard, il y a des truc déjà tout fait.....
Crée une liste std::list<int> (car apparemment c'est des int que tu veux trier)
et il y a une methode sort.
Code:

1 2 3 4 std::list<int> MyList; //... MyList.sort(); // Et voila
Je ne sais pas si la syntaxe est exacte je ne suis pas devant mon PC.
03/08/2005, 19h45
mathieu_t

Citation:

Envoyé par Rafy

Je ne sais pas si la syntaxe est exacte je ne suis pas devant mon PC.

Tu fais des posts par la force de l'esprit ?? :lol: :mouarf2:
04/08/2005, 08h47
Matthieu Brucher
Citation:
Envoyé par Rafy

Tu devrai utiliser la librairie standard, il y a des truc déjà tout fait.....
Crée une liste std::list<int> (car apparemment c'est des int que tu veux trier)
et il y a une methode sort.

Code:

1 2 3 4 std::list<int> MyList; //... MyList.sort(); // Et voila

Je ne sais pas si la syntaxe est exacte je ne suis pas devant mon PC.
Tout à fait d'accord, ça marche avec tout à partir du moment qu'il y a certains opérateurs de comparaisons définis.
04/08/2005, 10h47
sony351

//AnsiString est un type qui permet de manipuler des chaines de caractères
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
chaines de caractères est beaucoup plus lourd que int

mais merci pour l'info sur la déclaration d'un tableau de int (je savais pas comment en faisait)
05/08/2005, 10h55
Laurent Gomila

La suite ici :

http://www.developpez.net/forums/vie....php?p=2136120

Merci d'éviter de dupliquer les sujets à l'avenir.