Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Дәріс №8 Массивтеді сұрыптау әдістері
|
|
Дә рістің мақ саты – студенттерді массивтерді сұ рыптау ә дістерімен таныстыру, сұ рыптудың мысалдарын келтіру.
| Алгоритмдерді ә детте сандық (есептеу) жә не сандық емес (есептеусіз) деп бө леді. Сандық алгоритмдер сандармен математикалық есептеулер жү ргізуге арналғ ан, ал сандық емес алгоритмдер ә ртү рлі қ ұ рылымданғ ан мә ліметтермен жұ мыс істейді. Ең маң ызды есептеусіз алгоритмдердің бірі болып сұ рыптау жә не іздеу табылады. Объектілердің берілген тізбегін қ андай да бір анық талғ ан ретпен қ айта топтастыратын ү рдісті сұ рыптау деп атайды. Сұ рыптаудың мақ саты – сұ рыпталғ ан тізбекте қ ажетті элементтерді іздестіруді жең ілдету. Сұ рыптау алгоритмдері мә ліметтер қ ұ рылымын таң дауғ а тә уелді, сондық тан сұ рыптау ә дістерін екі тү рге бө леді: ішкі сұ рыптау алгоритмдері(массивтерді сұ рыптау) жә не сыртқ ы сұ рыптау алгоритмдері(файлдарды сұ рыптау). Сандық емес алгоритмдер ү шін жазбалар массивтерін сұ рыптау тә н. Кілттік ө ріс – сызық тық тә ртіптегі қ атынаспен анық талатындай мә лімет типімен берілген ө ріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұ рыптауда ө згермесе, онда сұ рыптау ә дісі орнық ты деп аталады. Ішкі сұ рыптаулар алгоритмдері – бұ л ішкі жадтағ ы мә ліметтерді сұ рыптау алгоритмдері, бұ л жағ дайда қ олайлы қ ұ рылым – массив. Массивтерді сұ рыптау алгоритмдеріне қ ойылатын басты талап – жадтың экономды пайдаланылуы. Элементтерді in situ (яғ ни элементтерді қ айта топтастыруды жадтың сол жерінде жү ргізеді) сұ рыптайтын қ арапайым сұ рыптау алгоритмдері бар: кірулермен сұ рыптау, таң даумен сұ рыптау, алмасумен сұ рыптау («кө бікше» ә дісі). Сұ рыптаудың жетілдірілген қ арапайым ә дістері: кемімелі ө сімшелі кіру бойынша сұ рыптау (Шелл сұ рыптауы), ағ аш кө мегімен сұ рыптау (пирамидалық сұ рыптау), бө ліктеу арқ ылы сұ рыптау (жылдам сұ рыптау). Кірулермен сұ рыптау – элементтер шартты тү рде дайын тізбекке a1, …, ai-1 жә не кіретін тізбекке ai, …, an бө лінеді, содан кейін ә рбір қ адамда, i=2 бастап жә не i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді. Таң даумен сұ рыптау – ең кіші кілтті элемент таң далады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Алмасумен сұ рыптау – барлық элементтер қ ажетінше сұ рыпталғ анша кө рші элементтер ө зара салыстырылып жә не орын ауыстырылады. Қ арапайым таң даумен сұ рыптау ә дісі қ арапайым ә дістердің ішіндегі ең жақ сысы, алмасумен сұ рыптау – ең жаманы, ал жылдам сұ рыптау ең тезі жә не ең жақ сысы болып табылады. |
Тапсырма. Екі бү тін сандық айнымалы берілген х жә не y. Осы элементтер кішіреиу ретінде қ оятын бағ дарламаны қ ұ ру керек
| if x< y then begin t: =x; x: =y; y: =t; end; |
Тапсырма. Пернетақ тадан берілген ү ш элементтің ішінен ең ү лкенін табу қ ажет.
а, b, c – пернетақ тадан берілетін сандар, Max – олардың ішіндегі максималды саны
| ... m: =a; if m< b then m: =b; if m< c then m: =c;... |
Тапсырма. Он элементтен тұ ратын массив берілген. Максималды элементті табатын бағ дарламаны қ ұ растыру қ ажет.
| ... Max: =a[1]; for i: = 2 to 10 do if Max< a[i] 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. |
№8 дә рістің сұ рақ тары
1. Массивтерді сұ рыптайтын негізгі ә дістер туралы айтып берің із?
2. Массивті сұ рыптау кезең інде қ алай бейнелеуге болады?
3. Массивті сұ рыптау ү шін қ андай қ осымша процедуралар мен функцияларды дайындап қ ою керек?
|
|