Algorithme du quicksort

Version imprimable

Bonjour,
Je dois faire un quicksort en pascal et j'ai des erreurs; seulement, tous ceux que je trouve sur le net ne sont pas comme dans mon cours. Je pense que le plus simple c'est que je vous montre le mien et vous nomme les erreurs.
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 41 program essai; type nbre=array[1..10]of integer; var deb,fin,indice,i,a:integer; procedure quicksort(var limite,deb,fin:integer;tab:nbre); var pivot,i,aux:integer; begin pivot:=tab[1]; limite:=fin; while limite<>i do begin if tab[i]<pivot then begin tab[i-1]:=tab[i]; i:=i+1; end; if tab[i]>pivot then begin aux:=tab[i]; tab[i]:=tab[limite]; tab[limite]:=aux; limite:=limite-1; end; end; tab[i]:=pivot; quicksort(limite-1,deb,tab); quicksort(fin,limite+1,tab); end; begin writeln('Entrez les nombres'); deb:=1; fin:=1; while tab[i]<=0 or i=10 do begin read(tab[i]; i:=i+1 fin:=fin+1 end; for a:=1 to fin end; quicksort(tab,limite,deb,fin); end.
Mes erreurs sont aux récursives à "limite-1", à coup sûr il le fera après pour le +1 et si j'enlève -1 pour voir si je n'ai pas une autre erreur sur cette ligne il m'inscrit "type mismatch" pour tab.
Merci à toute personne qui pourra m'aider.

21/10/2008, 20h20
Alcatîz

Bonjour,

Sans vouloir te froisser, il y a pas mal d'erreurs dans ton code. ;)

Celles qui concernent directement ta question sont les suivantes : tout d'abord, ta procédure quicksort nécessite 4 paramètres; dans les appels récursifs, tu n'en spécifies que 3.
Ensuite, le paramètre limite est transmis par adresse :

Code:

procedure quicksort(var limite,...

Lors de l'appel récursif, tu dois donc absolument transmettre comme paramètre une variable, pas le résultat d'une expression comme limite-1.

rectification

On ne peut pas me froisser en corrigeant mes erreurs, je me froisse toute seule. Il y en a, elles sont tellement énormes que je ferais mieux d'abandonner.
Je les corrige mais, comme j'ai du mal avec les récursives, le problème est que je vais avoir du mal à corriger la fonction; pour les erreurs trop bêtes ça va aller.

Le revoici un peu corrigé :

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
41
42
43
44
45
46
47
48
49
50
51
program essai;
 
uses crt;
 
type nbre=array[1..10]of integer;
 
var deb,fin,indice,a:integer;
    tab:nbre;
 
function quicksort(var limite,deb,fin:integer;tab:nbre):integer;
var pivot,i,aux:integer;
begin
  i:=deb;
  pivot:=tab[deb];
  while limite<>i do
    begin
      if tab[i]<pivot then
        begin
          tab[i-1]:=tab[i];
          i:=i+1;
        end;
      if tab[i]>pivot then
        begin
          aux:=tab[i];
          tab[i]:=tab[limite];
          tab[limite]:=aux;
        end;
    end;
  tab[i]:=pivot;
  quicksort:=(limite-1);
  quicksort:=(limite+1);
end;
 
var limite,i:integer;
 
begin
  clrscr;
  writeln('Entrez les nombres');
  deb:=1;
  fin:=1;
  i:=1;
  read(tab[i]);
  while (tab[i]>0) or (i=10) do
    begin
      i:=i+1;
      read(tab[i]);
      fin:=fin+1
    end;
  limite:=fin;
  quicksort(limite,deb,fin,tab);
end.

21/10/2008, 22h27
Alcatîz

Pour lire les 10 nombres au début, et généralement pour toute lecture sur le périphérique standard d'entrée, il est préférable d'utiliser readln au lieu de read.
Le test de fin de boucle doit également être modifié :

Code:

while (tab[i]>0) and (i<10) do

Pour le codage de l'algorithme lui-même, je pense que tu devrais partir d'un bon pseudo-code bien testé sur papier.

J'avoue que j'ai du mal à reconnaître ton algorithme. :oops: Dans le quicksort, à chaque exécution de la procédure récursive, il faut commencer par partager la partie de tableau à trier en deux parties en sélectionnant un pivot. Ensuite, il faut exécuter la procédure sur la partie de gauche puis la partie de droite.

Pour t'aider, des cours sont à ta disposition.
Par exemple : http://recursivite.developpez.com/?page=page_5#LIV-I

;)

Un grand merci

C'est réglé et il fonctionne, c'est génial, merci, merci.

Je vous le mets, vous verrez le grand ménage, mais votre lien a fait beaucoup.
ENCORE MERCI

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
41
42
43
44
45
46
47
48
program essai2;
uses crt;
var tab : array[1..10] of integer;
procedure QuickSort(debut, fin: integer);
var i,pivot, gauche, droite, temp: integer;
begin
  pivot := debut;
  gauche := debut;
  droite := fin;
  repeat
    if tab[gauche] >= tab[droite] then
    begin
      temp := tab[gauche];
      tab[gauche] := tab[droite];
      tab[droite] := temp;
      pivot := gauche + droite - pivot;
 
    end;
    if pivot = gauche then dec(droite) else inc(gauche);
  until gauche = droite;
  if debut < gauche - 1 then QuickSort(debut, gauche - 1);
  if fin > droite + 1 then QuickSort(droite + 1, fin);
end;
 
 
var a,deb,b, fin,limite,i:integer;
begin
clrscr;
writeln('Entrez les nombres');
deb:=1;
fin:=1;
i:=1;
read(tab[i]);
repeat
   begin
   i:=i+1;
   read(tab[i]);
   fin:=fin+1;
   b:=b+1;
   end;
until (tab[i]=0) or (i=10);
limite:=fin;
quicksort(deb,fin);
for a:=1 to b do
begin
writeln(tab[a]);
end;
end.

Jai,

Il est utile de prendre l'habitude de faire une présentation régulière et cohérente.

Petit exemple avec ton code:

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
program essai2;
 
uses crt;
 
var 
  tab: array[1..10] of Integer;
 
procedure QuickSort(debut, fin: Integer);
var 
  i, pivot, gauche, droite, Temp: Integer;
begin
  pivot := debut;
  gauche := debut;
  droite := fin;
  repeat
    if tab[gauche] >= tab[droite] then
    begin
      Temp := tab[gauche];
      tab[gauche] := tab[droite];
      tab[droite] := Temp;
      pivot := gauche + droite - pivot;
    end;
    if pivot = gauche then 
      Dec(droite) 
    else 
      Inc(gauche);
  until gauche = droite;
  if debut < gauche - 1 then 
    QuickSort(debut, gauche - 1);
  if fin > droite + 1 then 
    QuickSort(droite + 1, fin);
end;
 
var 
  a, deb, b, fin, limite, i: Integer;
begin
  clrscr;
  Writeln('Entrez les nombres');
  deb := 1;
  fin := 1;
  i := 1;
  Read(tab[i]);
  repeat
    begin
      i := i + 1;
      Read(tab[i]);
      fin := fin + 1;
      b := b + 1;
    end;
  until (tab[i] = 0) or (i = 10);
 
  limite := fin;
  quicksort(deb, fin);
  for a := 1 to b do
  begin
    Writeln(tab[a]);
  end;
end.

D'autre part, éviter les variables globales (tab dans ton code), c'est une très mauvaise habitude (passer toutes les données nécessaires à une fonction/procédure en paramètres).

Et de plus, il serait utile de décomposer le tout en différentes fonctions/procédures (pourquoi l'avoir fait pour le tri, et pas pour remplir le tableau, pour l'afficher ?).

:)