Rendezések

Feladat

Rendezési algoritmusok kipróbálása, hatékonysági viselkedésének vizsgálata.

A rendezések egy ElemSzam méretü r tömben történik.

Többféle föltöltés közül lehet választani:

o a növekvően / csökkenően rendezettől,

o a majdnem rendezetten át,

o véletlenszerüen kitöltöttig.

A föltöltés nemcsak az r-re vonatkozik, hanem az s-re is. Ez használható föl a további rendezések kiinduló értékének beállítására.

Keretprogram

Program RendezesKeret;

{

Rendezési algoritmusok kipróbálásához keret.

A rendezések egy ElemSzam méretü r töműben történjen.

Többféle föltöltés közül lehet választani:

- a növekvően / csökkenően rendezettől,

- a majdnem rendezetten át,

- véletlenszerüen kitöltöttig.

A föltöltés nemcsak az r-re vonatkozik, hanem az s-re is.

Ez használható föl a további rendezések kiinduló értékének

beállítására.

}

Uses

Newdelay,Crt,Dos;

Const

MaxN=1000;

Type

TElem=Integer;

TSorozat=Array[1..MaxN] of TElem;

Var

Kezdet,Veg,

ElteltIdo: LongInt;

s,r : TSorozat; {A föltöltések mindkettőt beállítják,

a rendezések az r-t rendezik.}

ElemSzam : Integer;

{$I RENDMENU.PAS}

{

Ebben a file-ban található a rendezéshez szükséges menüző program.

Számunkra érdekes most ebből mindössze:

- Menuzes(FoMenu), amely beindítja a párbeszédet és hívogatja

a megfelelő rendező eljárásokat.

- TombKiir, amely az r tartalmát oszloposan megjeleníti a képernyőn.

}

Procedure OraIndul;

Var

o,p,mp,szmp: Word;

ol: LongInt;

Begin

GetTime(o,p,mp,szmp); ol:=o; {konverzió LongInt-té}

Kezdet:=szmp+100*(mp+60*(p+60*ol{konverzió LongInt-té}))

End; {OraIndul}

Procedure OraAll;

Var

o,p,mp,szmp: Word;

ol: LongInt;

Begin

GetTime(o,p,mp,szmp); ol:=o; {konverzió LongInt-té}

Veg:=szmp+100*(mp+60*(p+60*ol{konverzió LongInt-té}));

ElteltIdo:=Veg-Kezdet

End; {OraAll}

Procedure Kiirasok(cim: String);

Var

i: Integer;

Begin

ClrScr;

TombKiir(cim);

Writeln; Writeln('Eltelt idő:',ElteltIdo, ' századmásodperc.')

End; {Kiirasok}

Procedure EgyszeruCseres;

Begin

OraIndul;

{itt van az r rendezése}

OraAll;

Kiirasok('Egyszerü cserés');

r:=s; {Az eredeti értéket visszaállítja}

End; {EgyszeruCseres}

Procedure MinimumKivalasztasos;

Begin

OraIndul;

{itt van az r rendezése}

OraAll;

Kiirasok('Minimumkiválasztásos');

r:=s; {Az eredeti értéket visszaállítja}

End; {MinimumKivalasztasos}

Procedure Buborek;

Begin

OraIndul;

{itt van az r rendezése}

OraAll;

Kiirasok('Buborék');

r:=s; {Az eredeti értéket visszaállítja}

End; {Buborek}

Procedure JavitottBuborek;

Begin

OraIndul;

{itt van az r rendezése}

OraAll;

Kiirasok('Javított buborék');

r:=s; {Az eredeti értéket visszaállítja}

End; {JavitottBuborek}

Procedure Beilleszteses;

Begin

OraIndul;

{itt van az r rendezése}

OraAll;

Kiirasok('Beillesztéses');

r:=s; {Az eredeti értéket visszaállítja}

End; {Beilleszteses}

Begin

ClrScr;

Randomize; {Mindig véletlenszerű kezdőérték}

ElemSzam:=100; {Opcionális méret}

Menuzes(FoMenu);

End.

RendMenu.pas – include-állomány

{$f+ a saját eljárások, függvények kezeléséhez igényli a TURBO PASCAL}

Const

MaxDb = 6;

Type

MenuPont = Record

kerdes: String;

sorsz : Byte;

tevek : Procedure;

segit : Word;

End;

Menu = Record

cim: String;

db : Byte;

am : Array [1..MaxDb] of MenuPont;

bfx,bfy: Byte;

End;

Procedure Varakozas; Forward;

Procedure Ures; Forward;

Procedure AblakRajzolas(bfx,bfy,hossz,szel: Byte); Forward;

Procedure Menuzes(m: Menu); Forward;

Procedure Vege; Forward;

{

Menüdeklaráció:

}

Procedure Menu1; Forward; {Parmétermenü}

Procedure Menu2; Forward; {Rendezések menüje}

Procedure Menu3; Forward; {Föltöltések menüje}

Procedure Menu1_1; Forward; {Az egyes rendezéseket hívó eljárás}

Procedure Menu1_2; Forward; {Az egyes rendezéseket hívó eljárás}

Procedure Menu1_3; Forward; {Az egyes rendezéseket hívó eljárás}

Procedure Menu1_4; Forward; {Az egyes rendezéseket hívó eljárás}

Procedure Menu1_5; Forward; {Az egyes rendezéseket hívó eljárás}

Procedure FeltoltNovekedve; Forward;

Procedure FeltoltCsokkenve; Forward;

Procedure FeltoltAzonossal; Forward;

Procedure FeltoltVeletlennel; Forward;

Procedure FeltoltMajdnemRendezve; Forward;

{

Segéd globális eljárás:

}

Procedure TombKiir(cim: String); Forward;

{

A megirandó rendezések:

}

Procedure EgyszeruCseres; Forward;

Procedure MinimumKivalasztasos; Forward;

Procedure Buborek; Forward;

Procedure JavitottBuborek; Forward;

Procedure Beilleszteses; Forward;

{

Menüleírótábla deklarációja:

}

Const

FoMenu : Menu=(cim: 'Főmenü';

db : 4;

am : ((kerdes:'Paramétermegadás';sorsz:1;tevek:Menu1;segit:1),

(kerdes:'Feltöltés';sorsz:1;tevek:Menu3;segit:3),

(kerdes:'Rendezési módszer';sorsz:1;tevek:Menu2;segit:2),

(kerdes:'Vége'; sorsz:1;tevek:Vege;segit:99),

(kerdes:'';sorsz:0;tevek:Ures;segit:0),

(kerdes:'';sorsz:0;tevek:Ures;segit:0));

bfx: 10;

bfy: 5);

Al1Menu: Menu=(cim: 'Rendezések';

db : 6;

am : ((kerdes:'Egyszerü cserés';sorsz:1;tevek:Menu1_1;segit:4),

(kerdes:'Minimumkiválasztásos';sorsz:1;tevek:Menu1_2;segit:5),

(kerdes:'Buborék';sorsz:1;tevek:Menu1_3;segit:6),

(kerdes:'Javított buborék';sorsz:1;tevek:Menu1_4;segit:7),

(kerdes:'Beillesztéses';sorsz:3;tevek:Menu1_5;segit:8),

(kerdes:'Vége'; sorsz:1;tevek:Vege;segit:99));

bfx: 10;

bfy: 5);

Al2Menu: Menu=(cim: 'Föltöltések';

db : 6;

am : ((kerdes:'Növekedően';sorsz:1;tevek:FeltoltNovekedve;segit:7),

(kerdes:'Csökkenően';sorsz:1;tevek:FeltoltCsokkenve;segit:8),

(kerdes:'Azonosakkal';sorsz:1;tevek:FeltoltAzonossal;segit:9),

(kerdes:'Véletlennel';sorsz:3;tevek:FeltoltVeletlennel;segit:10),

(kerdes:'Majdnem rendezve';
sorsz:1;tevek:FeltoltMajdnemRendezve;segit:11),

(kerdes:'Vége'; sorsz:1;tevek:Vege;segit:99));

bfx: 10;

bfy: 5);

{

Menütevékenységek deklarációja:

}

Procedure Menu1;

Var

HolX: Integer;

Begin

AblakRajzolas(1,1,24,79);

Repeat

GotoXY(20,12); Write('Tömbméret (100..',MaxN,'):'); HolX:=WhereX;

Write(' ');

GotoXY(HolX,12); Readln(ElemSzam)

Until (ElemSzam>=100) and (ElemSzam<=MaxN);

ClrScr;

End; {1.Menü}

Procedure Menu2;

Begin

AblakRajzolas(1,1,24,79);

Menuzes(Al1Menu);

End; {2.Menü}

Procedure Menu3;

Begin

AblakRajzolas(1,1,24,79);

GotoXY(38,12);

Menuzes(Al2Menu);

End; {3.Menü}

Procedure Menu1_1;

Begin

AblakRajzolas(1,1,24,79);

GotoXY(28,12);

Writeln('Egyszerü cserés rendezés');

Window(2,2,78,23); {Az aktív ablakterület}

EgyszeruCseres;

Varakozas

End; {1.1.Menü}

Procedure Menu1_2;

Begin

AblakRajzolas(1,1,24,79);

GotoXY(26,12);

Writeln('Minimumkiválasztásos rendezés');

Window(2,2,78,23); {Az aktív ablakterület}

MinimumKivalasztasos;

Varakozas

End; {1.2.Menü}

Procedure Menu1_3;

Begin

AblakRajzolas(1,1,24,79);

GotoXY(36,12);

Writeln('Buborék');

Window(2,2,78,23); {Az aktív ablakterület}

Buborek;

Varakozas

End; {1.3.Menü}

Procedure Menu1_4;

Begin

AblakRajzolas(1,1,24,79);

GotoXY(32,12);

Writeln('Javított buborék');

Window(2,2,78,23); {Az aktív ablakterület}

JavitottBuborek;

Varakozas

End; {1.4.Menü}

Procedure Menu1_5;

Begin

AblakRajzolas(1,1,24,79);

GotoXY(36,12);

Writeln('Beillesztéses');

Window(2,2,78,23); {Az aktív ablakterület}

Beilleszteses;

Varakozas

End; {1.5.Menü}

Procedure FeltoltNovekedve;

Var

i: Integer;

Begin

AblakRajzolas(1,1,24,79);

s[1]:=Random(ElemSzam);

For i:=2 to ElemSzam do

Begin

s[i]:=s[i-1]+Random(3)

End;

r:=s;

TombKiir('Föltöltés növekedve');

Varakozas

End; {FeltoltNovekedve}

Procedure FeltoltCsokkenve;

Var

i: Integer;

Begin

AblakRajzolas(1,1,24,79);

s[1]:=Random(ElemSzam);

For i:=2 to ElemSzam do

Begin

s[i]:=s[i-1]-Random(3)

End;

r:=s;

TombKiir('Föltöltés csökkenve');

Varakozas

End; {FeltoltCsokkenve}

Procedure FeltoltAzonossal;

Var

i: Integer;

Begin

AblakRajzolas(1,1,24,79);

s[1]:=Random(ElemSzam);

For i:=2 to ElemSzam do

Begin

s[i]:=s[i-1]

End;

r:=s;

TombKiir('Föltöltés azonosakkal');

Varakozas

End; {FeltoltAzonossal}

Procedure FeltoltVeletlennel;

Var

i: Integer;

Begin

AblakRajzolas(1,1,24,79);

For i:=1 to ElemSzam do

Begin

s[i]:=Random(ElemSzam)

End;

r:=s;

TombKiir('Föltöltés véletlenekkel');

Varakozas

End; {FeltoltVeletlennel}

Procedure FeltoltMajdnemRendezve;

Var

i,j,k: Integer;

seged: TElem;

Begin

AblakRajzolas(1,1,24,79);

s[1]:=Random(ElemSzam);

For i:=2 to ElemSzam do

Begin

s[i]:=s[i-1]+Random(3)

End;

For i:=1 to ElemSzam Div 10 do

Begin

j:=Random(ElemSzam);

Repeat

k:=Random(ElemSzam)

Until k<>j;

seged:=s[j]; s[j]:=s[k]; s[k]:=seged;

End;

r:=s;

TombKiir('Föltöltés majdnem rendezve');

Varakozas

End; {FeltoltMajdnemRendezve}

{

Menüdeklaráció vége

}

Procedure TombKiir(cim: String);

Var

i: Integer;

Begin

Window(1,1,80,25); {Az aktív ablakterület}

GotoXY(((80-length(cim)) Div 2)+2,1);

HighVideo; Write(cim); Lowvideo;

Window(2,2,78,23); {Az aktív ablakterület}

For i:=1 to ElemSzam do

Begin

NormVideo; Write(i:5,':'); HighVideo; Write(r[i]:5);

End;

End; {TombKiir}

Procedure Varakozas;

Var

c: Char;

Begin

Window(1,1,80,25); {Az aktív ablakterület}

Repeat

GotoXY(40,24); Write('|'); Delay(100); GotoXY(40,24); Write('/'); Delay

(100);

GotoXY(40,24); Write('-'); Delay(100); GotoXY(40,24); Write('\'); Delay

(100);

Until KeyPressed; c:=ReadKey;

ClrScr;

End; {Várakozás}

Procedure Ures; {Az üres menüpontokhoz tartozó tevékenység}

Begin

End; {üres}

Procedure Vege;

Begin

AblakRajzolas(1,1,24,79);

GotoXY(38,12);

Writeln('Vége');

GotoXY(1,24);

Delay(1000);

ClrScr;

End; {Vége}

Procedure AblakRajzolas(bfx,bfy,hossz,szel: Byte);

Var

i: Byte;

Begin

Window(bfx,bfy,bfx+szel,bfy+hossz);

ClrScr;

For i:=1 to szel do

Begin

GotoXY(i,1); Write('-'); GotoXY(i,hossz); Write('-');

End;

For i:=2 to hossz do

Begin

GotoXY(1,i); Write('-'); GotoXY(szel,i); Write('-');

End;

End; {AblakRajzolás}

Procedure Menuzes(m: Menu);

Var

melyik,

szel : Byte;

Procedure Help (a : Word);

Begin

Ablakrajzolas(30,10,13,50);

GotoXY(5,5);

Write(a);

Varakozas;

Window(m.bfx,m.bfy,m.bfx+szel+2,m.bfy+m.db+2);

End;

Procedure MenuKiiras(m: Menu);

Var

i: Byte;

Procedure KepernyoKimentes;

Begin

End; {KepernyoKimentes}

Procedure KepernyoVisszamentes;

Begin

End; {KepernyoVisszamentes}

Function MaxSzel(m: Menu): Byte;

Var

i,j: Byte;

Begin

j:=Length(m.cim);

For i:=1 to m.db do

Begin

If j<Length(m.am[i].kerdes) then j:=Length(m.am[i].kerdes);

End;

MaxSzel:=j

End; {MaxSzel}

Begin {MenüKiírás}

KepernyoKimentes; {Verembe!!!}

szel:=MaxSzel(m)+1;

AblakRajzolas(m.bfx,m.bfy,m.db+2,szel+2);

GotoXY(((szel-length(m.cim)) Div 2)+2,1);

HighVideo; Write(m.cim); Lowvideo;

For i:=1 to m.db do

Begin

GotoXY(2,i+1); Write(m.am[i].kerdes);

GotoXY(m.am[i].sorsz+1,i+1);

HighVideo; Write(m.am[i].kerdes[m.am[i].sorsz]); Lowvideo;

End;

End; {MenüKiírás}

Function MenuValasztas(m: Menu): Byte;
Var
c : Char;
eleg : Boolean;
i : Integer;
betuk: Set of Char;

Begin {MenüVálasztás}

betuk:=[];

For i:=1 to m.db do

Begin

c:=Upcase(m.am[i].kerdes[m.am[i].sorsz]);

betuk:=betuk+[c];

End;

i:=1;

Highvideo; GotoXY(2,i+1); Write(m.am[i].kerdes); Lowvideo;

eleg:=False;

Repeat

GotoXY(1,1);

c:=Readkey;

Case c of

#0 : Begin

c:=Readkey;

Case c of

#80 : Begin

GotoXY(2,i+1); Write(m.am[i].kerdes);

GotoXY(m.am[i].sorsz+1,i+1);

HighVideo;

Write(m.am[i].kerdes[m.am[i].sorsz]);

Lowvideo;

i:=i+1;

If i>m.db then i:=1;

Highvideo;

GotoXY(2,i+1); Write(m.am[i].kerdes);

Lowvideo;

c:=#0; {speciális jel}

End;

#72 : Begin

GotoXY(2,i+1); Write(m.am[i].kerdes);

GotoXY(m.am[i].sorsz+1,i+1);

HighVideo;

Write(m.am[i].kerdes[m.am[i].sorsz]);

Lowvideo;

i:=i-1;

If i=0 then i:=m.db;

Highvideo;

GotoXY(2,i+1); Write(m.am[i].kerdes);

Lowvideo;

c:=#0; {speciális jel}

End;

#59 : help(m.am[i].segit);

End; {case}

End;

#13 : eleg:=true;

#27 : Begin

i:=m.db; eleg:=True;

End;

End; {case};

If not eleg and (Upcase(c) in betuk) then

Begin

i:=1;

While Upcase(c)<>Upcase(m.am[i].kerdes[m.am[i].sorsz]) do Inc(i);

eleg:=True;

End;

Until eleg;

MenuValasztas:=i;

End; {MenüVálasztás}

Begin {Menüzés}

ClrScr;

Repeat

MenuKiiras(m);

melyik:=MenuValasztas(m);

m.am[melyik].tevek;

Until melyik=m.db;

End; {Menüzés}

{A próbához, mint programhoz:

Begin

Menuzes(FoMenu);

End.

}