Главная страница
Контакты

    Басты бет


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

жүктеу 0.7 Mb.



жүктеу 0.7 Mb.
бет1/5
Дата01.04.2018
өлшемі0.7 Mb.

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


  1   2   3   4   5

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БIЛIМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛIГI


СЕМЕЙ қаласының ШӘКӘРIМ атындағы МЕМЛЕКЕТТIК УНИВЕРСИТЕТI

«Іріктеу және іздеу әдістері» пәнінен

ДӘРІСТЕР КУРСЫ

Семей


2015

МАЗМҰНЫ

ГЛОССАРИЙ 4

ДӘРІСТЕР 6

1.Кіріспе. Іріктеу әдістері 6

2. «Көбікше» әдісі (Айырбастау бойынша сұрыптау) 13

3. Шейкерлік іріктеу (Мойындық іріктеу) 21

4.Тікелей қосу іріктеуі 26

5. Шелл сұрыптау әдісі 31

6. Хоар сұрыптамасы (лездік сұрыптау) 35

7. Пирамидті іріктеу 47

8. Файлдарды сұрыптау әдістері (Сыртқы сұрыптау әдістері) 53

Алғы сөз

Ұсынылып отырған дәрістер курсының мазмұны 5В070400 «Есептеу техникасы және бағдарламалық қамсыздандыру» мамандығының «Іріктеу және іздеу әдістері» пән бағдарламасы үшін жазылған. Берілген нұсқаулық іздеу және сұрыптау алгоритмдерімен таныстырады, алгоритмдердің бағдарламалық реализациясын көрсетеді.

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

Кіріспе

Берілген курста негізгі және сыртқы жадыда орналасқан деректерді ұйымдастыру, сұрыптау және іздеумен байланысты фундаменталды материалдар мазмұндалған. Сәйкес білімдер кез-келген деңгейдегі бағдарламаушыларға қажет.

Дәрістерде ішкі жадта деректерді іздеу әдістері және бұлармен байланысқан деректердің қызметші құрылымдары қарастырылады. Бұл аумақтарда хэштеу және ағаштар негізіндегі тәсілдер кең таралған. Сонымен қатар, соңғы жылдары іздеудің жоғары жылдамдығын қамтитын салыстырмалы жаңа іздеу әдістері пайда болды.

Деректердің типтері мен құрылымдары қазіргі кездегі бағдарламалау технологиясы құрылатын фундаментті бейнелейді. Жалпы сұрыптауды берілген жиынды бір анықталған ретте қайтадан топтастыру процессі деп түсіну керек. Сұрыптаудың мақсаты – сұрыпталған жиында элементтерді іздестіруді жеңілдету.



Біз сұрыпталған объекттермен анықтама кітапшаларында, кітаптардың мазмұнында, кітапханаларда, сөздіктерде, қоймаларда, барлық сақталған объекттер бар жерлерде кездесеміз. Сондықтан, егер сөз деректерді өңдеу жайлы болса, онда міндетті түрде сұрыптау алгоритмі қолданылады.

ГЛОССАРИЙ

  1. Іріктеу (сұрыптау) – «анықталған рет» бойынша элементтерді орналастыру процессі.

  2. Басқалардан ертерек адамдармен танылатын әдіс, оның қарапайымдылығының арқасында, көпіршік сұрыптауы деп аталады (bubble sort), бұл әдісте келесі амалдар жүргізіледі: берілген ретті бұзатын көрші элементтерді орындармен ауыстыру. Бұл процесс толық файл сұрыпталған жағдайда ғана аяқталады.

  3. Гномдардың сұрыптауы (ағылш. Gnome sort) — қосулары бар сұрыптауға ұқсаған алгоритм, бірақ керекті орынға элемент көпіршік әдісі бойынша орналастырылады.

  4. Табиғи іріктеу (ағылш. Natural sort) — қосуы бар сұрыптаудың қарапайым және тиімді модификациясы, мұнда элементтер сұрыпталып қойған болуы мүмкін.

  5. Жазба – кейбір құрылым немесе амал жайлы ақпараттар элементтерінң сәйкестігі. Жазбадағы әр элемент, мысалы, жұмысшының номері, тауардың бағасы, жазбаның өрісі болып аталады.

  6. Кілт - файлды іріктеу ережелерінде қолданылатын шаманы сақтайтын өріс.

  7. Жұптасқан алмастыру әдісі жұп және тақ қарастырулардың әртүрлі сандардан тұрады.

  8. Лездік сұрыптау – әдістің тиімділігіне әсер ететін критикалық мәнді алуға арналған әртүрлі тәсілдердің алгоритмдерінің жалпы аталуы.

  9. Кірістік рекурсия- егер процедурада рекурсивті шақыру соңғы болмаса, онда мұндай рекурсия кірістік деп аталады.

  10. Рекурсияның тереңдігі – бағдарламаның жұмыс барысында компьютердің жадысында сақталатын бастапқы процедураның аяқталмаған копияларының саны.

  11. Массивбір типті деректердің жиыны, әр элементтің өз индексі болады.

  12. Массивтерді қосу – А массивті В массивына қосқанда С массиві пайда болады, яғни C[i]=A[i]+B[i]. Алу аналогтық түрде ұйымдастырылады.

  13. Сыртқы сұрыптау – сыртқы сақтау құралдарында орналасқан деректерді сұрыптау.

  14. Ішкі сұрыптау – компьютердің оперативті жадында орналасқан деректерді сұрыптау.

  15. Кілттік өріс – сызықтық тәртіптегі қатынаспен анықталатындай мәлімет типімен берілген өріс.

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

ДӘРІСТЕР

1. Кіріспе. Іріктеу әдістері. (3 сағат)

Дәрістің мақсатыіріктеу және іздеу әдістерінің негізгі ұғымдарымен және анықтамаларымен таныстыру, пәннің негізгі терминдерімен таныстыру.

Алгоритмдерді әдетте сандық (есептеу) және сандық емес (есептеусіз) деп бөледі. Сандық алгоритмдер сандармен математикалық есептеулер жүргізуге арналған, ал сандық емес алгоритмдер әртүрлі құрылымданған мәліметтермен жұмыс істейді. Ең маңызды есептеусіз алгоритмдердің бірі болып сұрыптау және іздеу табылады.

Сұрыптау - берілген обьектілер жиынын ұсынылған реттілікпен қайта теріп орналастыру процесі.

Сұрыптаудың мақсаты – сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету. Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді, сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау алгоритмдері(файлдарды сұрыптау).



Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив. Қарапайым сұрыптау алгоритмдері: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау).

Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,…, ai-1 және кіретін тізбекке ai,…, an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді.

Керекті орынды іздеу кезінде оң жақтағы келесі элементпен орын ауыстыру қарастырылады, яғни таңдалып алынған элемент сұрыпталғандардың J=I-1 нөмірінен басталатын кезекті элементімен салыстырылады. Егер таңдалып алынған элемент a[I]-ден артық болса, онда ол сұрыпталғандар ішіне қосылады, әйтпесе a[J] бір орынға ығысады да, таңдалған элемент сұрыпталғандар ішіндегі келесі элементпен салыстырылады. Керекті орынды іздеу әрекеті екі жағдайда:

- Егер a[I]> a[J] болатын элемент табылса;

- Дайын тізбектің сол жақ шетіне жеткен кезде аяқталады.

Мысалы:

int i,j,x;



For(i=1;i

{x=a[i]; //ауысатын элементті есте сақтау

J=i-1;

While(x=0) // керекті орынды іздеу



{a[j+1]=a[j]; // оңға жылжыту

j--; }


A[j+1]=x; //элементті кірістіріп қою }

Таңдаумен сұрыптау – ең кіші элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Қалған элементтермен де осы тәсіл қайталанады.

int I, min, n_min,j; for(int i=0;i

{ min=a[i]; n_min=i; //минимумды іздеу

for(j=i+1;j

{ min=a[j]; n_min=j; }

a[n_min]=a[i]; /алмастыру a[i]=min; }

Алмасумен сұрыптау – барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады. Осындай әрекет нәтижесінде ең кіші элемент жиымның ең сол жақ шетіне ығысады.

For(int i=1;i=I;j--) If(a[j]

{int r=a[j]; a[j]=a[j-1];a[j-1]=r;}

Жиымдарды сұрыптау жылдамдығы әр түрлі болады. Қарапайым сұрыптау тәсілдері n*n рет салыстыруды керек етеді, мұндағы n- жиым элементтері саны; ал жылдам сұрыптау тәсілі n*ln(n) рет салыстыруды қажет етеді. Қарапайым тәсілдер түсінуге жеңіл, өйткені алгоритмі түсінікті. Күрделі тәсілдер аз әрекеттер санын керек еткенмен, операциялары күрделірек болады, сондықтан элементтер саны аз жиымдарға қарапайым тәсілдерді қолданған дұрыс.

Сыртқы сұрыптау алгоритмдері – бұл сыртқы жадтағы мәліметтерді сұрыптау алгоритмдері, мұнда қолайлы құрылым - файл. Негізгі ерекшелігі - өңдеудің әрбір уақыт мезетінде тек бір ғана элементі жетімді. Файлдарды сұрыптау әдістерінің көпшілігі тоғыстыру процедурасына негізделеді.



Тоғыстыру – екі (немесе одан да көп) тізбектерді бір тізбекке біріктіру, ол тізбек элементтері қайталанатын таңдау арқылы реттелген. Қарапайым тоғыстыру келесі қадамдардан тұрады:

1. a тізбегі b және c екі жартыға бөлінеді;

2. b және c тізбектері жеке элементтерді реттелген жұптарға біріктіру арқылы тоғыстырылады;

3. Алынған тізбек a деп аталады, содан кейін 1 және 2 қадамдар қайталанады; бұл жолы реттелген жұптар реттелген төрттіктерге тоғыстырылады;

4. Алдыңғы қадамдар қайталады; төрттіктер сегіздіктерге тоғыстырылады, барлық үрдіс бүкіл тізбек реттелгенше жалғасады; тоғыстырылатын жарты тізбектер ұзындықтары екі еселеніп отырады.

Табиғи тоғыстыру – бұл әр тоғыстыруда мүмкін ең ұзын ішкі тізбектер біріктірілетін тоғыстыру.

Нысандардың берілген тізбегін қандай да бір анықталған ретпен қайта топтастыратын үрдісті сұрыптау деп атайды. Сұрыптаудың мақсаты – сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету. Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді, сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау алгоритмдері(файлдарды сұрыптау). Сандық емес алгоритмдер үшін жазбалар массивтерін сұрыптау тән.



Сурет 1. Сұрыптау алгоритмдерінің классификациясы

Кілттік өріс – сызықтық тәртіптегі қатынаспен анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі орнықты деп аталады. Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив.

Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі).

Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау). Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,…, ai-1 және кіретін тізбекке ai,…, an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді. Таңдаумен сұрыптау – ең кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Алмасумен сұрыптау – барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.

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

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

Іздеу деп берілген жиында берілетін эталон априорының (немесе шаблонның) қасиеттеріне иә объектіні табуды атайды. Көп жағдайда жиын массив түрінде анықталады.

Сызықтық іздеу – қажетті элементті массив элементтерін қарапайым бірінен кейін бірін эталонмен салыстыра отырып іздейтін процедура.

Кедергімен сызықтық іздеу – бұл ізделінді элемент массивтің шекаралық a[n+1] элементі болып қосымша енгізіліп, және іздеу үрдісінде a[i]=x болатындай i табылатын іздеу.

Ал егер a[i]=x тек қана i=n+1 болса, онда массивте ізделінді элемент жоқ. Көп жағдайда іздеу реттелген массивте жүргізілген тиімді. Бұл жағдайларда тиімді әдістердің бірі – қақ бөлу бойынша іздеу.

Қақ бөліп іздеу әдісінде ізделінді эталонды салыстыру массивтің ортасында орналасқан элементпен жүргізіледі, салыстыру нәтижесіне байланысты (артық немесе кем) ары қарай іздеу массивтің не сол жақ жартысында, не оң жақ жартысында жүргізіледі.

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

Ағаштармен байланысты ұғымдар кең таралған және интуитивті түсінікті. Ағаштың бірнеше мүмкін анықтамалары бар.

Мысалы, графтар көзқарасы жағынан, ағаш деп жиі жағдайда бағытталмаған ұшы белгіленген, циклдары болмайтын, графты атайды. Бізді тек бағытталған ағаштар қызықтыратын болады, бағдарламаушылар көзқарастары жағынан. Сондықтан біз келесі рекурсивті анықтамамен қолданамыз: Т базалық типті R ағашы – бұл немесе (a) бос ағаш (бір де бір ұшы жоқ ), немесе (b) T типті кейбір ұш (ағаштың түбі) соңғы (мүмкін, нөльдік) Т базалық ағаштармен байланысқан санмен (Бұл ағаштар R ағашының ішіндегі ағаштар деп аталады). Бұл анықтамадан келесіні түсінуге болады, біржақты бағытталған тізім ағаш болып аталады. (Сур. 1).



http://www.citforum.idknet.com/programming/theory/sorting/sort2pics/4_1.gif

Сурет. 2. Графтың бір түрі

Ағаштарды әртүрлі бейнеде көрсетуге болады ( бұл тек бірқалыпты иерархиялық құрылым). мысалы, 2 және 3 суреттерінде бір ағаштың екі бейнеленуі көрсетілген, бұл ағаштың базалық типінде латын алфавитінің әріптерінің көпшілігі бар. 3 суреттегі графтық бейнелеу бағдарламалау спецификасына жақынырақ.

http://www.citforum.idknet.com/programming/theory/sorting/sort2pics/4_2.gif
Сурет. 3. Графтың екінші түрі

Ағаштардың ішіндегі ағаштардың байланыстарын бұтаұтар деп атаймыз, ал әр ағаштың түбін ұшы деп атаймыз. Реттелген деп бұтақтары реттелген ағаштарды атаймыз. Мысалыр, 4 суретте екі реттелген ағаштар айырылады.



http://www.citforum.idknet.com/programming/theory/sorting/sort2pics/4_3.gif
Сурет.4. Суретте екі бірдей граф көрсетілген

Ұштар саны немесе бұтақтар саны x ұшына жолы деп аталады. Биіктігі немесе тереңдігі деп ұштың максималды ұзындығын атаймыз.



http://www.citforum.idknet.com/programming/theory/sorting/sort2pics/4_4.gif

Сурет 5. Бұтақтары немесе ұштары көп граф.

Бақылау сұрақтары

  1. «Іріктеу және іздеу әдістері» пәнінің мақсаттары.

  2. Ағаштардың мүмкін болатын анықтамаларын атаңыз.

  3. Граф деген не?

  4. Ұшқа апаратын жолдың ұзындығы деген не?


  1   2   3   4   5

  • ГЛОССАРИЙ Іріктеу (сұрыптау)
  • Гномдардың сұрыптауы
  • Лездік сұрыптау
  • Рекурсияның тереңдігі
  • Массивтерді қосу
  • Ішкі сұрыптау
  • Тоғыстыру арқылы сүрыптау
  • ДӘРІСТЕР 1. Кіріспе. Іріктеу әдістері. (3 сағат) Дәрістің мақсаты
  • Ішкі сұрыптаулар алгоритмдері
  • Іздеу

  • жүктеу 0.7 Mb.