Exercice pascal"trie"

On utilise le tri à bulle !
voici une analyse :

procedure Tri (var T:vecteur ; x:entier )

[test <-- faux] Répéter
pour i de 1 à (n-1) faire
si T[i] > T[i+1] alors
x <-- T[i]
T[i] <-- T[i+1]
T[i+1] <-- x
test <-- vrai
finsi
finpour
Jusqu'à (test = faux)

salue;
Autres résultats, domaine www.commentcamarche.net »

comment avoir les solutions d'un probleme d'Algorithme.
Comment le site fonctionne merci.

Le tri par fusion est le meilleur en efficacité (pour 100 000 données on a 600 000 comparaisons).
Le tri par bulle est le pire (pour 100 000 données on a 10 000 000 000 comparaisons).

Voici deux corrigés d'unités que mon prof a fait cette année...

La première définit le type de tableaux que l'on va utiliser :

unit tableau_elem;

interface

type element = real; // pour le modifier il faut aussi modifier Afficher

const nmax = 100;
type tableau = array [1..nmax] of element;

// affiche n éléments du tableau depuis le p-ième
procedure Afficher (var t: tableau; n, p: integer);

// teste si les n premiers éléments d'un tableau sont par ordre croissant
function Croissant (var t: tableau; n: integer): boolean;

implementation

const larg = 5; // largeur d'affichage d'un élément
const prec = 1; // nombre de decimales

procedure Afficher (var t: tableau; n, p: integer);
var i: integer; begin
   for i := 1 to p-1 do write(' ' : larg);
   for i := p to p+n-1 do write(t[i] : larg : prec);
   writeln
end;

function Croissant (var t: tableau; n: integer): boolean;
var i: integer; begin
   result := false;
   for i := 1 to n-1 do if t[i] > t[i+1] then exit;
   result := true;
end;

begin end.

La deuxième unité concerne le tri sur les tableaux (dont le type est définit dans la première)

unit tri_fusion;

interface

uses tableau_elem;
procedure Trier (var t: tableau; n: integer);

implementation

// copie une zone  de src (source) dans dst (destination).
procedure Copier (var src, dst: tableau; n, p, q: integer);
var i: integer;
begin
   for i := 0 to n - 1 do dst[q + i] := src[p + i]
end;

// fusionne 2 zones de src (source) dans dst (destination).
// elles doivent être déjà triées par ordre croissant.
// Une version récursive terminale

procedure Fusionner (var src, dst: tableau; n1,p1, n2,p2, q: integer);
begin
   if n2 = 0 then
      Copier(src, dst, n1, p1, q)
   else if n1 = 0 then
      Copier(src, dst, n2, p2, q)
   else
   // cas général
   if src[p1] <= src[p2] then begin
      dst[q] := src[p1];
      Fusionner(src, dst, n1-1, p1+1, n2, p2, q+1)
   end else begin
      dst[q] := src[p2];
      Fusionner(src, dst, n1, p1, n2-1, p2+1, q+1)
   end
end;


// Une autre version, itérative

procedure Fusionner_v2 (var src, dst: tableau; n1,p1, n2,p2, q: integer);
begin
   while (n1 > 0) and (n2 > 0) do begin
      if src[p1] <= src[p2] then begin
         dst[q] := src[p1]; inc(q); inc(p1); dec(n1);
      end else begin
         dst[q] := src[p2]; inc(q); inc(p2); dec(n2);
      end
   end;
   
   if n1 > 0 then
      Copier(src, dst, n1, p1, q)
   else
      Copier(src, dst, n2, p2, q)
end;


// Comme Fusionner_v2, avec p[1], p[2] au lieu de p1, p2

procedure Fusionner_v3 (var src, dst: tableau; n1,p1, n2,p2, q: integer);
var n, p: array[1..2] of integer;
var lequel: integer;
begin
   n[1] := n1; p[1] := p1;
   n[2] := n2; p[2] := p2;
   
   while (n[1] > 0) and (n[2] > 0) do begin
      if src[p[1]] <= src[p[2]] then lequel := 1 else lequel := 2;
      dst[q] := src[p[lequel]];
      inc(q);
      inc(p[lequel]);
      dec(n[lequel]);
   end;
   
   if n[1] > 0 then lequel := 1 else lequel := 2;
   Copier(src, dst, n[lequel], p[lequel], q)
end;

// tab est le tableau à trier; tmp un tableau temporaire.
// trie par ordre croissant n éléments à partir du p-ième.
procedure TrierRec (var tab, tmp: tableau; n, p: integer);
var n1, n2, p1, p2: integer;
begin
   if n > 1 then begin
      // write('TrierRec(', n:2, ',', p:2,'): Avant: '); Afficher(tab, n, p);
      n1 := n div 2;
      n2 := n - n1;
      p1 := p;
      p2 := p + n1;
      TrierRec(tab, tmp, n1, p1);
      TrierRec(tab, tmp, n2, p2);
      Copier(tab, tmp, n, p, p);
      Fusionner(tmp, tab, n1, p1, n2, p2, p);
      // write('TrierRec(', n:2, ',', p:2,'): APRES: '); Afficher(tab, n, p);
   end
end;

procedure Trier (var t: tableau; n: integer);
var tmp: tableau;
begin
   TrierRec(t, tmp, n, 1)
end;

begin end.

C'est très indigeste, mais d'un point de vue efficacité y a pas photo !

ps: faisant confiance à mon prof, on va dire que y a pas de faute... Et sinon cherchez l'erreur !

Merçi frangin pour ton aide.je tiendrais compte de la remarque la prochaine fois.porte toi bien. tchao

aide pour solution de l'exercice suivant en pascal.
exo:Ecrire une fonction Kchiffre qui prend en entrée un nombre entier n et un nombe entier k et renvoie le k ième chiffre(à partir de la droite) du nombre n si k est inferieur ou égal au nombre de chiffre n sinon renvoie -1

{de +}
procedure trie_par_selection(var t:tab ; n:integer);
var
i,j,y,m:integer;
begin
for i := 1 to n-1 do
begin
m:=i;

for j := i to n do
begin
if t[j]<t[m] then
begin
y:=t[i];
t[i]:=t[m];
t[m]:=y;
n:=n-1;
end;
end;

end;
end;

bonjour svp^aidez moi j veu ecrire un program en turbo pascal qui fai un tri a bulles d un vecteur dans l ordre croissanrt pour demain c est urgent et merci

salut dans le programe, et avant de mettre les 'var', vou mettez : type t=array[1..20] of integer; et puis tu termine ton program ...

Je veux voir la réponse
plz .. plz

bonjour
je un problem :
ecrire un program en pascal qui cherche la 1ere position d'une valeur v dans un tableau b de n réel . l'entier n est 5<n<30.
specification du problem et le algoritme :!!!
plz ..plz mnt .
et merci
dorssaf d'akouda

la plus plus simple methode c le trie par selection
un autre tab
parcour de tab en cherchan le min
le metre dans le 2emme tab

svp l'algorithme du tri shell

salut je cherche une methode de tri par shell (algo recursive) **sombol**

qui peut m'aider a resoudre l'exercice suivant:
ecrire une fonction recursive booleene qui détermine si une chaîne de caractéres ch comporte plus de caractères c1 que de caractères c2(cette fonction retourne vrai si le nombre de c1 est supérieur à celui de c2)

Salut
voila une methode recursive de tri par selection
procedure permuter( var x, y : integer);
var z : integer;
begin
z:=x;
x:=y;
y:=z;
end;

function posmin ( t: vect; d,f : integer): integer;
var pm : integer;
begin
if d= f then posmin := d
else
begin
pm := posmin(t,d+1,f);
if t[d]<t[pm] then posmin:= d
else posmin:=pm;
end;
end;

procedure trier ( var t : vect; d,f: integer);
var pm : integer;
begin
if d<>f then
begin
pm := posmin(t,d,f);
if d<>pm then permuter(t[d],t[pm]);
trier(t,d+1,f);
end;
end;

program trie;
uses wincrt;
type
tab=array [1..20]of integer;
var
t:tab;
n:integer;
procedure saisie (var t:tab ,n:integer);
begin
repeat

readln (n);
until n>20
end;
procedure tri ( var t:tab,n:integer);
var
i:integer;
begin
for i :=1 to n do
begin
if t[i]<t[i+1] then
begin
permuter (t[i],t[i+1])
end;
end;

MERCI POUR VOS AIDE A+

il sagie plusieures metodes de trie :
program trie;
uses wincrt;
var
y,k:integer;
begin
repeat
k=false;
for i:=1 to n-1 do
begin
if t[i]>t[i+1] then
begin
t:=t[i];
end
else
t[i]:= t[i+1];
k:=true;
end;
until (k=false);
end;