Tri par sélection / par insertion / à bulle // Recherche séquentielle et dichotomique

**WhiteTigerZ** · 09/04/2007, 11h20

Résumé de discussion Le 7/05
Le tri par selection :
Pour avoir une idée sur ce principe jete un coup d'oeil sur ce lien
http://darkskull.developpez.com/triselection/
et voila le code que j'ai fait

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
62
63
64
65
66
67
Program triselection ;
uses wincrt ;
type
   tab=array [1..20] of integer ;    
var
   n,x,p : integer ; t : tab ;
 
procedure saisie (var n : integer ; var t :tab );   
var
   i : integer ;   
begin 
 repeat
  writeln('Saisir la taille du tableau :');
  readln(n);
 until n in [5..20] ;
  For i:= 1 to n do                     
   begin
    repeat
     writeln('Saisir l''élément',i) ;
     readln(t[i]) ;
    until (t[i] > 0)   
   end;  
end;
 
function pos_max(n : integer ;t :tab; p :integer):integer ; 
var
   max,i : integer ;
Begin
     max:=p ;
 for i:= p to n do
  begin
   if t[i]>t[max] then
    max:=i ;
  end;
   pos_max:=max ; 
End;
 
procedure trie (n : integer ; var t :tab )   ;
var
   i,max,p : integer ;   
Begin  
 for i:= 1 to n-1 do
  begin   
   p:=pos_max(n,t,i);
   x:=t[i];
   t[i]:=t[p];
   t[p]:=x ;
  end;
End;  
 
procedure affiche (n : integer ; t :tab) ;
var
   i : integer ; 
Begin
 for i:= 1 to n-1 do
  begin
   write(t[i]);
   write('|');
  end;
   write(t[n]); 
End;
 
Begin       
 saisie(n,t); 
 trie(n,t);
 affiche(n,t);
End.

Le tri par insertion
Pour avoir une idée sur ce principe jete un coup d'oeil sur ce lien
http://lwh.free.fr/pages/algo/tri/tri_insertion.htm
et voila le code que j'ai fait

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
62
63
64
65
66
67
68
69
70
71
72
Program triinsertion ; 
uses wincrt ; 
type 
    tab=array[1..20] of integer ; 
var 
 n,x,i : integer ; t: tab ; 
 
procedure saisie (var n : integer ;var t:tab); 
var 
i : integer ; 
Begin 
 repeat 
  writeln('saisir la taille du tableau :'); 
  readln(n); 
 until n in [5..20]   ;  
  For i:= 1 to n do 
   begin 
    repeat 
     writeln('Saisir l''element ',i); 
     readln(t[i]); 
    until t[i] > 0 ; 
   end; 
End; 
 
function position (t:tab ; i : integer ): integer ; 
var 
   j : integer ; 
Begin 
 j:=0 ; 
  repeat 
   j:=j+1 ; 
  until t[j] >= t[i] ; 
 position:=j ; 
End; 
 
procedure tri(var t : tab ; n:integer ); 
var 
int,i,j,p : integer ; 
Begin 
 for i:=2 to n do 
  begin 
   p:=position(t,i); 
    if p <> i then 
     begin 
      int:=t[i] ; 
       for j :=i-1 downto p do 
        begin 
         t[j+1]:=t[j] ; 
        end; 
      t[p]:=int ; 
     end; 
  end;  
End; 
 
procedure affiche (var t :tab ; n : integer ); 
var 
   i:integer ; 
begin 
 for i:= 1 to n-1 do 
  begin 
   write(t[i]); 
   write('|'); 
  end; 
   write(t[n]); 
end; 
 
begin 
 saisie(n,t); 
 x:=position(t,i); 
 tri(t,n); 
 affiche(t,n); 
end.

Le Tri a bulle :
Pour avoir une idée sur ce principe jete un coup d'oeil sur ce lien
http://lwh.free.fr/pages/algo/tri/tri_bulle.htm
et voila le code que j'ai fait

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
program tri_tab;
uses wincrt; 
type 
     tab= array [1..25] of integer; 
var 
    t:tab; 
    n:integer; 
 
procedure saisie(var n:integer; var t:tab); 
var 
    i:integer; 
begin 
 repeat 
  writeln('donnner le nbre d''element du tableau'); 
  read(n); 
 until n in [5..25];
 
 For i:=1 to n do 
  begin 
   writeln('donner l''element ',i); 
   read(t[i]); 
  end; 
end; 
 
procedure tri(n:integer; var t:tab); 
var 
    verif:boolean; 
    i,x:integer; 
begin 
 repeat 
  verif:=true; 
   for i := 1 to n-1 do 
    begin 
     if t[i]>t[i+1] then 
      begin 
       x:=t[i]; 
       t[i]:=t[i+1]; 
       t[i+1]:=x; 
       verif:=false; 
      end; 
    end; 
 until verif=true; 
end; 
 
procedure affiche(n:integer; t:tab); 
var 
    i:integer; 
begin 
 write('| '); 
  for i:=1 to n do 
   begin 
    write(t[i],' | '); 
   end; 
end; 
 
BEGIN 
 saisie(n,t); 
 tri(n,t); 
 affiche(n,t); 
END.

- La recherche séquentielle qui consiste à parcourir une liste de valeur jusqu'à trouver la valeur cherchée ou atteindre la fin de la liste.
voila le programme que j'ai fait

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 sequentielle ;
uses wincrt ;
type
   tab = array [1..20] of integer ;
var
   t : tab ;
   n,e : integer ;
   x : boolean ;
 
procedure saisie ( var n,e : integer ;var t :tab);
var
   i : integer ;
begin
 repeat
  writeln('Saisir la taille du tableau :');
  readln(n);
 until n in [5..20];
  for i:= 1 to n do
   begin
    repeat
     writeln('Saisir l''élement ',i);
     readln(t[i]);
    until t[i] > 0 ;
   end;
    writeln('saisir un entier :');
    readln(e);
 end;
 
function existe (n,e : integer ; t :tab) : boolean ;
var
   i : integer ;
   verif : boolean ;
begin
 verif := false ;
 i:=1 ;
 repeat
  i:=i+1
 until (t[i]=e) or (i=n) ;
  if t[i]=e then verif:=true else verif:=false ; 
   existe:=verif ;
end;
 
begin
 saisie(n,e,t);
 x:=existe(n,e,t);
 if x=true then writeln(e,' existe dans le tableau') else if x=false then 
  writeln(e,' n''existe pas dans le tableau'); 
end.

La recherche dichotomique: qui consiste à chercher en subdivisant la série ordonnée en deux parties égales et vérifier dans quelle partie figurerait la valeur recherchée,puis réitérer ce processus
Voila le programme que j'ai fait

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 dichotomique ;
uses wincrt ;
type
   tab = array [1..20] of integer ;
var
   t : tab ;
   n,e : integer ;
   x : boolean ;
 
procedure saisie ( var n,e : integer ;var t :tab);
var
   i : integer ;
begin
 repeat
  writeln('Saisir la taille du tableau :');
  readln(n);
 until n in [5..20];
  for i:= 1 to n do
   begin
    repeat
     writeln('Saisir l''élement ',i);
     readln(t[i]);
    until t[i] > 0 ;
   end;
    writeln('saisir un entier :');
    readln(e);
end;
 
function existe (n,e : integer ; t :tab) : boolean ;
var
   i,bi,bs : integer ;
   x : boolean ;
begin
 x:=false ;
 bi:=1 ;
 bs:=n ;
  repeat n:=(bi+bs) div 2 ;
   if t[n] = e then
    x:=true
     else if t[n] < e then
      bi:=n+1 
       else bs:=n-1 ;
  until (x=true) or (bi >= bs) ;
end;
 
begin
 saisie(n,e,t);
 x:=existe(n,e,t);
 if x=true then writeln(e,' existe dans le tableau') else if x=false then 
 writeln(e,' n''existe pas dans le tableau'); 
end.

Salut tout le monde

,
voila je n'arrive par a faire un programme pascal qui puisse trier un tableau en ordre décroissant par le principe de trie par séléction
Si vous ne connaissez pas cet algorithme de trie par séléction cliquer sur ce lien
http://darkskull.developpez.com/triselection/
voila mon essai (e que j'ai pu faire)

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
62
63
64
65
66
67
68
Program triinsertion ;
uses wincrt ;
type
   tab=array [1..25] of integer ; 
var
   n : integer ; t : tab ;
 
procedure saisie (var n : integer ; var t :tab );
var
   i : integer ;
 
begin
 
 repeat
  writeln('Saisir le nombre d''éléments :');
  readln(n);
 until n in [5..25] ;
 
 For i:= 1 to n do
  begin
   repeat
    writeln('Saisir l''élément',i) ;
    readln(t[i]) ;
   until (t[i] < 30) and (t[i] > 0)
  end;
 
end;
 
 
function trie (n : integer ; t :tab ):integer   ;
var
   i,max,long,x : integer ;
 
begin
 
  long:=1 ;
  max:=0 ;
   repeat
    for i:= long to n-1 do
     begin
      if t[i] > t[max] then
      max:=i ;  
     end;
      x:=t[long] ;
      t[max]:=x ;
      t[long]:=t[max] ; 
      long:=long+1    
   until  long=n-1 ;
 
end;
 
procedure affiche (n : integer ; t :tab) ;
var
   i : integer ;
 
begin
 for i:= 1 to n-1 do
  begin
   write('"');
   write(t[i]);
  end;
end;
 
begin
saisie(n,t);
trie(n,t);
affiche(n,t);
end.

Merci d'avance pour vos réponses

**droggo** · 09/04/2007, 14h15

Hol,

Voici ton code avec mes remarques.

J'y ai ajouté ma version du tri

et de l'initialisation du tableau (tant que les codes de tri ou autre traitement ne sont pas au point, il est tout de même plus pratique d'avoir un remplissage automatique du tableau, plutôt qu'entrer n valeurs à chaque nouveau test).

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
Program triinsertion ;
uses wincrt ;
 
type
   tab=array [1..25] of integer ; 
var
   n : integer ; t : tab ;
 
procedure saisie (var n : integer ; var t :tab );
var
   i : integer ;
 
begin
 
 repeat
  writeln('Saisir le nombre d''éléments :');
  readln(n);
 until n in [5..25] ;
 
 For i:= 1 to n do
  begin
   repeat
    writeln('Saisir l''élément',i) ;
    readln(t[i]) ;
   until (t[i] < 30) and (t[i] > 0)
  end;
 
end;
 
procedure saisie2 (var n : integer ; var t :tab );
var
   i : integer ;
 
begin
 
 repeat
  writeln('Saisir le nombre d''éléments :');
  readln(n);
 until n in [5..25] ;
 
 For i:= 1 to n do
  begin
    t[i] := random(30);
  end;
 
end;
 
{ procedure trie (n : integer ; t :tab )  ;
  la procédure travaille sur une copie locale
  du tableau !! }
procedure trie (n : integer ; var t :tab )  ;
var
   i,max,long,x : integer ;
 
begin
 
  long:=1 ;
  { max:=0 ;
    alors que max sert à pointer dans le tableau
    dont les indices commencent à 1 }
   repeat
     // max = long, inutile de vérifier les indices < long,
     // supposés être triés
     max := long;
//    for i:= long to n-1 do
    for i:= long to n do
     begin
      if t[i] > t[max] then
      max:=i ;
     end;
{     ici, le swap est mal fait
      x:=t[long] ;
      t[max]:=x ;
      t[long]:=t[max] ; <== t[max] a été changé
 
      pour swapper A et B, il faut faire:
        tampon = A
        A = B
        B = tampon
}
      x := t[long];
      t[long] := t[max];
      t[max] := x;
      long:=long+1
   until  long=n-1 ;
 
end;
 
procedure trie2 (n : integer ; var t :tab );
var
  i,j,max,tamp  : integer;
begin
  for i:=1 to n-1 do
  begin
    { recherche indice du max }
    { on met max = i, pas besoin de chercher
      dans les indices < i, supposés être classés }
    max := i;
    for j := i+1 to n do
    begin
      if (t[j] > t[max]) then max := j;
    end;
    { si max <> i, on swappe les valeurs }
    if (max <> i)
    then
    begin
      tamp := t[i];
      t[i] := t[max];
      t[max] := tamp;
    end;
  end; { for i:=1 to n-1 do }
end;
 
 
procedure affiche (n : integer ; t :tab) ;
var
   i : integer ;
 
begin
 { pourquoi to n - 1 ?
 for i:= 1 to n-1 do   }
 for i:= 1 to n do
  begin
   write(' ');
   write(t[i]);
  end;
end;
 
begin
 randomize;
saisie2(n,t);
trie(n,t);
affiche(n,t);
 
readln; { pour avoir le temps de lire le résultat }
end.

Mon leitmotiv : l'indentation est presque bonne, pas assez régulière, pas mal de lignes vides qui n'ajoutent rien à la clarté du code.

**WhiteTigerZ** · 15/04/2007, 12h07

salut
j'ai pas jetter un coup d'oeil sur ton programme juste pour que le mien soit un peu original

j'ai lit les commentaires et je viens d'optimiser mon programme avec la declaration des variables locales et l'Imbrication de procédures

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
Program triinsertion ;
uses wincrt ;
type
   tab=array [1..25] of integer ; 
var
   n : integer ; t : tab ;
 
procedure saisie (var n : integer ; var t :tab );
var
   i : integer ;
 
begin
 
 repeat
  writeln('Saisir la taille du tableau :');
  readln(n);
 until n in [5..25] ;
 
 For i:= 1 to n do
  begin
   repeat
    writeln('Saisir l''élément',i) ;
    readln(t[i]) ;
   until (t[i] < 30) and (t[i] > 0)
  end;
 
end;
{La fonction pos_max vas chercher l'indice du plus grand élément }
function pos_max(n : integer ;t :tab; p :integer):integer ; 
var
   max,i : integer ;
Begin
max:=p ;
for i:= p to n do
 begin
  if t[i]>t[max] then
   max:=i ;
 end;
 pos_max:=max ; 
End;
{La procédure permut c'est celle qui va faire la pérmutation du plus grand élément par la case adéquate }
procedure permut(n : integer;t :tab; p : integer) ;
var
   i,x,max: integer ;
Begin
 max:=pos_max(n,t,p)  ;
 
 for i:= p to n-1 do
  begin
 
    x:=t[i];
    t[i]:=t[max];
    t[max]:=x ;
  end;    
 
End;
{la procedure trie est la procedure principale c'est celle qui va trier le tableau en ordre décroissant }
procedure trie (n : integer ; t :tab )   ;
var
   j,max,p : integer ;
 
begin
 
for j:= 1 to n-1 do
 Begin
 
    p:=pos_max(n,t,j);
    permut(n,t,p);
 
 End;
 
 
end;
 
procedure affiche (n : integer ; t :tab) ;
var
   i : integer ;
 
begin
 for i:= 1 to n-1 do
  begin
   write(t[i]);
   write('|');
  end;
  write(n);
end;
 
begin
saisie(n,t);
trie(n,t);
affiche(n,t);
end.

**droggo** · 15/04/2007, 13h14

Hol,

Je n'ai pas pris le temps de lire, mais, on y revient toujours:

Leitmotiv :
- faire une indentation régulière et cohérente.
- éviter les lignes vides qui ne servent pas clarifier le code
- par contre, en mettre là où c'est plus utile, par exemple entre 2 procédures/fonctions

Et bon point : plus d'utilisation de variables globales, c'est bien.

Envoyé par WhiteTigerZ

l'Imbrication de procédures

Où ça ?

S'il y en a, l'indentation devrait le montrer

**WhiteTigerZ** · 15/04/2007, 13h35

Envoyé par droggo

Hol,

Je n'ai pas pris le temps de lire, mais, on y revient toujours:

Leitmotiv :
- faire une indentation régulière et cohérente.
- éviter les lignes vides qui ne servent pas clarifier le code
- par contre, en mettre là où c'est plus utile, par exemple entre 2 procédures/fonctions

Et bon point : plus d'utilisation de variables globales, c'est bien.

Où ça ?

S'il y en a, l'indentation devrait le montrer

Salut
Le programme que je fait est faux !! la compilation est corecte mais l'execution est fausse

Il est difficile de trouver une erreur dans son code quand on la cherche.C'est encore bien plus dur quand on est convaincu que le code est juste

Ah ma tête il va s'exploser

**droggo** · 15/04/2007, 14h00

La,

Envoyé par WhiteTigerZ

Salut
Le programme que je fait est faux !! la compilation est corecte mais l'execution est fausse
Ah ma tête il va s'exploser

Je n'ai pas dit le contraire, je ne l'ai ni lu en détail, ni testé.

Mes remarques ne viennent que du "coup d'oeil", qui ne me donne pas envie de lire effectivement le code.

Et on y revient encore et toujours : la présentation du code est importante, l'indentation est importante, les commentaires sont importants, ...

Tri par sélection / par insertion / à bulle // Recherche séquentielle et dichotomique

Pascal

Vue hybride

Discussions similaires

Partager

Partager