Discussion :

[clochette71]

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 :

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
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.

[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 :

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

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.

[clochette71]

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 :

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
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.

[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 :

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

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. 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

[clochette71]

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 :

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
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.

[droggo]

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 :

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
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 ?).