Problème avec le quicksort

**relena93** · 12/06/2007, 15h50

bonjour
je fais un programme qui trie des elements dans un tableau, je me sert du quicksort
j'utilise un code pris dans
http://www.dailly.info/algorithmes-de-tri/rapide.php
( le pseudo code )
et enfaite mon programme ne marche pas et je ne comprend pas se qui va pas
merci pour votre aide

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
program trie_de_colone;
uses crt;
type tableau = array[1..4] of integer;
var
  choix, i : byte;
  tab : tableau;
 
procedure trier_tableau(tab_trie : tableau; debut, fin : integer);
   var
      pivot : integer;
 
   function partition (tab_part : tableau; premier, dernier : integer) : integer; 
      var
         cpt, pivot, swap, s : integer;
 
      BEGIN
         cpt := premier;
         pivot := tab_part[premier];
         for s := (premier + 1) to dernier do
            begin
               if tab_part[s] < pivot then
                  begin
                    {inc(cpt);}
                     swap := tab_part[cpt];
                     tab_part[cpt] := tab_part[s];
                     tab_part[s] := swap;
                     inc(cpt);
                 end;
            end;
 
        swap := tab_part[cpt];
        tab_part[cpt] :=tab_part[premier];
        tab_part[premier] := swap;
        partition := cpt;
      END;
 
   BEGIN
      if debut < fin then
         begin
            pivot := partition(tab_trie, debut, fin);
            trier_tableau(tab_trie, debut, (pivot - 1));
            trier_tableau(tab_trie, (pivot + 1), fin);
         end;
   END;
 
BEGIN
   clrscr;
   writeln('algo de trie');
   {tableau pour essayer}
   tab[1] := 4;
   tab[2] := 1;
   tab[3] := 3;
   tab[4] := 2;
   trier_tableau (tab,1 ,4);
   writeln('tableau final');
   for i := 1 to 4 do
      begin
         write(tab[i]);
         readln;
      end;
END.

**droggo** · 12/06/2007, 17h09

Jai,

Dans

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

procedure trier_tableau(tab_trie : tableau; debut, fin : integer);

la déclaration telles qu'elle est implique que la procédure travaille avec une copie locale du tableau.

Il faut déclarer comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

procedure trier_tableau(var tab_trie : tableau; debut, fin : integer);

du coup, je n'ai pas lu plus loin.

l

**relena93** · 12/06/2007, 17h33

j ai changer mais sa marche toujours pas

**droggo** · 12/06/2007, 18h35

Gie,

Il y a le même problème de copie locale dans

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

function partition (tab_part : tableau; premier, dernier : integer) : integer;

qu'il faut donc déclarer comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

function partition (var tab_part : tableau; premier, dernier : integer) : integer;

D'autre part, dans cette même procédure, il y a une erreur:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
               if tab_part[s] < pivot then
                  begin
                    {inc(cpt);}
                     swap := tab_part[cpt];
                     tab_part[cpt] := tab_part[s];
                     tab_part[s] := swap;
                     inc(cpt);
                 end;

il faut effectivement incrémenter cpt avant de faire le swap, comme tu l'avais fait au début.

Il faut donc faire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
               if tab_part[s] < pivot then
                  begin
                     inc(cpt);
                     swap := tab_part[cpt];
                     tab_part[cpt] := tab_part[s];
                     tab_part[s] := swap;
                 end;