АЖ таңдау бойынша сұрыптау

Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 15 бет
Таңдаулыға:

ҚОЖА АХМЕТ ЯСАУИ АТЫНДАҒЫ ХАЛЫҚАРАЛЫҚ ҚАЗАҚ-ТҮРІК УНИВЕРСИТЕТІ

ИНЖЕНЕРИЯ ФАКУЛЬТЕТІ

КОМПЬЮТЕРЛІК ИНЖЕНЕРИЯ КАФЕДРАСЫ

ЖОБА

Тақырыбы: Таңдау арқылы сұрыптау, Шелл сұрыптау, Шейкер сұрыптау

Орындады
6B06151 Ақпараттық жүйелер бағыты бойынша білім алушылар
Үмен Бексұлтан Өтепбергенұлы
Хусан Сауран Нурланұлы

Тексерді
компьютерлік инженерия кафедрасының аға оқытушысы
Сапарбекова Г.А.

Кентау 2021

1
МАЗМҰНЫ

КіPіспE
1
Берілген үш сұрыптауды сипаттау
1.1
Таңдау әдісі арқылы сұрыптау
1.2
Шейкер әдісі арқылы сұрыптау
1.3
Шелл әдісі арқылы сұрыптау
2
Берілген сұрыптауларға салыстыру және олардың реализациясы
2.1
Таңдау сұрыпталуының реализациясы
2.2
Шейкер сұрыпталуының реализациясы
2.3
Шелл сұрыпталуының реализациясы
2.4 жоғарыдағы сұрыптаулардың кодтары
және с, с++ тарихы
ҚOPытынды
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ ЖӘНЕ САЙТТАР
2
КІРІСПЕ
Сұрыптау деп - кез-келген белгінің өсуі немесе кемуі бойынша мәліметтер жиынтығындағы элементтерді дұрыс ретке келтірілген жиынтықты айтады. Сұрыптау дегеніміз электрондық кестелердегі мәліметтердің ретін өзгертуге немесе реттеуге болатын тапсырма. Сұрыптаудың көмегі арқылы барлық бірдей мәндері бар деректерді бір бағанда немесе бір жолда жүйелеп жазуға болады және ұқсас мәндердің барлық топтарын сұрыптауға болады.
Сұрыптаудың мақсаты - деректерді өңдеу барысынды сұрыпталған жиынтықтағы элементтерді іздеу кезінде жеңіл әдісті қолдану.
Барлық алгоритм сұрыптаулары екіге бөлінеді:
* Ішкі сұрыптау алгоритмі(массивтерді сұрыптау);
* Сыртқы сұрыптау алгоритмі(файлдарды сұрыптау).
Егер тең кілттері бар элементтердің бастапқы реттілігі сұрыптау кезінде өзгермесе, онда сұрыптау тұрақты, ал егер, бастапқы реттіліктің кері реттілігі жағдайында сұрыптаудың ең үлкен шығындары қажет болатын болса, онда сұрыптау табиғи деп аталады.
Қазіргі кезде ондаған сұрыптау алгоритмдері бар, олардың әрқайсысы өзінше жақсы. Кейбіреулерінде сұрыптау принциптерін түсіндіру оңай, ал басқалары үлкен массивтермен жұмыс істегенде жақсы, ал басқалары жылдамдық бойынша оңтайландырылған, төртіншісі -- процессорлық циклдердің саны, кодтың ықшамдылығы және т. б.
Қазіргі таңда массивтерді сұрыптау үшін осы көптеген сұрыптауларды алуға болады(ең көп танылған):
* Таңдау сұрыптауы;
* Қосу сұрыптау;
* Алмастыру сұрыптауы.
* Көбік сұрыптау
* Пирамида сұрыптау
Алмастыру сұрыптауы дегеніміз- егер алдыңғы элемент келесі элементтен үлкен болса, тізім элементтерін ауыстыратын жадтағы ең аз сұрыптау әдістерінің отбасын сипатту үшін қолданылатын жалпы термин.
Тізім элементтерін салыстыру реттілігімен ерекшеленетін бірқатар нақты нұсқалар бар. Айырбастаудың барлық қарапайым әдістерінде элемент өзінің жақын көршісімен салыстырылады, ал мүмкін болатын қозғалыстар-бұл үлкен кілтпен бір позицияға төмен жылжыту және кіші кілтпен бір позицияға жоғары жылжыту болып табылады.
Айырбастау сұрыптауының 3 қарапайым түрі бар. Олар:
1. Жұптасқан айырбастау;
2. Статдартты айырбастау;
3. Елеу әдісі.
Жұптық алмасу әдісі ("тақ-жұп пермутация "деп те аталады) әр түрлі "тақ" және "жұп" көріністерден тұрады. Тақ көріністерде тақ позицияның әр элементі жұп позициядағы көршісімен салыстырылады және олардың үлкені үлкен позицияны алады. Тізімнің төменгі көрінісі тізімдегі соңғы тақ элемент (N - 1) n соңғы жұп элементпен салыстырылғанға дейін жалғасады, егер тізімде тақ элементтер болса, онда соңғы элемент салыстырылмайды. Әрбір қарау барысында алмасуларды есептеу жүргізіліп отырады
.3
Елеу әдісі- әдістердің ішіндегі ең тиңмдңсң әрі ең күштісі деуге болады. Ол алмасудың басқа әдістерінен айырмашылығы, әрі ерекшесі болуының себебі, салыстыру кезінде тұрақты тізбегін сақтамайды.Сонымен қатаар, салыстыру кезінде тізбектің нәтижесінде жеке көріністерге бөлінбейді.Бұл әдіс пермутация болмағанша жүзеге аса береді.
Стандартты алмасу әдісі ("көпіршік әдісі" деп те аталады) тізімнің бір элементін әр қарау кезінде тиісті орынға жылжытады. Осылайша, бірінші рет қарау кезінде ең үлкен кілті бар жазба соңғы позицияға орналастырылады, екінші қарау кезінде келесі үлкен кілті бар жазба соңғы позицияға ауысады және т.б. әдіс элементтерді кему арқылы орналастыратындай етіп түрлендірілуі мүмкін.
Екі итерациядан кейін екі үлкен элемент дұрыс жерде болады және т.б. N итерациядан кейін массив сұрыпталатыны анық. Осылайша, ең нашар және орташа жағдайдағы асимптотика-O (n2), ең жақсы жағдайда - O(n).
Көпіршікті сұрыптау - ең танымал сұрыптау алгоритмдерінің бірі. Бұл жерде көршілес тұрған элементтерді салыстыру керек, егер алдыңғысы кейінгісінен үлкен болса, сандар орын ауысады. Осылайша, басында кішісі, ал соңында үлкен сандар тұрады.
Бұл алгоритм оқу болып саналады және тиімділігі төмен болғандықтан іс жүзінде қолданылмайды: ол массивтің соңында кішкентай элементтер (оларды "тасбақалар" деп атайды) тұрған сынақтарда баяу жұмыс істейді. Алайда, көптеген басқа әдістер негізделген, мысалы, шейкер сұрыптау және тарақ сұрыптау.
Жобада айтылатын алмасу әдісінің 3 түрін қарастырайық:
* Шелл сұрыпатуы
* Таңдау арқылы сұрыптау
* Шейкер сұрыптауы

4

11 Таңдау әдісі арқылы сұрыптау

Таңдау бойынша сұрыптау. Мүмкін, ең қарапайым сұрыптау алгоритмі мыналардан тұру керек: біздің объектілер арасында ең аз элементті табу, оның шығарып алу, қалған элементтердің арасында минималды элементті тауып, одан алдын алған элементтың қасына қосу. Бұл процесс біз барлық элементтерді сұрыптап бітпегенше қайталанады. Мұндай қарапайым процедура таңдау бойынша сұрыптау әдісі деп аталады, өйткені біз қалған элементтердің ішінен ең аз элементті іздейміз.
Таңдау бойынша сұрыптау- сұрыптау алгоритмін жүзеге асырудың ең оңай жолы. Көптеген ұқсас алгоритмдер сияқты, бұл сұрыптау салыстыру операциясына негізделген. Әр элементті бір бірімімен салыстырып, қажет еткен жағдайда элемент алмасу жасап, бұл әдіс тізбекті қажетті реттелген түрге әкеледі.
Тікелей таңдау бойынша сұрыптау алгоритмі қандай да бір мағынада тікелей қосу арқылы сұрыптауға қарама-қарсы. Тікелей қосылған кезде, әр қадамда кіріс тізбегінің тағы бір элементі және қосу орнын табу үшін дайын тізбектің барлық элементтері қарастырылады. Ең кіші кілті бар бір элементті іздеу үшін тікелей таңдау кезінде кіріс тізбегінің барлық элементтері қаралады және табылған элемент дайын тізбектің соңында келесі элемент ретінде орналастырылады.
Тікелей таңдау арқылы сұрыптау әдісі келесі ережелерге негізделген:
* Ең кіші кілті бар элемент таңдалады.
* Ол бірінші a 0 элементі бар жерлерде өзгереді.
* Содан кейін бұл операциялар қалған n-1 элементімен, n-2 элементімен және т.б. бір, ең үлкен элемент қалғанша қайталанады.

Таңдау бойынша сұрыптау массивтің минималды элементін іздеуден және оны массивтің бірінші орнына (бірінші өту) ауыстырудан тұрады. Келесі өтуде қайтадан минималды (максималды) элементті іздейді (біріншісін қоспағанда) және екінші позицияға қойылады. Сонымен, массив толығымен реттелгенге дейін сұрыпталады.
Сұрыптаудың алгоритмының мәні - массивтің өңделмеген бөлігін, минималды мәннің тізімін іздеуде және кейін осы мәнді массивтің өңделмеген бөлігіндегі бірінші элементпен ауысу болып келеді. Келесі қадамда массивтің өңделмеген бөлігі бір элементке азаяды.

1.2 Шейкер әдісі арқылы сұрыптау
Шейкер әдісі арқылы сұрыптау- ретсіздіктен құтылу арқылы құрылған сұрыптау.
Шейкер сұрыптауы көпіршікті сұрыптаудың жетілдірілген түрі деп атауға болады.
Көпіршікті сұрыптаудың бір мәселесі - өте баяу сұрыпталады. Оны жетілдіру үшін біз көбік әдісінің ерекше атаумен аталған Шейкер әдісін (коктейль әдісі) қолданамыз. Оның осылай аталған себебі, сұрыптау кезінде коктейльді жасағанда араластырғышқа ұқсағандықтан.
Бұл алгоритмнің негізгі мәні мынада:
# Массивтерді ретсіздіктен құтылу;
# Бір-бірінен алшақ орналасқан массив(элементтерді) салыстыру;
# Салыстырып отырған интервалдарды бірте-бірте кему ретінмен орналастыру;
5
# Соңғы қадамдарды элементтерді орын алмастыру арқылы салыстыру.
Шейкер әдісінің көбік әдісінен айырмашылығы - ол екі бағытта массивті реттейді. Сол себептен, алгоритмнің әр итерациясы екі бағытта жүзеге асырады. Бірінші қадамда ең жеңіл көпіршік массивтің соңына дейін көтеріледі, ал екінші қадамда ауыр көпіршік массивтің басына дейін түседі.
Қысқаша айтқанда, алгоритм қатаң солдан оңға қарай емес, алдымен солдан оңға, кейін оңнан солға ауысып жылжиды.
Уақыт бойынша қиыншылық:
Ең нашар уақыт: O(n2)
Орташа уақыт: O(n2)
Ең үздік уақыт: O(n)
Жад шығындары:O(1)
Ең нашар уақыт: O(n2)
Орташа уақыт: O(n2)
Ең үздік уақыт: O(n)
Жад шығындары:O(1)

1-кесте
Шейкер сұрыптау алгоритмін талдайтын болсақ:
1. Егер, кейбір жағдайлар кезінде өзгерістер болмаған жағдайда, алгоритмді өзгертуге болады;
2. Егер, индексті соңына жазатын болсақ, онда сол индекстің шегінде емес, сол индекстің өзінде аяқтауға болады;
3. Арнайы көру үшін ауыспалы бағыттарды қолданамыз(ең жеңілі бетіне шығады, ал ауыры төменге батады).
Шейкер сұрыптауы- элементтердің барлығы дерлік сұрыпталғанда сәтті қолданады.

Алгоритмнің жалпы идеясы:
* Массивті солдан оңға қарай алмастыру, көпіршік әдісіне ұқсас-көрші элементтерді салыстыру, егер сол жақ мән оң жақтан үлкен болса, олардың орнын ауыстырады. Нәтижесінде ең үлкен сан массивтің соңына ауысады.
* Соңғы сұрыпталғанға дейінгі элементтен бастап, массивті кері бағытта (оңнан солға) айналдырамыз. Бұл кезеңде элементтер бір-бірімен салыстырылады және ең кіші мән әрқашан сол жақта болғанынша ауыстырылады. Нәтижесінде ең кіші сан массивтің басына ауысады.
1.3
Шелл әдісі арқылы сұрыптау
1959 жылы американдық ғалым Дональд Шелл сұрыптау алгоритмін жариялады, оны кейіннен "Шелл сұрыптау"деп атады. Бұл алгоритмді көпіршікті сұрыптауды жалпылау және кірістіруді сұрыптау ретінде қарастыруға болады.
Әдістің идеясы бір-бірінен белгілі бір қашықтықта орналасқан топтарға бөлінген жүйелілік элементтерін салыстыру болып табылады. Бастапқыда бұл қашықтық d немесе N2, мұндағы N-элементтердің жалпы саны. Бірінші қадамда әр топқа бір-бірінен N2
6
қашықтықта орналасқан екі элемент кіреді; олар бір-бірімен салыстырылады және қажет болған жағдайда орындарын өзгертеді. Келесі қадамдарда тексеру және алмасу жүреді, d қашықтығы d2- ге азаяды және сәйкесінше топтар саны азаяды. Бірте-бірте элементтер арасындағы қашықтық азаяды және D=1-де массив арқылы өту соңғы рет жүреді.
Шеллді сұрыптау кезінде алдымен бір-бірінен белгілі бір қашықтықта тұрған мәндер салыстырылады және сұрыпталады {\displaystyle D}D ({\displaystyle d}d мәнін таңдау туралы төменде қараңыз). Осыдан кейін процедура {\displaystyle d}d кейбір кіші мәндер үшін қайталанады, ал Шелл сұрыптау {\displaystyle d=1}d=1 (яғни, кірістірулерді әдеттегі сұрыптау) кезінде элементтерді ретке келтіру арқылы аяқталады. Тиімділігі сұрыптау Шелла белгілі бір жағдайларда қамтамасыз етіледі, бұл элементтер "тезірек" (қарапайым әдістерінде сұрыптау, мысалы, көпіршік, әрбір перестанка екі элементтерін азайтады саны инверсий тізімінде максимум 1, ал сұрыптау кезінде Шелла бұл сан көп болуы мүмкін).
Шеллді сұрыптау көптеген жағдайларда жылдам сұрыптауға қарағанда баяу болғанына қарамастан, оның бірқатар артықшылықтары бар: стек үшін жад қажеттілігінің болмауы; нашар мәліметтер жиынтығында деградацияның болмауы-жылдам сұрыптау O(n2) деңгейіне оңай түседі, бұл Шелл сұрыптаудың ең нашар кепілдендірілген уақытынан гөрі нашар.
Дональд Л.Шелл (1924 жылдың 1 наурызы - 2015 жылдың 2 қарашасы) - Америкада дүниеге келген, ұлты амирикдақ. Дональд Шелл 2015 жылы 2 қарашада Солтүстік Каролина штатының Ашвилл қаласында қайтыс болды. Оның артында әйелі Хелен қалды. Shell Sort сұрыптау алгоритмін жасаған американдық компьютер ғалымы. Ол Ph.D дәрежесін алды. 1959 жылы Цинциннати университетінен математика бойынша және сол жылдың шілде айында ACM Communications-те қабықшаларды сұрыптау алгоритмін жариялады. Мичиган технологиялық университетін бітіргеннен кейін ол Екінші дүниежүзілік соғыс кезіндегі зақымдарды жөндеу үшін Армия инженерлер корпусынан, одан Филиппинге түсті. Соғыстан оралған ол Элис МакКаллоға үйленіп, Мичиган технологиялық университетіне оралып, математикадан сабақ берді. Содан кейін ол Цинциннатиге (Огайо) көшті ... жалғасы

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