Сурет 4. Жоғарылатын пирамида
Сонымен біз сызықтық массивті пирамидалық құрылым түрінде көрсетеміз
a[1]
|
a[2]
|
a[3]
|
a[4]
|
a[5]
|
a[6]
|
a[7]
|
a[8]
|
a[9]
|
a[10]
|
a[11]
|
a[12]
|
|
Пирамидалық сұрыптау әдісінің бағдарламалық бейнеленуі
for i := (N div 2) downto 1 do
begin
j := i;
while j <= (N div 2) do
begin
k := 2 * j;
if (k + 1 <= N) and (a[k] < a[k + 1]) then
k := k + 1;
if a[k] > a[j] then
begin
x := a[j];
a[j] := a[k];
a[k] := x;
j := k
end
else
Break
end
end;
Нәтиженің мысалысы
массивті аламыз [1, 7, 5, 4, 9, 8, 12, 11, 2, 10, 3, 6] (N = 12).
Оның бастапқы қалыпы осындай (сұр түспен пирамиданың негізі кқрсетілген):
1
|
7
|
5
|
4
|
9
|
8
|
12
|
11
|
2
|
10
|
3
|
6
|
|
Бірінші үш фильтрация өткізгеннен кейін (a[6], a[5], a[4]) келесі суретке ие боламыз (мұнда да сұр түспен фильтрацияға қатысатын элементтерді белгілейміз):
1
|
7
|
5
|
4
|
9
|
8
|
12
|
11
|
2
|
10
|
3
|
6
|
|
1
|
7
|
5
|
11
|
10 9
|
8
|
12
|
11
|
2
|
9 10
|
3
|
6
|
|
1
|
7
|
5
|
11 4
|
10
|
8
|
12
|
4 11
|
2
|
9
|
3
|
6
|
|
Просеивание двух следующих элементов (a[3] и a[2]) тоже не вызовет вопросов — для каждого из них будет достаточно только одного шага:
1
|
7
|
12 5
|
11
|
10
|
8
|
5 12
|
4
|
2
|
9
|
3
|
6
|
|
1
|
11 7
|
5
|
7 11
|
10
|
8
|
12
|
4
|
2
|
9
|
3
|
6
|
|
А вот для просеивания последнего элемента (a[1]) понадобится целых три шага:
12 1
|
11
|
1 12
|
7 1
|
10
|
8
|
5
|
4
|
2
|
9
|
3
|
6
|
|
12
|
11
|
8 1
|
7
|
10
|
1 8
|
5
|
4
|
2
|
9
|
3
|
6
|
|
12
|
11
|
8
|
7
|
10
|
6 1
|
5
|
4
|
2
|
9
|
3
|
1 6
|
|
Сонымен ең үлкен мәнге ие болған элемент жоғарылатын пирамидада түбкі орында тұрады.
№7 дәрістің бақылау сұрақтары
Пирамидалды сортировканың негізгі идеясы неде?
Пирамидалды сұрыптау алгоритмін қандай деректермен жұмыс істегенде қолданылу қажет?
Неге берілген сұрыптау әдісін пирамидалды деп атаған?
Пирамидалды сұрыптау әдісінде ең маңызды операция болып не есептеледі?
Берңлген әдіс әдістердің қай классына жатады?
Дәріс №8 Массивтеді сұрыптау әдістері
Дәрістің мақсаты – студенттерді массивтерді сұрыптау әдістерімен таныстыру, сұрыптудың мысалдарын келтіру.
Алгоритмдерді әдетте сандық (есептеу) және сандық емес (есептеусіз) деп бөледі. Сандық алгоритмдер сандармен математикалық есептеулер жүргізуге арналған, ал сандық емес алгоритмдер әртүрлі құрылымданған мәліметтермен жұмыс істейді. Ең маңызды есептеусіз алгоритмдердің бірі болып сұрыптау және іздеу табылады. Объектілердің берілген тізбегін қандай да бір анықталған ретпен қайта топтастыратын үрдісті сұрыптау деп атайды. Сұрыптаудың мақсаты – сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету. Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді, сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау алгоритмдері(файлдарды сұрыптау). Сандық емес алгоритмдер үшін жазбалар массивтерін сұрыптау тән. Кілттік өріс – сызықтық тәртіптегі қатынаспен анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі орнықты деп аталады. Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив. Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау). Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,…, ai-1 және кіретін тізбекке ai,…, an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді. Таңдаумен сұрыптау – ең кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Алмасумен сұрыптау – барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.
Қарапайым таңдаумен сұрыптау әдісі қарапайым әдістердің ішіндегі ең жақсысы, алмасумен сұрыптау – ең жаманы, ал жылдам сұрыптау ең тезі және ең жақсысы болып табылады.
|
Тапсырма. Екі бүтін сандық айнымалы берілген х және y. Осы элементтер кішіреиу ретінде қоятын бағдарламаны құру керек
if x then
begin
t:=x;
x:=y;
y:=t;
end;
|
|
Тапсырма. Пернетақтадан берілген үш элементтің ішінен ең үлкенін табу қажет.
а, b, c – пернетақтадан берілетін сандар, Max – олардың ішіндегі максималды саны
. . .
m:=a;
if m then
m:=b;
if m then
m:=c;
. . .
|
Тапсырма. Он элементтен тұратын массив берілген. Максималды элементті табатын бағдарламаны құрастыру қажет.
. . .
Max:=a[1];
for i := 2 to 10 do
if Max then
Max := a[i];
. . .
|
Енді көп сандарды сұрыптауға арналған бағдарлама құрастырайық:
Рrogram Sorting;
Сonst
n = ... ; {массивтегі элементтер саны}
Type
TArray = array [1..n] of integer;
Procedure FillArray (Var a: TArray);
Var
i: integer;
Begin
for i: = 1 to n do
a [i] := Random(100);
End; {процедураның соңы}
Procedure PrintArray (a: TArray);
Var
i: integer;
Begin
for i: = 1 to n do
write (a [i]: 3, ' ');
writeln;
End;
Begin {басты бағдарлама}
writeln('Іріктеудің әдісі . . .');
writeln('массивті элементтермен толықтырыңыз: ');
FillArray (a);
PrintArray (a);
AnySort (a, b);{берілген әдіспен сұрыптау процедурасы}
writeln('іріктелген массив: ');
PrintArray (b);
End.
|
Достарыңызбен бөлісу: |
