Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Практикалық сабақ №5. Қарапайым әдістің модификацияланған тәсілі
|
|
№ 5 практикалық сабақ ты орындауғ а арналғ ан методикалық нұ сқ аулар
Сандық алгоритмдер сандармен математикалық есептеулер жү ргізуге арналғ ан, ал сандық емес алгоритмдер ә ртү рлі қ ұ рылымданғ ан мә ліметтермен жұ мыс істейді. Ең маң ызды есептеусіз алгоритмдердің бірі болып сұ рыптау жә не іздеу табылады. Объектілердің берілген тізбегін қ андай да бір анық талғ ан ретпен қ айта топтастыратын ү рдісті сұ рыптау деп атайды. Сұ рыптаудың мақ саты – сұ рыпталғ ан тізбекте қ ажетті элементтерді іздестіруді жең ілдету. Сұ рыптау алгоритмдері мә ліметтер қ ұ рылымын таң дауғ а тә уелді, сондық тан сұ рыптау ә дістерін екі тү рге бө леді: ішкі сұ рыптау алгоритмдері(массивтерді сұ рыптау) жә не сыртқ ы сұ рыптау алгоритмдері(файлдарды сұ рыптау). Сандық емес алгоритмдер ү шін жазбалар массивтерін сұ рыптау тә н. Кілттік ө ріс – сызық тық тә ртіптегі қ атынаспен анық талатындай мә лімет типімен берілген ө ріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұ рыптауда ө згермесе, онда сұ рыптау ә дісі орнық ты деп аталады. Ішкі сұ рыптаулар алгоритмдері – бұ л ішкі жадтағ ы мә ліметтерді сұ рыптау алгоритмдері, бұ л жағ дайда қ олайлы қ ұ рылым – массив. Массивтерді сұ рыптау алгоритмдеріне қ ойылатын басты талап – жадтың экономды пайдаланылуы. Элементтерді in situ (яғ ни элементтерді қ айта топтастыруды жадтың сол жерінде жү ргізеді) сұ рыптайтын қ арапайым сұ рыптау алгоритмдері бар: кірулермен сұ рыптау, таң даумен сұ рыптау, алмасумен сұ рыптау («кө бікше» ә дісі). Сұ рыптаудың жетілдірілген қ арапайым ә дістері: кемімелі ө сімшелі кіру бойынша сұ рыптау (Шелл сұ рыптауы), ағ аш кө мегімен сұ рыптау (пирамидалық сұ рыптау), бө ліктеу арқ ылы сұ рыптау (жылдам сұ рыптау). Кірулермен сұ рыптау – элементтер шартты тү рде дайын тізбекке a1, …, ai-1 жә не кіретін тізбекке ai, …, an бө лінеді, содан кейін ә рбір қ адамда, i=2 бастап жә не i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді. Таң даумен сұ рыптау – ең кіші кілтті элемент таң далады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Алмасумен сұ рыптау – барлық элементтер қ ажетінше сұ рыпталғ анша кө рші элементтер ө зара салыстырылып жә не орын ауыстырылады.
Сурет.5. Массивті қ арапайым сұ рыптаудың модификацияланғ ан ә дісімен іріктеудің жалрыланғ ан алгоритмі
Кесте 5.1. Сұ рыптау мысалысы
Келесі бейнеленулерді ең гізейік:
Онда қ арапайым сұ рыптаудың модификацияланғ ан ә дістің циклдік алгоритмі келесі тү рге ие болады.
|
