Табиғи бірігу арқылы сұрыптау

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 5 бет
Таңдаулыға:

Семей қаласының Шәкәрім атындағы мемлекеттік университеті

Информатика және ақпараттық технология кафедрасы

СӨЖ

Тақырыбы: Табиғи бірігу арқылы сұрыптау

Орындаған: Даурембекова А. Е.

Топ: Т-341

Тексерген: Болсынбекова Ш. Ж.

Семей 2015

Жоспар

Кіріспе.
Сұрыптау түрлері.
Табиғи бірігу арқылы сұрыптау.
Қорытынды.

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

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

Тура біріктіру арқылы сұрыптау екі реттелген тізімді біріктіретін жай біріктіру әдісін қолданады. Басты идеясы біртіндеп үлкейетін элементтер түрінде файл ұйымдастырылатынында, яғни жазулар тізбегі r1<=r2<=…<=rn жазулар тізбегі. Мысалға, 3 деген ұзындықтағы сериялармен ұйымдастырылған бүтін сандар тізбегі:

7 15 29 7 11 13 16 22 31 5 12

Мұнда соңы 3 тен кем ұзындықта болуы мүмкін, бірақ оның жазулары да сұрыпталған.

Сұрыптау алгоритмі

FC 5, 15, 35, 30, 20, 45, 35, 5, 65, 75, 40, 50, 60, 70, 30, 40, 25, 10, 45, 55

Файлды екіге бөлеміз. Оның элементтерін сәйкесінше екіге бөлеміз. Осылайша, әрбір жаңа файлда элементтер тізімі пайда болады.
Ішкі тізімдерді салыстырамыз. Яғни, FA файлынан және FB файлынан бір-бір элементтен таңдап алып, жай біріктіру алгоритмін пайдалана отырып, қайтадан FC файлына жазамыз. Осылайша, барлық элементе қайтадан FC файлға ауысқанша жалғастырамыз.

FА 5, 35, 20, 35, 65, 40, 60, 30, 25, 45

FВ 15, 30, 45, 5, 75, 50, 70, 40, 10, 55

FC 5, 15, 30, 35, 20, 45, 5, 35, 65, 75, 40, 50, 60, 70, 30, 40, 10, 25, 45, 55

Бір қадамды қайталап, FА және FВ файлдарына екі элементті серияларды жазып шығарамыз.

FА 5, 15, 20, 45, 65, 75, 60, 70, 10, 25

FВ 30, 35, 5, 35, 40, 50, 30, 40, 45, 55

FА және FВ файлдарындағы екі элементті серияларды FC файлына 4 элементті серияға біріктіреміз. Мұнда реттелген тізімдерді біріктіру алгоритмін пайдаланамыз.

FC 5, 15, 30, 35, 5, 20, 35, 45

40 50 65 75 30 40 60 70 10 25 45 55

FС файлын екіге бөлетін қадамды FА және FВ файлында сәйкесінше 4 8 т. с. с элементтер серияларын құрай отырып және сериялардың әрбір жұптарын біріктіре отырып қайталаймыз. Процесс FА және FВ файлдары бір-бір реттелген тізімнен тұрғанда және олар FC сұрыпталған файлына соңғы рет бірікенде аяқталады.

Түзу бірігу сұрыптау анализі.

Сұрыптау бір элементі ішкі тізімдердің жүрістер сериясынан тұрады, әрбір жүрісте ішкі тізімнің ұзындығы екі еселенеді. Ол үшін log ₂ n жүріс қажет болады. Түзу бірігу арқылы сұрыптау 2n log ₂ n мәліметтерді қарауды талап етеді, сондықтан оның күрделілік реті O(n log ₂ n) .

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

Пайдаланылған әдебиеттер:

Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу) . Алматы, 1990ж.
Балапанов Е. К., Бөрібаев Б. Информатикадан 30 сабақ, Алматы, 1999 ж.

... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.