Қазақстан республикасының бiлiм және ғылым министрлiгi

жүктеу/скачать 1,23 Mb.

бет	4/5
Дата	31.07.2017
өлшемі	1,23 Mb.
	#22426

1 2 3 4 5

Дәріс №8 Массивтеді сұрыптау әдістері

Жоғарылатын пирамида

Сурет 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.

Каталог: ebook -> umkd
umkd -> Мамандығына арналған Сұлтанмахмұттану ПӘнінің ОҚУ-Әдістемелік кешені
umkd -> Қазақстан Республикасының
umkd -> Қазақстан Республикасының
umkd -> Студенттерге арналған оқу әдістемелік кешені
umkd -> ПӘннің ОҚУ Әдістемелік кешені 5В011700 «Қазақ тілі мен әдебиеті» мамандығына арналған «Ұлы отан соғысы және соғыстан кейінгі жылдардағы қазақ әдебиетінің тарихы (1941-1960)» пәнінен ОҚытушыға арналған пән бағдарламасы
umkd -> «Балалар әдебиеті» пәніне арналған оқу-әдістемелік материалдар 2013 жылғы №3 басылым 5 в 050117 «Қазақ тілі мен әдебиеті»
umkd -> ПӘннің ОҚУ-Әдістемелік кешенінің
umkd -> 5 в 011700- Қазақ тілі мен әдебиеті
umkd -> 5 в 011700- Қазақ тілі мен әдебиеті
umkd -> «Филология: қазақ тілі» мамандығына арналған

жүктеу/скачать 1,23 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5

Қазақстан республикасының бiлiм және ғылым министрлiгi

Жоғарылатын пи­ра­ми­да

Жоғарылатын пирамида