Бір өлшемді массивтерді сұрыптау алгоритмдері: «таңдау» және «алмастыру» әдістері
Бұл тақырыпта бір өлшемді массивтерді сұрыптаудың типтік алгоритмдерімен танысуды бастаймызмыз. Типтік алгоритмдердегі массив элементтерін сұрыптаудың олимпиадалық тапсырмаларын қарастырамыз.
Жұмыс мақсаты: Таңдау және алмастыру арқылы сұрыптау алгоритмін қолдану арқылы классикалық есептерді шығару.
Таңдау арқылы сұрыптау
Сұрыптау алгоритмдерінің ішіндегі ең жеңілі – осы таңдау арқылы сұрыптау болып табылады. Мұнда алдымен, ең кіші элемент табылады да, бірінші элементпен алмастырылады, сосын, қалған элементтердің ішіндегі ең кішісі анықталып, екінші элементпен алмастырылады. Дәл осылайша 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.
Сұрақтар.
· «Таңдау» сұрыптаудың бірінші қадамында не болады?
· «Цифрлық» сұрыптау әдісіндегі ішкі циклдың санауын сыртқы циклдың санауына тәуелділігін анықтаңдар?
Тапсырмалар
· Символды жол сандардан және латын әріптерінен тұрады. Олардың әрқайсысы өз орнында қалатындай етіп сандарды кему реті бойынша, әріптерді алфавиттік тәртіп бойынша реттеу керек.
· Натурал сандардан тұратын массив берілген, ондағы жай сандарды өсу ретімен, ал құрама сандарды кему ретімен сұрыптау керек.
· Сөйлемдегі дауысты дыбыстарды алфавит тәртіппен өсу реті бойынша, ал дауыссыз дыбыстарды кему реті бойынша орналастыру керек.
· Сөйлемдегі сөздердің орнын алфавиттік тәртіппен (әрбір сөздегі бірінші әріп бойынша) орналастыру қажет.
