Program rendezesek; {rendezes.pas: 90.11.07}

(*

A Minimumkiválasztásos rendezés működésének

vizsgálata:

mozgatások "elméleti" minimuma/maximuma és

tényleges száma,

valamint átlagos értéke véletlenszerű sorozatokra.

*)

Uses

Newdelay,Crt;

Const

Meret=100; {a rendzendő elemek száma}

Ism=100; {a rendezés ismétlések száma

az átlagos hatékonyság "méréséhez"}

Type

TElem = Integer;

TIndex = 1..Meret;

TVektor= Array [TIndex] of TElem;

Var

a,b : TVektor; {a rendezendő és a tartalék sorozat}

rsz, {rendezések ismétlési száma}

csdb: LongInt; {elemcserék v. mozgatások száma}

sz : String;

atl : Real;

c : Char;

Min,

Max : LongInt;

Procedure Csere(Var x: TVektor; i,j: TIndex);

Var

s : TElem;

Begin

s:=x[i]; x[i]:=x[j]; x[j]:=s;

Inc(csdb,3);

End; {Csere}

Procedure Egyenes;

Var

i : TIndex;

Begin

For i:=1 to Meret do a[i]:=i;

End; {Egyenes}

Procedure Forditott;

Var

i : TIndex;

Begin

For i:=1 to Meret do a[i]:=Meret-i;

End; {Fordított}

Procedure RND_Permutal(Var x : TVektor);

Var

i,j,k : TIndex;

Begin

For i:=1 to Meret do

Begin

j:=Random(Meret)+1; Csere(x,j,i);

End;

For i:=1 to Meret do

Begin

j:=Random(Meret)+1; k:=Random(Meret)+1; Csere(x,j,k);

End;

End; {RND_Permutal}

Procedure Rendez(Var x : TVektor);

Var

i,j : TIndex;

mini: TIndex;

min : TElem;

Begin

csdb:=0;

For i:=1 to Meret-1 do

Begin

mini:=i; min:=x[i]; Inc(csdb);

For j:=i+1 to Meret do

Begin

If x[j]<min then

Begin

mini:=j; min:=x[j]; Inc(csdb);

End;

End;

x[mini]:=x[i]; x[i]:=min; Inc(csdb,2);

End

End; {Rendez}

Procedure EredmenyKiiras(cim: String; x : TVektor);

Var

i : TIndex;

Begin

ClrScr; Writeln(cim); GotoXY(1,5);

Writeln('Mozgatások száma:',csdb);

atl:=((rsz-1)*atl+csdb)/rsz;

Writeln(' Átlag:',atl:6:2);

Writeln(' Elméleti minimum:',Min:5);

Writeln(' - " - maximum:',Max:5);

{ Sound(1720); Delay(50);}

While Keypressed do

Begin

Delay(200);

For i:=1 to Meret do Write(x[i]:4);

Readln;

End;

NoSound;

End; {EredmenyKiiras}

Begin

Randomize;

{elméleti mozgatás-szám:}

Min:=3*Meret-3; Max:=3*Meret-3+Meret*Meret div 4;

atl:=0;

rsz:=1; {rendezésszám az 'egyenes' és a 'fordított' esethez}

Egyenes; b:=a; Rendez(b); EredmenyKiiras('Egyenes sorrend',a);

ReadKey;

Forditott; b:=a; Rendez(b); EredmenyKiiras('Fordított sorrend',a);

ReadKey;

For rsz:=1 to Ism do

Begin

Str(rsz:2,sz);

RND_Permutal(b); a:=b; Rendez(b); EredmenyKiiras('Random '+sz,a);

Delay(300); {lassítás}

End;

c:=ReadKey

End.