Цифрлы срыптау

Бір лшемді массивтерді срыптау алгоритмдері: «тадау» жне «алмастыру» дістері

Бл таырыпта бір лшемді массивтерді срыптауды типтік алгоритмдерімен танысуды бастаймызмыз. Типтік алгоритмдердегі массив элементтерін срыптауды олимпиадалы тапсырмаларын арастырамыз.

 

Жмыс масаты: Тадау жне алмастыру арылы срыптау алгоритмін олдану арылы классикалы есептерді шыару.

 

Тадау арылы срыптау

 

Срыптау алгоритмдеріні ішіндегі е жеілі – осы тадау арылы срыптау болып табылады. Мнда алдымен, е кіші элемент табылады да, бірінші элементпен алмастырылады, сосын, алан элементтерді ішіндегі е кішісі аныталып, екінші элементпен алмастырылады. Дл осылайша n-1-ші элементке дейін жаластырылады. Оны іске асыру алгоритмі былай жазылуы ммкін:

for i:=1 to n-1 do

for j:=i+1 to n do

if a[i]>a[j] then

begin

c:=a[i];

a[i]:=a[j];

a[j]:=c

end;

1-мысал.«Уаытты срыптау» есебі. Саат, минут жне секундпен берілген уаыт бірліктерін срыптау ажет.

Кіріс мліметтері

INPUT.TXT атты кіріс файлыны бірінші атарында N бтін саны (1 N 100), ал келесі N атарда N уаыт бірлігі жазылан. рбір уаыт бірлігі ш бтін санмен – сааттар (0..23 аларыында), минуттар (0..59 аралыында) жне секундтар (0..59 аралыында) берілген.

Шыыс мліметтері

OUTPUT.TXT атты шыыс файлына берілген уаыт бірліктерін спелі ретпен срыптап шыарыыз (шыарылатын сандарды ешайсысында бастаушы 0-дер болмасын).

Тест

№	INPUT.TXT	OUTPUT.TXT
	10 20 30 7 30 00 23 59 59 13 30 30	7 30 0 10 20 30 13 30 30 23 59 59

 

 

// Тадау арылы срыптауды олдану

var i,ch,m,s,n:integer;

ms:array[1..100] of longint;

 

procedure sort;

var j,i,mem:longint;

begin

for i:=1 to n-1 do

for j:=1 to n-1 do

if ms[j]>ms[j+1]then

begin

mem:=ms[j];

ms[j]:=ms[j+1];

ms[j+1]:=mem;

end;

end;

//Негізгі программа

begin

assign(input,'INPUT.TXT'); reset(input);

assign(output,'OUTPUT.TXT');rewrite(output);

readln(n);

for i:=1 to n do

begin

readln(ch,m,s);

ms[i]:=ch*3600+m*60+s;

end;

sort;

for i:=1 to n do

begin

ch:=ms[i] div 3600;

m:=ms[i] mod 3600;

s:=m mod 60;

m:=m div 60;

writeln(ch,' ',m,' ',s)

end;

close(input);

close(output);

end.

 

Цифрлы срыптау

 

2-мысал. «Аурон» аламшарында атмосфера жо деуге болады, сондытан оны р жеріндегі температура крсеткіші -100..100 аралыында ауытып отырады. Бізді мамандар аламшарды N нктесіндегі температурасын анытауа ол жеткізді. кінішке орай, аныталан мліметтер лкен ателіктермен есептелген, сондытан оларды бтін сана дейін дгелектеу ажет деп шешілді. Ондаы температурасы жоары жне тмен нктелерді крнекі трде анытауа Сізді кмегііз ажет. Сіз планета нктелеріні температурасын кемімейтін (спелі) тртіппен срыптауыыз керек.

Шешу идеясы: Берілген есеп бтін сандарды срыптауа арналан, сондытан, бір араанда, те арапайым сияты крінеді. Біра есепті крделілігі ондаы элементтер санымен тікелей байланысты. Яни, 1000000 элементі бар массивті срыптау иын емес, біра уаыт шектеуінде біз келтірген срыптау дістеріні ешайсысы лгермейді. Дегенмен, цифрлы срыптау (DigitalSort) деп аталатын келесі тсіл есепті орындалу уаытына сыйымды бадарлама руа ммкіндік береді:

Массив элементтеріні абылдайтын мндері шектеулі боландытан, бкіл массивті жадта сатау міндетті емес: бар боланы – массивті рбір элементін оыан кезде ондай мндерді кездесу санын анытап алса жеткілікті, яни массивті оыан кезде inc(d[a[i]]) процедурасын пайдаланамыз. Сонда, d массивіні рбір элементі а массивінде кездесетін элементтер санын анытайды.

d массиві аныталан со -100..100 арасындаы і мнін d[i] рет экрана шыарса боланы.

{цифрлы срыптау алгоритмін олдану}

var a:array[1..1000000] of integer;

d:array[-100..100] of integer;

i,n,j,k:integer;

begin

{assign(input,'input.txt');

assign(output,'output.txt');

reset(input); rewrite(output);}

read(n);

for i:=1 to n do

begin

a[i]:=random(201)-100;

write(a[i],' ');

inc(d[a[i]]);

end; writeln;

for i:=-100 to 100 do

writeln(i,' ',d[i]);

for i:=-100 to 100 do

for j:=1 to d[i] do

write(p,i,' ');

{close(input); close(output);}

end.

 

Салыстыру шін, дл осы есепті жылдам срыптау тсілі арылы жазылан програм-масын келтірейік. Бадарламаларды орындалу уаытына мн берідер.

 

// жылдам срыптау алгоритмін олдану

var
i,n:longint;
buf, X:extended;
a:array[1..1000000]of extended;

procedure Sort(L,R:Longint);
var j:longint;
begin
i:=L; j:=R; X:=a[(i+j)shr 1];
repeat
while a[i]<X do inc(i);
while a[j]>X do dec(j);
if i<=j then begin
buf:=a[i]; a[i]:=a[j]; a[j]:=buf;
inc(i); dec(j);
end;
until i>j;
if i<R then Sort(i,R);
if j>L then Sort(L,j);
end;

begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
read(input,n);
for i:=1 to n do read(input,a[i]);
sort(1,n);
for i:=1 to n do write(output,a[i]:0:0,' ');
close(output);
close(input);
end.

 

 

Сратар.

· «Тадау» срыптауды бірінші адамында не болады?

· «Цифрлы» срыптау дісіндегі ішкі циклды санауын сырты циклды санауына туелділігін анытадар?

Тапсырмалар

· Символды жол сандардан жне латын ріптерінен трады. Оларды райсысы з орнында алатындай етіп сандарды кему реті бойынша, ріптерді алфавиттік тртіп бойынша реттеу керек.

· Натурал сандардан тратын массив берілген, ондаы жай сандарды су ретімен, ал рама сандарды кему ретімен срыптау керек.

· Сйлемдегі дауысты дыбыстарды алфавит тртіппен су реті бойынша, ал дауыссыз дыбыстарды кему реті бойынша орналастыру керек.

· Сйлемдегі сздерді орнын алфавиттік тртіппен (рбір сздегі бірінші ріп бойынша) орналастыру ажет.