7. Функция. Оның программада қолдану ерекшеліктері. Функцияны сипаттау және анықтау. Прототип. Рекурсия. Рекурсия механизмі. Рекурсивтік функция. Оны қолданудың артықшылығы.

Функцияны сипаттау (Описание функции; function declaration) — міндетгі анықтайтын жоғары деңгейдегі программалау тілінің конструкциясы. Функцияға атау беруге (егер қажет болса), оның формальдық параметрлерін көрсетуге және алгоритмнің жүзеге асырылатын міндетін анықтауға қызмет етеді. Функцияны сипаттау программадағы сипаттамалар бөлімінде (мысалы, Паскальда) немесе программалық модуль түрінде әзірленген бас программадан (мысалы, Фортранда) кейін орналасады. Функцияны сипаттау формасы нақтылы тілдің синтаксисімен тағайындалады. Әдетте, Функциялық сипаттау денесі мен функцияның бас тақырыбынан тұрады. Тақырыпта функцияның атауы көрсетіледі және формальдық параметрлері көрсетілуі мүмкін. Ал міндеттің денесінде орындалатын алгоритм міндеттері программаланады.

Рекурсивті алгоритм қаншалықты тиімді? Оның тиімділігін есептей аламыз ба, егер тікелей есептеу алгоритмі квадратты, кіру мәліметтерінің бөліктеуі логарифмді, барлық шешімдердің бірігуі сызықты (кіру мәліметтерінің мөлшеріне байланысты), ал әрқайсысының мөлшері бастапқының төрттен біріне тең болатын барлық кіру мәліметтері 8 бөлікке бөлінетінін білетін болсақ? Бұл есепті шеші оңай емес, оған қалай кірісу керек екендігі де түсініксіз. Дегенмен, «бөл де басқар» түріндегі алгоритмдерді талдау оңай екені анықталды, егер сіздің алгоритміңіздің қадамдары жоғарыда келтірілген жалпы түрдегі алгоритмнің қадамдарына сәйкес қойылса: тура есептеу, кіруді бөлу, бірнеше рекурсивті шақырулар саны және алынған шешімдердің біріктірілуі. Егер осы қадамдар бір-бірімен қалайша біріктірілетінін және әр қадамның күрделілігін білетін болсақ, онда «бөл де басқар» түріндегі алгоритм күрделілігін анықтау үшін келесі формуланы қолдануға болады:

мұндағы DAC —DivideAndConquer алгоритмінің күрделілігі,

DIR — Direct Solution алгоритмінің күрделілігі,

DIV — Divide Input алгоритмінің күрделілігі,

COM — CombineSolutions алгоритмінің күрделілігі.

Осы жалпы формула арқылы алдындағы абзац басында қойылған сұрақ өте қарапайым болып қалады. Тек әр бөліктің белгілі күрделіліктерін формулаға қойсақ болғаны. Нәтижесінде:

немесе кіші жиындар шамасы бірдей болғандықтан, одан да оңай формула:

Мұндай түрдегі теңдіктер рекурренті деп аталады, өйткені функция мәні өз терминдері арқылы беріледі. Сол функцияның басқа шақыруларынан тәуелсіз, тек N-нан тәуелді болатын күрделілік үшін өрнекті тапқымыз келеді.

Факториал мысалына қайтып оралсақ. Факториалды есептеу алгоритмінің барлық кезеңдерін жалпы DivideAndConquer алгоритмімен сәйкес қоялық. Енді осы сәйкестікті пайдаланып, жоғарыда келтірілген жалпы формулаға қою керек мәндерді анықтаймыз. Factorial функциясындағы тура есептеулер ешқандай әрекеттерді қажет етпейді, кіру мәліметтерін бөлу және нәтижелерді біріктіру алгоритмінің әрқайсысы тек бір әрекетті қажет етеді, ал рекурсивті шақыру бастапқы мөлшерден 1-ге кем болатын тек бір есепті шығарады. Нәтижесінде Factorial функциясын есептеу санына келесі рекурентті қатынасты аламыз:

8. Массивтерді сұрыптау алгоритмдері.Таңдау әдісі. Массивте екілік іздеу. Орын алмастыру әдісі. Орнына қою әдісі (метод вставок). Айырмашылықтары.

Алгоритмдерді әдетте сандық (есептеу) және сандық емес (есептеусіз) деп бөледі. Сандық алгоритмдер сандармен математикалық есептеулер жүргізуге арналған, ал сандық емес алгоритмдер әртүрлі құрылымданған мәліметтермен жұмыс істейді. Ең маңызды есептеусіз алгоритмдердің бірі болып сұрыптау және іздеу табылады. Объектілердің берілген тізбегін қандай да бір анықталған ретпен қайта топтастыратын үрдісті сұрыптау деп атайды. Сұрыптаудың мақсаты – сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету. Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді, сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау алгоритмдері(файлдарды сұрыптау). Сандық емес алгоритмдер үшін жазбалар массивтерін сұрыптау тән. Кілттік өріс – сызықтық тәртіптегі қатынаспен анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі орнықты деп аталады. Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив. Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау). Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,…, ai-1 және кіретін тізбекке ai,…, an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді. Таңдаумен сұрыптау – ең кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Алмасумен сұрыптау – барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.

Қарапайым таңдаумен сұрыптау әдісі қарапайым әдістердің ішіндегі ең жақсысы, алмасумен сұрыптау – ең жаманы, ал жылдам сұрыптау ең тезі және ең жақсысы болып табылады.

Орын ауыстырып сұрыптаудың негізгі идеясы сұрыпталған тізімге жаңа элементті қосар кезде оны кез келген орынға емес бірден қажетті орынға қою керек, сосын барлық тізімді қайтадан сұрыптау керек. Орын ауыстырып сұрыптау l өлшемді кез келген сұрыпталған тізімнің бірінші элементін оқиды. Екіэлементті сұрыпталған тізім бірэлементті тізімнің қажетті орнына алдыңғы берілген тізімнен екінші элементті қосқаннан құрылады. Енді алдыңғы берілген тізімнен сұрыпталған екіэлементті тізімге үшінші элемент қоюға болады. Бұл процесс алдыңғы берілген тізімнің барлық элементтері тізімнің кеңейтілген сұрыпталған бөлігіне қойылғанға дейін қайталана береді.

Енді көпіршікті сұрыптауға өтейік. Оның негізгі принципі кіші мәндерді тізім басына ығыстыру, ал үлкен мәндерді төмен түсіреді. Көпіршікті сұрыптаудың көптеген әртүрлі нұсқалар бар. Бұл параграфта олардың біреуін сипаттаймз, сонымен бірге, кейбіреуі жаттығуларда қарастырылады.

Көпіршікті әдіс алгоритмі тізім бойынша бірнеше рет өтеді. Әрбір өткенде көрші элементтерді салыстырады. Егер көрші элементтердің тізімі дұрыс емес болса, онда олар орын ауыстырады. Әрбір тәсіл тізім басынан басталады. Алдымен бірінші мен екінші элементтер, сосын екінші мен үшінші, содан кейін үшінші мен төртінші және т.с.с.; жұпта ретсіз тұрған элементтердің орны ауыстырылады. Тізімнің ең үлкен элементін бірінші өткенде тапқан кезде ол тізімнің соңына жеткенге дейін барлық кезекті элементтермен орын ауыстыра береді. Сондықтан екінші рет өткенде соңғы элементпен салыстыру қажет емес. Екінші рет өткенде тізімнің екінші элементі соңғы позициядан бастап екіншіге түседі. Процесті жалғастыра берсек әрбір өткен сайын ең болмағанда кезекті бір элемент өзінің орнында қалады. Бұл кезде ең кіші мәндер жоғары қарай жиналады. Егер қандай да бір өткен кезде ешқандай элементтердің орны ауыспаса, онда олардың барлығы қажетті ретпен тұр, және алгоритмнің орындалуын тоқтатуға болады. Әрбір өткенде бірден бірнеше элемент өзінің орнына жақындай түседі, тек біреуі ғана нақты орнында келеді.

Көпіршіктік сүрыптау (көпіршік әдісімен сүрыптау) (Пузырьковая сортировка (сортировка методом пузырька); bublle sorting) — реттелетін жиымның көрші элементтерін тізбектік орын ауыстырудан тұратын сұрыптау тәсілі. Тоғыстыру арқылы сүрыптау (Сортировка слиянием; merge sorting) — бірінші кезеңде жазбалар тобы жедел жадта сүрыпталатын өрі бірнеше таспаға жазылатын, ал екінші кезенде реттелген топтар бірнеше таспадан бір таспаға жинақталатын сыртқы сүрыптау