Массивтерді сұрыптаудың қарапайым алгоритмдері
КІРІСПЕ
5
І СҰРЫПТАУ АЛГОРИТМДЕРІ
8
0.1 Алгоритм түсінігі
9
0.2 Іздеу және тандау алгоритмдері
13
0.3 Көпіршік алгоритмі
16
1.4 Қарапайым таңдау алгоритмі
18
1.5 Қарапайым кірістіру алгоритмі
18
1.6 Массивтерді сұрыптаудың жетілдірілген алгоритмдері
19
1.6.1 Шелл алгоритмі
19
1.6.2 Жылдам сұрыптау алгоритмі
20
1.6.3 Пирамидалық сұрыптау алгоритмі
22
1.6.4 Біріктіру алгоритмдері
24
ІІ САНДЫҚ МАССИВТЕРДІ СҰРЫПТАУ
26
0.1 Массив түсінігі
26
0.2 Массивтерді сұрыптау
31
2.2.1Таңдау арқылы сұрыптау
32
2.2.2Ауыстыру арқылы сұрыптау
34
2.2.3 Шейкерлік сұрыптау
39
2.2.4 Тікелей қосу сұрыптауы
44
2.2.5 Пирамидалық сұрыптау
53
2.3 Оқушылардың массивті сұрыптауға өз бетінше орындауына арналған тапсырмалар
57
ҚОРЫТЫНДЫ
60
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР
61
КІРІСПЕ
Қазіргі таңда заманымыздың цифрланған дәуірге қадам басқан кезеңінде көптеген мамандардың функционалдық міндеттерін сәтті орындауы көбінесе дербес компьютерлерді, байланыс құралдарын, қолданбалы бағдарламалардың кәсіби пакеттерін және әртүрлі зияткерлік ақпараттық технологияларды шебер қолдануымен анықталады.
Қоғамды ақпараттандыру процестері информатика және басқару процестерін компьютерлендіру саласындағы білімді қалыптастыруды қажет етеді.
Қазіргі уақытта жаңа ақпараттық технологиялар мамандандырылған ғана емес, сонымен қатар күнделікті өмірде де маңызды орын алады. Компьютерлер бизнесте, басқаруда, саудада, оқуда және адам қызметінің көптеген басқа салаларында қолданылады.
Компьютерлік технологиялар әртүрлі операцияларды орындау үшін өте ыңғайлы, бірақ әр түрлі қолдану салаларында бұл операциялар әртүрлі. Сондықтан нақты техникалық құралдарды қолданатын әрбір жеке сала компьютерлердің жұмысын қамтамасыз ететін өз бағдарламаларын қажет етеді.
Бағдарламалық жасақтаманы бағдарламалау сияқты ғылым саласы жасайды. Бұл соңғы уақытта барған сайын маңызды бола түсуде, өйткені күн сайын компьютер біздің өміріміздің қалыпты құбылысына айналуда.
Осылайша, жаңа ақпараттық технологиялар біздің заманымызда өте өзекті және кейінгі даму мен жетілдіруге көп көңіл бөлуді қажет етеді. Сонымен қатар, бағдарламалаудың да маңызы зор, ол информатиканың іргелі бөлімдерінің бірі болып табылады, сондықтан қазіргі таңда оған өте қатты көңіл бөлінуде.
Бағдарламалау бірқатар маңызды ішкі міндеттерді қамтиды.
Бағдарламалауда үлкен көлемдегі мәліметтерді өңдеумен байланысты тапсырмалар жиі кездеседі. Мәліметтердің бүкіл көлемін бағдарлама ішінде сақтау үшін массивтер қолданылады - құрылымдалған деректер түрлерінің қарапайым түрі.
Массив - бірдей элементтерді сақтайтын жад аймақтарының белгілі тізбегі. Әрбір осындай жад аймағы массив элементі деп аталады. Массивтерде олардың құрамындағы элементтердің саны, сондай ақ бағдарламада бір және көп өлшемді массивтерді сипаттау мүмкіндігін білдіретін өлшем бар. Массивтегі элементтер саны оның мөлшері деп аталады.
Бағдарламалаудың маңызды міндеттерінің бірі - сұрыптау мәселесі.
Сұрыптау есептері іздеу есептері сияқты базалық болып табылады. Практикалық жағдайда бұл міндеттер өзара байланысты. Сұрыптауға байланысты мәселелерді шешуге көптеген іргелі ғылыми зерттеулер, көптеген алгоритмдер жасалды.
Жалпы жағдайда сұрыптауды белгілі бір ретпен берілген объектілер жиынтығын қайта құру процесі деп түсіну керек. Көбінесе мәліметтердің ауқымды көлемін сұрыптау кезінде элементтердің өздерін қайта құру мүмкін емес, сондықтан мәселені шешу үшін элементтерді индекстер бойынша ретке келтіру жүзеге асырылады. Яғни, элементтердің индекстері оларға сәйкес келетін элементтердің мәндері мәселенің шарты бойынша сұрыпталатын ретпен құрылады.
Маманды қалыптастыру мектеп қабырғасынан басталады. Ендеше, орта білім беру мектептерінде 7-9 сыныптарда массивтер, оларды жариялау және өңдеу туралы жалпы түсінік ала отырып, баланың бағдарламалау туралы алғашқы идеялары туындап, қызығушылығы артатыны мүмкін екенін атап өтуге болады. Сонда оқытудың келесі кезеңінде мамандандырылған сыныптарда мұғалім мен оқушы бағдарламалық жасақтаманы жасау үшін мейлінше жан жақты қолданылатын, заманауи бағдарламалау тілін алады.
Осылайша, мұғалім массивтерді сұрыптауға, элементтерді іздеуге байланысты көптеген мәселелерді шешуге жақындай алады, бұл оқытудың мамандандырылған кезеңінде оқушыға қысқа мерзімде әр түрлі мәселелерді шешуге мүмкіндік береді.
Бұл жұмыста теориялық бөлімде тек мектеп информатикасы ғана емес жалпы информатикада қолданылатын сұрыптау алгоритмдері толық қамтылды.
Жұмыстың теориялық бөлігін орындау кезінде әр алгоритмнің қасиеттерін егжей-тегжейлі ашатын келесі сұрақтарға жауап беріледі, атап айтқанда:
қандай салыстыру элементтер жұбының реттілігін анықтайды?
қандай орын ауыстыру бірнеше элементті өзгертеді?
жиынтықтың барлық элементтері реттелгенге дейін элементтерді салыстыру мен қайта құруды жүзеге асыратын сұрыптау алгоритмі қандай?
Қарастырылған сұрыптау алгоритмдерінің бәріне қасиеттер ортақ деп айтуға болады. Олар көптеген алгоритмдерден таңдалады, өйткені біріншіден, олар жиі қолданылады, екіншіден, басқа алгоритмдердің көпшілігі осы алгоритмдердің әртүрлі сипатталған түрлері деп айтуға болады.
Практикалық бөлімде бағдарламалау тілін қолдана отырып, есептер шешуге бағдарлама құру арқылы бар білімімізді бекітеміз.
Сондай-ақ, бұл жұмыста деректерді практикалық тұрғыдан реттеу мәселесі, яғни сұрыптау әдістерінің артықшылықтары мен кемшіліктері айтылған.
Дипломдық жұмысты орындау кезінде ABC Pascal бағдарлама ортасын қолданылды. Және жұмыстың мәтіндік бөлігін орындауға Microsoft Word қосымшасын пайдаланылды.
Microsoft Word-бұл әртүрлі құжаттар мен деректерді құруға, өңдеуге, экранға шығаруға және басып шығаруға, сонымен қатар файл түрінде сақтауға арналған мәтіндік редактор. Ол аталған операциялармен қатар мәтінді форматтауға (құжаттың бүкіл және оның бір бөлігі бойынша), құжаттарды ресімдеудің әртүрлі стильдерін қалыптастыруға, қаріптердің көп санын пайдалануға, мәтін фрагменттерін бөлуге (курсивпен, астын сызумен, қалың қаріппен және басқа да құралдармен), мәтінді бағандар түрінде теруге, иллюстрацияларды мәтіндерге қосуға, әр түрлі көрсеткіштер мен сілтемелерді қалыптастыруға, беттердің жоғарғы және төменгі колонтитулдарын енгізуге, мәтін элементтерін автоматтандырылған іздестіруді жүргізуге және қателерді, мәтіннің кез-келген бөлігін басқа орынға көшіруге және орын ауыстыруға қабілетті.
Дипломдық жұмыс теориялық және практикалық бөлімнен тұрады. Теориялық бөлімде сұрыптау алгоритмдері жайлы толық ақпарат беріліп, практикалық бөлімде нақты есептерге қолданыстары келтіріліп, бағдарламалау тілінде бағдарламалары, олардың электронды есептегіш машинада орындалу нәтижесі, сандық массивтер үшін тестілеуден өткені толығымен көрсетілген. Соңында өз бетінше орындауға арнайы тапсырмалар келтірілген.
І СҰРЫПТАУ АЛГОРИТМДЕРІ
Сұрыптау (ағылш. sorting-жіктеу, ретке келтіру) - таңдалған өлшемге байланысты бір нәрсенің бірізді орналасуы немесе топтарға бөлінуі, анықталған рет бойынша элементтерді орналастыру процессі.
Сұрыптаудың мақсаты - сұрыпталған жиында элементтерді іздестіруді жеңілдету.
Сұрыптау әдістерінің классификациясын қарастыратын болсақ, ол сызықты құрылымдардағы сұрыптау және сызықты емес құрылымдардағы сұрыптау болып екіге бөлінеді.
Сызықтық іздеу - қажетті элементті массив элементтерін қарапайым бірінен кейін бірін эталонмен салыстыра отырып іздейтін процедура. Ол қою, таңдау және айырбастау болып бөлінеді.
Сызықты емес құрылымдардағы сұрыптау турнирлі және пирамидалы болып екі топқа ажыратылады.
Қою - қарапайым және бинарлық (екілік) қоюға, таңдау - қарапайым таңдау болып, айырбастау - стандартты, Шелл әдісі және Хоар әдістерінен құралады.
Сұрыптау әдістері
Сызықты құрылымдардағы сұрыптау
Сызықты емес құрылымдардағы сұрыптау
Қою
Таңдау
Айырбастау
Турнирлі
Пирамидалы
Қарапайым Стандартты
Қарапайым Шелл-әдісі
Бинарлы Хоар -әдісі
1-сурет. Сұрыптау алгоритмдері
Сұрыптау - бұл белгілі бір тәртіп қатынасына сәйкес: алфавит бойынша, өрістің сандық мәнінің өсуіне не кемуіне және т.б. кестенің жазбаларын немесе нақты жағдайда -массив элементтерін ретке келтіру.
Сұрыптау, біріншіден, массив элементтерін қажетті ретпен қарауға, өңдеуге мүмкіндік береді, екіншіден, массив элементтерін жылдам (екілік) іздеуге мүмкіндік береді.
Ол үшін жоғарыда байқағанымыздай, алгоритм қолданамыз. Ендеше алгоритм түсінігінен басталық.
2.1 Алгоритм түсінігі
Тарихи жағынан алгоритм термині ІХ ғасырда өмір сүрген шығыс математигі Мухаммед ибн Муса әл-Хорезми тегінен шыққан. Алғашында ол алгорифм деп аталды. Келе келе өзгеріске ұшырады - алгоритм.
Ол алғаш негізгі төрт арифметикалық амалдың ережесін құрастырған. Басында осы ережелер алгоритмдер деп аталып, кейіннен термин ары қарай дамуын ең алдымен математикада жалғастырды - алгоритм деп қандай-да бір бастапқы мәліметтер класына бірдей орындалатын есептеулер тәсілі атала бастады, мысалы, функцияның туындысын табу.
Математикаға оқытудың маңызды міндеттерінің бірі жалпы есептеу алгоритмдерін меңгерту болып табылады. Басқаша айтқанда, егер мектеп оқушысын екі санды бағанмен қосуға үйретсе, онда оған тек сол екі санды қосу ғана емес, жалпы кез-келген екі санды қосуға қолданылатын әмбебап тәсілді (алгоритмді) үйретуде дегенді білдіреді.
Мұндай мысалдарды көптеп келтіруге болады. Тек математикада ғана емес - алгоритм термині барлық салада қолданысқа ие болды.
Осыған байланысты сұрақ туындайды: алгоритмнің жалпы және нақты анықтамасын құруға болды ма (кез-келген алгоритм ұғымы )?
Мысалы, осы анықтаманы пайдаланып, қандай-да бір нұсқаулар жиынтығы алгоритм бола алатындығын немесе бола алмайтындығын анықтауға бола ма?
Егер дұрыс мағынада айтсақ, алгоритм дегеніміз - қандай-да бір класстың кез-келген есебін шешуді қамтамасыз ететін, бірмәнді нақты анықталған қарапайым әрекеттер тізбегі.
Бірақ бұл анықтаманы алгоритмнің қатаң анықтамасы ретінде қабылдауға болмайды. Себебі оның ішінде басқа анықталмаған ұғымдар қолданылған - бірмәнділік, қарапайымдылық және т.б.
Бұл ұғымдарды алгоритмге тән жалпы қасиеттерді көрсету арқылы жетілдіруге болады. Оларға төмендегі қасиеттер жатады:
1. Алгоритмнің дискреттілігі - алгоритмнің жеке қадамдарға бөлінетінін білдіреді, сол сияқты келесі қадамның орындалуы тек қана алдыңғы қадамдағы барлық амалдар орындалып болғаннан кейін ғана мүмкін болады. Мұнда аралық мәліметтер жиынтығы аяқталған және олар алдыңғы қадамдағы мәліметтерге қандай-да бір ережені қолдану арқылы алынады.
2. Алгоритмнің детерминерленгендігі - кез келген қадамдағы аралық шамалардың жиынтығы алдыңғы қадамда болған шамалар жүйесімен бірмәнді анықталатынын білдіреді. Бұл қасиет алгоритмнің нәтижесі оның орындаушысына байланысты емес, тек енгізілген мәліметтер мен алгоритмнің өзінің қадамдарына (әрекеттер тізбегіне) байланысты екенін білдіреді.
3. Қадамдардың қарапайымдылығы - келесі шамалар жиынтығын алдыңғыдан алу заңдылығы қарапайым әрі жергілікті болу керек. Қандай қадамды (әрекетті) қарапайым деп есептеуге болатыны алгоритм орындаушысының ерекшеліктеріне байланысты анықталады.
4. Алгоритмнің нәтижелілігі - егер қандай да бір бастапқы мәліметтерден келесі шамаларды алу тәсілі нәтижеге әкелмесе, онда алгоритм нәтижесі ретінде нені есептеу керектігі көрсетілуі керек.
5. Алгоритмнің жалпылығы - бастапқы шамалар жүйесі қандай да бір жиыннан таңдалынады. Бұл қасиет бір алгоритм, яғни бір әрекеттер жиынтығы, жалпы жағдайда, кандай-да бір есептер класын (яғни, көп есептерді) шешуге қолданылатынын білдіреді.
Практикада компьютерде есепті шешу үшін бұл қасиет маңызды, себебі, неғұрлым біртипті есептердің үлкен шеңберін шешуге мүмкіндік берсе, бағдарламаның пайдаланушылық құндылығы соғұрлым жоғары болады. Бірақ алгоритмдік теория құру үшін бұл қасиет қолданысқа ие емес және міндетті болып табылмайды.
Қасиеттерді көрсету арқылы анықталған алгоритм түсінігін қатаң деп есептеуге болмайды, себебі қасиеттерді айтқанда шама, тәсіл, қарапайым, жергілікті және басқа да нақты мағынасы ашылмаған терминдер пайдаланылды. Ары қарай бұл анықтаманы алгоритмнің қатаң емес түсінігі деп атаймыз.
Сұрақ туындайды: алгоритмнің нақты анықтамасын алу осыншама маңызды ма, егер онсыз да алгоритмдерді құрып, қолдануға болса (тіпті, терминнің өзін қолданбай-ақ)? Және де алгоритмнің интуитивті ұғымы қатаң болмаса да анық болды, тіпті ХХ ғасырға дейін қандай да бір процесстің алгоритм болатындығы немесе болмайтындығы туралы математиктер арасында дау туындаған жағдайы болған емес.
ХХ ғасырдың басында алгоритмдік шешілуі білінбейтін мәселелер туындаған кезде жағдай бірқатар өзгерді. Шынында да, алгоритмнің бар болуын дәлелдеу үшін белгілі бір тәсілдерді пайдаланып осы есепті шешу керек, немесе ол болмаса жаңа тәсілдерді ұсыну керек - мұндай жағдайда сипатталған процестің алгоритм екеніне көз жеткізу үшін алгоритмнің интуитивті ұғымы да жеткілікті.
Қандай да бір есепті немесе есептер класын шешу алгоритмін құрудың мүмкін еместігі фактісін дәлелдеу әлдеқайда күрделірек - алгоримнің нақты анықтамасынсыз бұл мәселе өзінің мағынасын жоғалтады.
Алгоритмнің нақты анықтамасын құруды қажет ететін басқа негіз - алгоритмдік әрекеттерді орындау кезінде қадамның қарапайымдылығы түсінігінің анықталмағандығы болып табылады.
Математика сандық объектілерді қарастырғанда олармен орындалатын әрекеттер есептеу амалдарының қандай да бір тізбегіне келтірілетін және арифметикалық амалдар, сол сияқты шамалар арасындағы қатынасты тексеруге байланысты бірнеше логикалық амалдар (теңдік, теңсіздік, кіші, үлкен және т.б.) элементар қадамдар деп есептелінеді.
Алайда математика кейінірек күрделі объектілердің (векторлар, матрицалар, жиындар, функциялар) қасиеттері мен оларға қолданылатын амалдарды зерттеуге көшті де, қадамның қарапайымдылығы түсінігі оңай көрінбейтін болды. Мысалы, интеграл алу немесе матрицаны транспонирлеуді қарапайым қадам деп қарастыруға бола ма?
Ақырында, есеп бірнеше алгоритм құруға мүмкіндік берген жағдайда теориялық және практикалық тұрғыдан алғанда оларды салыстыру және ең тиімдісін таңдау туралы сұрақ туындайды, бұл сұрақты шешу мәселесі де алгоритмнің қатаң анықтамасынсыз мүмкін емес.
Кез келген алгоритм ұғымының нақты анықтамасын, яғни, алгоритмнің барлық ойға келетін түрлері жатқызылатын максималды жалпы анықтамасын құру қажеттілігі осылайша туындады.
ХХ ғасырдың 20-шы жылдарында алгоритмнің нақты анықтамасын құру мәселесі маңызды математикалық мәселелердің біріне айналды. Бұл анықтама бір жағынан алгоритмнің интуитивті түсінігінің маңызына сәйкес келуі қажет болса, екінші жағынан формальды түрде қатаң болуы қажет болды. Осындай түсінікті құрастыру әрекеттері ХХ ғасырдың 30-шы жылдарында алгоритмдер теориясының өз алдына жеке ғылым болып қалыптасуына әкелді. Бұл ғылым математикалық логикамен бірге математиканың негізгі құралдарын - дәлелдеу тәсілдерін, аксиоматикалық теорияны құру тәсілдерін, математикалық процедуралардың қасиеттерін және т.б. қарастырады.
40-шы, 50-ші жылдарда есептеу техникасы мен оның функционалдануы мен қолданылуына байланысты ғылымдардың қарқынды дамуы кезінде осы ғылымдардың негізінде алгоритмдер теориясы жататыны анықталды, себебі компьютер алгоритмдер түрінде көрсетілетін процедураларды ғана жүзеге асыра алады.
Кез келген программа алгоритмнің орындаушы - компьютер түсінетін тілде жазылуы. Осылайша практикалық тұрғыдан алғанда да алгоритм ұғымын жетілдіру маңызды болып табылады.
Алгоритм түсінігін жетілдіру алгоритмдік модельдер аясында жүргізіледі. Модель есепті шешу кезінде қолдануға болатын құралдар жиынтығын көрсетеді, яғни, элементар қадамдар тізімін, келесі қадамды анықтау тәсілін, т.б.
Алгоритмдік модельдер теориялық және практикалық болуы мүмкін. Теориялық тұрғыдан алғанда модельдердің бір жағынан әмбебап болғаны, яғни, кез-келген алгоритмді сипаттауға мүмкіндік бергені, екінші жағынан неғұрлым қарапайым болғаны, яғни, есепті шешудің неғұрлым аз құралын пайдаланғаны ерекше қызығушылық тудырады. Қарапайымдылық талабы алгоритмнің нақты қажет элементтері мен қасиеттерін ерекшелеп, осы қасиеттер туралы жалпы тұжырымдарды дәлелдеуді қамтамасыз ету үшін маңызды. Практикалық және қолданбалы модельдерде программалаудың қолайлылығы мен есептеу тиімділігі маңыздырақ, сондықтан олардың құралдары (қарапайым қадамдар жиынтығы, т.б.) әлдеқайда көп және күрделірек, бұл теориялық анализді қиындатады.
Алгоритмнің қатаң анықтамасын құрудың теориялық қырларында тарихи жағынан негізгі үш бағыт бөлініп шықты.
Бірінші бағыт аргументтердің бүтін санды мәндеріне тәуелді сандық функциялардың мәндерін есептеуге мүмкіндік беретін алгоритмдерді қарастырумен байланысты - мұндай функциялар есептелінетін функциялар атауына ие болды. Есептелінетін функциялар ұғымы алгоритмдер ұғымы сияқты қатаң ұғым емес. Бірақ А.Черчтің, К.Гедельдің, С.Клинидің еңбектерінің арқасында барлық жерде анықталған есептелінетін функциялар класының қатаң анықталатын бөлікті рекурсиялы функциялар класымен ұқсастығы негізделді. Бұл алгоритмдік шешілу мәселесін есепті шешетін рекурсиялы функцияны құру мүмкіндігін (немесе мүмкін еместігін) дәлелдеуге келтіруге мүмкіндік берді. Дәл осы жолмен А.Черчке математикалық логиканың мәселелерінің бірі - предикаттардың ақиқаттығын есептеу мәселесінің шешілмейтіндігін дәлелдеудің сәті түсті.
Екінші бағыт машиналық математикамен байланысты.
Алгоритм орындаушысы - алгоритмде көрсетілген әрекеттер тізімін орындауға қабілетті субъект немесе құрылғы. Әрбір орындаушыға әрекеттерді орындауға нұсқау - арнайы тілдер арқылы беріледі. Мұнда әрекеттерді көрсететін қызметші сөздер, сол сияқты оларды біріктіретін синтаксикалық ережелер, командалар жиынтығы орындаушының командалар жиынтығын құрайды.
Дискретті информацияны өңдеудегі қарапайым бір белгіні екіншісімен ауыстыру болып табылады. Бірақ қарапайым әрекеттер тізімін орындайтын абстрактілі және шынайы құрылғы жасауға болады. Орындаушыға арналған мұндай алгоритм құру барысында интегралданған командалар тізбегін көрсету жеткілікті, ал оларды шын қарапайым командалар тізбегіне түрлендіруді орындаушы өзі атқарады. Мұндай алгоритмдеудің көпсатылылығы компьютерді басқару барысында көп қолданылады.
Шын қарапайым әрекет деп процессордың әрекеттерін айтуға болады. Қазіргі процессорларда олар бірнеше жүз немесе мыңға барады.
Оларды машиналық команда, ал белгіленуін машиналық кодтар деп атайды. Машиналық кодтардан бөлінген бірінші (төменгі) деңгейдегі ассемблер коды есептелінеді, яғни ішкі (аппараттық - тәуелді) тіл. Қарапайым әрекеттерді күрделі командаларға біріктіру бұл деңгейде әлі жүргізілмейді және ассемблердің жалпы командалар саны процессордың командалар санымен бірдей болады.
Бірақ машиналық пен процессор регистрлері-мнемоникаларда символдық бейнелеу формалары қолданылады. Бұл пайдаланушыға екілік машиналық кодтан қарағанда қолайлы.
Мнемониктерді машиналық командаларға аударуды - ассемблер программасы жүзеге асырады. Программист орындаушы ретінде осы тілмен жұмыс істейді. Қарапайым әрекеттерді біріктіретін командалар жоғары деңгейдегі программалау тілдерінде көрінеді. Мысалы, Write сөзін программа текстінде жазу жеткілікті. Ал транслятор оларды қарапайым қадамдарға айналдырады. Программистке қарағанда бұл жағдайда орындаушы программалау тілінің трансляторы есептеледі. Бұдан жоғары қарапайым интеграциялау деңгейлерін қолданбалы программалардан көреміз. Бұл жерде ақырғы пайдаланушыға қарағанда қолданбалы программа орындаушы болып тұр. Мұндау орындаушының командалар жүйесіне барлық басқару командалары кіреді, яғни меню, экрандық батырмалар және т.б. интерфейс элементтері.
Бір команданы орындау күрделі әрекеттердің тізімін орындауға әкеледі, мысалы текстің көп жолдарын туралау.
Осылайша алгоритмді жазу барысында алгоритмді көрсету тілі формальды болуы мүмкін, ал онда орындаушының өзімен шынайы қарапайым әрекеттерге аударылатын күрделі командалар қолданылады.
Сұрыптау есептері іздеу есептері секілді негізгі болып табылады. Практикада бұл есептер өзара байланысты. Сұрыптауға байланысты есептерді шешуге көптеген іргелі ғылыми зерттеулер, көптеген алгоритмдер жасалды.
Жалпы жағдайда сұрыптауды белгілі бір ретпен берілген объектілер жиынтығын қайта құру процесі деп түсіну керек. Көбінесе деректердің үлкен көлемін сұрыптау кезінде элементтердің өздерін қайта құру мүмкін емес, сондықтан мәселені шешу үшін элементтерді индекстер бойынша ретке келтіру жүзеге асырылады. Яғни, элементтердің индекстері оларға сәйкес келетін элементтердің мәндері мәселенің шарты бойынша сұрыпталатын ретпен құрылады.
Сұрыптау реттелген жиынтықтағы элементтерді табуды жеңілдету үшін қолданылады. Сұрыптау міндеті-бағдарламалаудағы негіздердің бірі.
Сұрыптау дегеніміз-бір типтегі мәліметтер жиынтығын өсу немесе кему бойынша реттеу.
Іздеу алгоритмінен басталық.
1.2 Іздеу және тандау алгоритмдері
Іздеу екіге бөлінеді: тізбектеліп іздеу, бинарлық іздеу.
1. Тізбектеліп іздеу
Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады.
Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп іздеу кез келген тізбек үшін қолайлы, тізбектеліп іздеудің орталық тиімділігі O(n) тең болады.
2. Бинарлық іздеу
Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады.
Бинарлық іздеудің алгоритмі:
1. Массивтің ортаңғы элементінің индексін табу: mid=(low+high)2.
2. Орталық элементтің мәнін кілтпен салыстыру Key. Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз.
3. Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз.
Мысалы: Бүтін сандардан тұратын А массиві берілсін. 33 кілті берілген элементі бар табу керек.
А элементтері:
0
1
2
3
4
5
6
7
8
-7
3
5
8
12
16
23
33
55
Low=0 High=8 mid=4
33A(mid)
0 1 2 3 4 5 6 7 8
-7
3
5
8
12
16
23
33
55
mid
Low=5
High=8
mid=6
33A(mid)
0 1 2 3 4 5 6 7 8
-7
3
5
8
12
16
23
33
55
mid
Low=7
High=8
mid=7
33=A(mid)
Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық іздеуде 3 салыстыру жүргізіледі.
Сұрыптау деректерді өңдеудің ең көп қолданылатын процедураларының бірі болғандықтан, сұрыптау алгоритмдерінің тиімділігіне өте жоғары талаптар қойылады.
Алгоритмдердің жұмысын теориялық тұрғыдан алынған бағалау арқылы да, эмпирикалық түрде де алгоритмдерді эксперименттік салыстыру арқылы бағалауға болады.
Теориялық өнімділік бағалары көбінесе сұрыпталған кесте жазбаларының санына байланысты сұрыптау уақытының өсу жылдамдығын бағалау түрінде көрінеді. Олар, мысалы: "бұл алгоритмде o(N2) рейтингі бар"дейді. Бұл N жазбаларының саны көбейген кезде, мысалы, 10 есе, алгоритмнің жұмыс уақыты шамамен 102 = 100 есе артады дегенді білдіреді. Бұл жағдайда максималды уақытты бағалауды (яғни, осы алгоритм үшін ең сәтсіз болған жағдайда) және орташа уақытты (яғни кездейсоқ кесте үшін сұрыптау уақытының математикалық күтуі) ажырату керек.
Үлкен мәндердегі алгоритмдердің мінез-құлқын салыстыру үшін "О-үлкенге дейінгі дәлдікпен" бағалаудың мағынасы бар, іс жүзінде үлкен N үшін O(N⋅log(N)) немесе осы мәнге жақын алгоритмдер қолайлы деп саналады, ал O(N2) бағалаумен сұрыптау алгоритмдері қолайсыз болып саналады.
Сонымен қатар, кестенің кішігірім өлшемдерінде, бірнеше ондаған жазбаны айталық, O(N2) бағалауы бар қарапайым алгоритмдер жақсы бағаланған күрделі алгоритмдерге қарағанда тезірек жұмыс істей алады.
Алгоритмдерді эксперименттік бағалау нақты нәтиже береді, бірақ бағаланатын бағдарламаның жұмыс уақыты алгоритмнің сапасына қосымша көптеген факторларға, атап айтқанда, компьютерлердің жұмысына және нақты сұрыпталған мәліметтерге байланысты, олар бірдей мөлшерде сыналған алгоритм үшін сәтсіздеу болуы мүмкін.
Эксперименттік бағалаудың компьютердің жұмысына тәуелділігін азайту үшін жұмыс уақытынан басқа, осы алгоритмге тән орындалған операциялардың санын жазып алған жөн. Сұрыптау үшін мұндай операциялар кесте элементтерінің кілттерін салыстыру және жазбаларды қайта құру (тағайындау) болып табылады. Сонымен қатар, зерттелген алгоритмді белгілі алгоритмдердің кез-келгенімен бірдей бастапқы деректермен салыстыру пайдалы.
Алгоритмді бағалауға нақты деректердің әсерін жою үшін кездейсоқ бастапқы деректермен сынақтарды бірнеше рет қайталау керек, алайда мұндай эксперименттер көп уақытты қажет етеді, сонымен қатар математикалық статистика әдістерін қолдана отырып нәтижелерді сауатты бағалау қажет.
Кестелерді сұрыптау кезінде жазу кілті (яғни жазбаларды салыстыру үшін қолданылатын жазбаның бөлігі) және кілттен басқа қосымша мәліметтер болуы мүмкін жазбаның өзі ерекшеленеді.
Сұрыптау алгоритмдері негізінен кілттерді салыстырудан және жазбаларды ауыстырудан тұрады және бір-бірінен салыстырылатын және ретке келтірілетін ретпен ерекшеленеді.
Массивтерді сұрыптау мәселесінде массив элементтерінің өздері кілттер болып табылады және олар қайта құрылады. Бұл айырмашылықтың маңыздылығы массивтер үшін сұрыптау алгоритмдерін зерттеуге мүмкіндік береді, Қажет болған жағдайда осы алгоритмдерді жалпы кестелер үшін оңай өзгертуге болады.
Енді ең танымал ішкі сұрыптау алгоритмдеріне қысқаша шолу жасалық.
Массивтерді сұрыптаудың қарапайым алгоритмдері
Қарапайым алгоритмдер, өкінішке орай, жоғары тиімділікпен ерекшеленбейтін келесі үш айқын және қарапайым алгоритмді қамтиды:
* Көпіршік алгоритмі (BubbleSort)
* Қарапайым таңдау алгоритмі (SelectionSort)
* Қарапайым кірістіру алгоритмі (InsertionSort)
1.3 Көпіршік алгоритмі (BubbleSort)
Көпіршік сұрыптау (көпіршік әдісімен сүрыптау) (Пузырьковая сортировка (сортировка методом пузырька); bublle sorting) -- реттелетін жиымның көрші элементтерін тізбектік орын ауыстырудан тұратын сұрыптау тәсілі.
Бұл әдіс тиімділік жағынан ең соңғы орынға ие болған, ең қарапайым ішкі әдістердің классына жатады. Бірақ, оған қарамастан, бұл әдіс кең танымал, өте тез еске сақталатын атының арқасында - судың бетіне шығатын көпіршік әдісі немесе батып бара жатқан доп әдісі.
Алгоритмнің идеясы келесідей:
Массивтің 1-ші және 2-ші индексті элементтерін салыстырамыз. Егер бірінші екіншіден артық болса, онда бұл элементтерді орындарымен ауыстырамыз. Одан соң 2 және 3-ші элементтерді, содан кейін 3 және 4-индексті элементтерді салыстырамыз (және қажет болса, өзгертеміз) т.с.с. Элементтерді салыстырғаннан кейін (N-1) және N алгоритмнің бірінші өтуі аяқталады. Осы өтуден кейін массивтің максималды элементі соңғы орында екендігіне кепілдік беруге болады (яғни, N индексі бар). Екінші жолда біз 1-ші және 2-ші, 2-ші және 3-ші жұптарын салыстырамыз ... (N-2) және (N-1). Әрі қарай осы іспеттес. N-1 өткеннен кейін барлық элементтер өздерінің заңды орындарын алады.
Келесі кезеңде қандай да бір орын ауыстыру жасалғанын арнайы белгімен белгілеп, өту санын азайтуға тырысуға болады. Егер бүкіл өту кезінде бірде-бір өзгеріс болмаса, онда массив қазірдің өзінде сұрыпталған және алгоритмнің жұмысын мерзімінен бұрын аяқтауға болады. Алайда, мұндай жағдай сирек айтарлықтай пайда әкеледі. Кездейсоқ толтырылған массив үшін 75% ықтималдылықпен алгоритмнің барлық өтуі әлі де орындалатынын көрсету қиын емес.
Мысалы. 6 элемент берілген болсын - 15, 33, 42, 07, 12, 19- бүтін сандар. Осы сандарды сұрыпталық (1-кесте).
Нәтижесінде, алты элемент үшін 5+4+3+2+1 = 15 салыстыру және 8 орын ауыстырулар өткізілді.
Көпіршікті алгоритмнің "шейкер сұрыптау"деп аталатын тағы бір модификациясы бар.
Бұл тақ жолдарда көпіршіктің солдан оңға қарай өтетіндігімен ерекшеленеді (циклдегі индекс артады), ал жұп жолдарда - оңнан солға (индекс азаяды). Осылайша, алғашқы екі өтуден кейін массивтің максималды және минималды элементтері өз орындарында болады.
Кесте 1. Сұрыптау амалдары
қадам
а1
а2
а3
а4
а5
а6
Амалдар
қадам1
15
33
42
07
12
19
салыстыру 19 және 12, ауыстыру жоқ
15
33
42
07
12
19
салыстыру 12 және 07, ауыстыру жоқ
15
33
07
42
12
19
салыстыру 07 және 42, орындарын ауыстырамыз
15
07
33
42
12
19
салыстыру 07 және 33, орындарын ауыстырамыз
07
15
33
42
12
19
салыстыру 07 және 15, орындарын ауыстырамыз; 07 - минималды
қадам 2
07
15
33
42
12
19
салыстыру 19 және 12, ауыстыру жоқ
07
15
33
12
42
19
салыстыру 12 және 42, орындарын ауыстырамыз
07
15
12
33
42
19
салыстыру 12 және 33, орындарын ауыстырамыз
07
12
15
33
42
19
салыстыру 12 және 15, орындарын ауыстырамыз, 12 - екінші минималды.
қадам3
07
12
15
33
19
42
салыстыру 19 және 42, орындарын ауыстырамыз
07
12
15
19
33
42
салыстыру 19 және 33, орындарын ауыстырамыз
07
12
15
19
33
42
салыстыру 19 және 15, ауыстыру жоқ, 15 - үшінші минималды.
қадам4
07
12
15
19
33
42
салыстыру 42 және 33, ауыстыру жоқ
07
12
15
19
33
42
салыстыру 33 және 19, ауыстыру жоқ, 19 - төртінші элемент.
қадам 5
07
12
15
19
33
42
салыстыру 42 және 33, ауыстыру жоқ, сұрыптау аяқталды
07
12
15
19
33
42
Бұл алгоритмнің негізгі мағынасы алмастыру бойынша сұрыптауға жатады. Айрымашылығы, алмастыру бойынша сұрыптау тек бір бағыт бойынша жүргізілетіндігін байқадық, ал бұл жағдайда бағыт әрбір рет өзгеріп тұрады. Бұл сұрыптауда ауыстырулар туралы және соңғы алмастыру жасалған орынды есте сақтап отырады. Базалық алгоритмде екілік сүзгі саны N div 2 - ге тең.
Біріншіден, егер массив бөлігінде қозғалыстарда орын ауыстырулар болмаса онда массивтің бұл бөлігі сұрыпталған болып есептеледі, сондықтан, оны қарастырудан алып тастауға болады.
Екіншіден, массивтің соңынан басына дейін өткенде минималды элемент бірінші позицияға тұрады, ал максималды элемент тек бір позицияға оң жаққа қарай қозғалады.
Массивтің жұмыс бөлігінің шектері әр итерацияның орын ауыстыруында орнықтырылады. Массив рет бойынша оң жақтан сол жаққа және сол жақтан оң жаққа кезек кезек қарастырылады.
Бұл сұрыптаудың үздік жағдайы -- сұрыпталған массив (О(n)), ең жаманы -- кері бағытта сұрыпталған массив (O(n²)).
Салыстырулар санының ең кіші мәні Шейкер-сұрыптауында C=N-1. Бұл сұрыпталған массивте тек бір өтуге сәйкес.
1.4 Қарапайым таңдау алгоритмі (SelectionSort)
Бұл алгоритмнің идеясы одан да қарапайым:
Массивтің минималды элементін табамыз және оны бірінші элементпен ауыстырамыз. Содан кейін сол процедураны қайталаймыз, массивтің екінші элементінен бастап, содан кейін үшіншіден бастап және т.б. N-1 өтуден кейін барлық элементтер орнында болады.
1.5 Қарапайым кірістіру алгоритмі (InsertionSort)
Идея келесідей:
Алгоритмнің белгілі бір сәтінде массивтің алғашқы k элементтері сұрыпталсын, яғни, өсу бойынша орналастырылған.
Келесі кезеңде біз (k+1) элементтерін сұрыптауға тырысамыз. Ол үшін R жұмыс айнымалысындағы элементтің мәнін (k+1) есте сақтаймыз және R-ны K, (k-1), (k-2) және т.б. элементтердің мәндерімен салыстырамыз.
Салыстыру R элементі орналастырылатын орын табылғанша жалғасады (бұл келесі салыстырылатын элемент R-ден кіші немесе оған тең болған кезде немесе массивтің басына жеткенде болады).
Осылайша, келесі кезеңде массивтің сұрыпталған бөлігі 1 элементке артады. K = 1 мәнінен бастап, N-1 өту үшін бүкіл массивті сұрыптауға болады.
Қарапайым кірістіру алгоритмін k+1 элементін кірістіру үшін орынды k-дан 1-ге дейінгі элементтерді дәйекті қарау арқылы емес, бинарлы іздеу арқылы жақсартуға болады (яғни R-ді J: = (k+1) div 2 элементімен салыстырыңыз, содан кейін аралықтардың бірінде іздеуді жалғастырыңыз [1..j-1] немесе [j + 1..k] және т.б.).
Бинарлы кірістіру алгоритмі деп аталатын бұл тәсіл салыстыру санын едәуір азайтады, бірақ, өкінішке орай, орын ауыстыру санына әсер етпейді.
Қарапайым алгоритмдерді салыстыру
Жоғарыда аталған үш алгоритмнің барлығы және олардың барлық модификациялары максималды және орташа бағалау O (N2), сондықтан үлкен массивтер немесе сұрыптау уақытына қатаң талаптар болмаған жағдайда ғана қолданылады.
Тәжірибелер көрсеткендей, көпіршікті алгоритм әдетте үшеуінің ішіндегі ең баяу, ал таңдау және кірістіру алгоритмдері шамамен бірдей сұрыптау уақытын береді.
Кейбір жағдайларда бастапқы массив "сұрыпталған дерлік" болады деп күтуге болады, яғни элементтердің аз ғана бөлігі тәртіпті бұзады.
Бұл, мысалы, егер массив бұрын сұрыпталған болса, бірақ содан кейін ондағы мәліметтер аздап өзгертілген. Бұл жағдайда сұрыпталған дерлік массивтерде өте жоғары жылдамдықты көрсететін алгоритмдері бәсекелестіктен тыс қалады.
Кірістіру алгоритмдерінің бұл ерекшелігі төменде сипатталған Шелл алгоритмінде қолданылады.
1.6 Массивтерді сұрыптаудың жетілдірілген алгоритмдері
Алгоритмдердің күрделенуі үлкен массивтерді сұрыптаудың тиімділігін едәуір арттырады. Біз осы кластың ең танымал алгоритмдерін атап өтелік.
1.6.1 Шелл алгоритмі
Бұл әдіс Дональд Л. Шелл ұсынған, орналасқан жері бойынша тұрақсыз сұрыптау болып табылады. Шелл әдісі қосулар әдісінің жақсартылған нұсқасы.
Сұрыпталған массивтің элементтерін h тізбектеріне бөлеміз, олардың әрқайсысы бір бірінен h қашықтықта орналасқан элементтерден тұрады (мұнда h-ерікті натурал сан).
Бірінші тізбекте 1, h+1, 2h+1, 3h+1 және т.б. индекстері бар элементтер болады, екіншісі - 2, h+2, 2h+2 және т. б., соңғы тізбек - h, 2h, 3h және т. б.
Бұл үшін қарапайым кірістіру әдісін қолдана отырып, әр тізбекті бөлек массив ретінде сұрыптаймыз.
Содан кейін біз жоғарыда айтылғандардың барлығын h - тың бірқатар мәндері үшін орындаймыз, ал соңғы рет - h=1 үшін.
Осыдан кейін массив сұрыпталатыны анық.
h1-дегі барлық жолдар уақытты ысырап етпегені анық емес. Алайда, үлкен h-тағы элементтердің алыс қашықтықтары массивті сұрыпталған күйге жақындатқаны соншалық, соңғы өту кезінде өте аз жұмыс қалады.
Тәжірибелер көрсеткендей, үлкен мәндер үшін алгоритмнің орташа жұмыс уақытын бағалау шамамен O(N 1.26). Бұл қарапайым алгоритмдер үшін O(N2)-ге қарағанда әлдеқайда жақсы.
Шелл алгоритмінің тиімділігі үшін h мәндерінің кему тізбегін сәтті таңдау үлкен мәнге ие. Көршілес k мәндерімен hk мәндері бір-біріне еселік болмағаны жөн.
Әдебиеттерде, әдетте, екі тізбектің біреуін қолдану ұсынылады:
h k+1 = 3hk + 1 немесе hk+1 = 2hk+1.
Екі жағдайда да бастапқы hk ретінде барлық сұрыпталған тізбектердің ұзындығы кемінде 2 болатын тізбектен осындай мән таңдалады.
Пайдалану үшін, мысалы, осы формулалардың біріншісін алдымен h1:=1 қою керек, содан кейін келесі hk үшін hk =(N - 1) div 3 теңсіздігі орындалғанға дейін hk+1: = 3*hk+1 формуласы бойынша циклде h мәнін арттыру керек.
Бұл hk мәні алгоритмнің бірінші жолында қолданылуы керек, содан кейін кері формула бойынша келесі мәндерді алуға болады:
h k-1 := (hk-1) div 3, h1=1 дейін.
Неғұрлым күрделі формулалар Седжвик тізбегін анықтайды:
hk=9∙2k-9∙2k2+1, егер k-тақ болса8∙2k-6∙2k+12+1, егер k-жұп болса
hk - ны Седжвик бойынша таңдау кезінде алгоритмнің орташа жұмыс уақыты O(N76), ал максимум O(N43) болатындығы дәлелденген.
Практикада Седжвик тізбегінің жеткілікті мүшелерін тек бір рет есептеу ыңғайлы
(олар: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929,16001, 36289, 64769, 146305, 260609, 587521, 1045505, ...),
содан кейін берілген N бойынша k таңдаймыз, онда hk = (N - 1) div 3, содан кейін циклде k кемуі бойынша hk тізбегінің мәндерін таңдаймыз.
1.6.2 Жылдам сұрыптау алгоритмі (QuickSort)
Бұл әдісті 1962 жылы Оксфорд университетінің профессоры К.Хоар жасап шығарған.
Бұл алгоритм массивті бөлу операциясына негізделген.
Айталық, x-сұрыпталатын массивтің кездейсоқ таңдалған элементі болсын (элементті бөлу).
Бөлу операциясы массив элементтерін алдымен x-тен кіші немесе оған тең (міндетті түрде өсу ретімен емес), содан кейін x-тен үлкен немесе оған тең болатын элементтер болатындай етіп өзгертуге бағытталған.
Бөлуді орындау үшін массив элементтерін солдан оңға қарай қарап, x-тен үлкен немесе оған тең элементтердің біріншісіне тоқталайық. сол элементтің индексі i болсын. Біз i және j элементтерін ауыстырамыз, содан кейін i-ден оңға және j-ден солға қарай жүре береміз, орнында тұрмаған элементтердің жұптарын ауыстырамыз.
Бөлу ij болған кезде аяқталады.
Жылдам сұрыптау алгоритмін келесідей түрде сипаттауға болады.
X массивінің кез келген элементін алып, оны бөлу әрекетін орындаймыз. Егер массивтің сол жәненемесе оң сегменттерінде бірден артық элемент болса, онда біз осы кесіндінің әрқайсысы үшін массивке орындалған барлық әрекетті орындаймыз (яғни, еркін элементті таңдаймыз, бөлуді орындаймыз және т.б.).
Жоғарыда келтірілген бірнеше мәрте бөлу операциясын орындауды ұйымдастырудан көрі рекурсивті айқындау рәсімі көмегімен сұрыптау оңайырақ.
Алгоритмнің рекурсивті емес сипаттамасы қиынырақ, өйткені қажет болған жағдайда бөлінгеннен кейін пайда болған массивтің екі аралығын сұрыптау керек, екіншісі сұрыпталған кезде аралықтардың бірін (дәлірек айтқанда, оның индекстерінің екі шекаралық мәні) стекке нақты сақтау керек. Сонымен қатар, рекурсивті емес нұсқа әдетте тиімдірек болады және, ең бастысы, пайдаланылған стек тереңдігін азайтуға мүмкіндік береді.
Мұны істеу үшін біз әрқашан сұрыпталатын массивтің екі аралығынан ұзағырақ стекке әкелуісіз керек. Бұл жағдайда бір уақытта стекте орналасқан аралықтардың максималды саны log2(N) - нен аспауы керек.
Жылдам сұрыптау алгоритмінің тиімділігіне таңдау да әсер етеді.
Теориялық тұрғыдан алғанда, x еркін түрде таңдалуы мүмкін, бірақ егер бастапқы массив сұрыпталған немесе сұрыпталғанға жақын болса, бірінші немесе соңғы элементтің x ретінде таңдау өте нашар нәтижелерге әкелетінін көруге болады. Осыған байланысты x ретінде массивтің ортасынан элементті немесе кездейсоқ таңдалған индексі бар элементті таңдау әдеттегідей.
Кейде сәл күрделі ереже қолданылады: массивтің бірінші элементін, соңғы элементті, массивтің ортасынан элементті алып, осы үшеуінің орташа мәнін x ретінде таңдаңыз.
QuickSort алгоритмінде O(n⋅log(N)) орташа уақыт бағасы бар және іс жүзінде ол басқаларға қарағанда тезірек болады, алайда болмаған жағдайда ол O(N2) ретіне сәйкес уақытты қажет етуі мүмкін.
Кейбір жағдайларда QuickSort-ты көпіршікті алгоритммен біріктіру орынды болуы мүмкін. Шындығында, бөлу процедурасы массивтің бөлінген сегменттері қысқа болған кезде өте аз пайдалы жұмыс жасайды. Ұзындығы L-ден аспайтын сегменттерді бөлуге болмайды, содан кейін "көпіршіктің"L-1 өтуін орындау арқылы массивті сұрыптауға болады. Көптеген қысқа массивтер үшін "көпіршіктің" жеке өтуін ұйымдастырудың қажеті жоқ, сұрыпталған массивте "көпіршікті" өткізіп жіберу оңайырақ.
Тәжірибе көрсеткендей, L мәні 3 - 4-тен аспайды.
1.6.3 Пирамидалық сұрыптау алгоритмі (HeapSort)
Бұл алгоритм пирамида ұғымына негізделген.
Оны 1964 жылы америкалық ғалымдар Дж. У. Дж. Уильямс мен Р.У. Флойд ұсынған еді.
A1, A2, ... AN массиві пирамида деп аталады, егер:
2k = N болатын барлық k үшін Ak = A2k;
2k+1 = n болатын барлық k үшін Ak = A2k+1 болса.
Пирамиданы массив түрінде ұсынылған екілік ағаш ретінде қарастыруға болады, оның ата-аналық шыңмен байланысты мәні ұлдармен байланысты мәндерден кем емес. Сонымен қатар, A1-ағаштың тамыры, A2 және A3-оның ұлдары, A4, ... A7-немерелері және т. б.
Сұрыптау алгоритмі екі кезеңнен тұрады: пирамида салу және пирамиданы сұрыпталған массивке айналдыру. Әрбір фазаның негізінде пирамида арқылы элементтерді електен өткізу операциясы жатыр.
Електен өткізу операциясының мәні келесідей.
Жоғарыда келтірілген теңсіздіктер бұзылуы мүмкін элементтердің тек біреуі үшін "дұрыс" пирамида бар делік. Пирамиданың дұрыстығын қалпына келтіру үшін алдымен Ak ұлдарын, яғни A2k және A2k+1 элементтерін салыстыру керек. Осы элементтердің үлкен санын r әрпімен белгілеңіз. Енді сіз Ar-ді әкемен (ak элементімен) салыстыруыңыз керек, егер Ak = Ar теңсіздігі бұзылса, онда Ak және Ar-ді ауыстырыңыз.
Енді Ak үшін екі теңсіздік орындалады, бірақ Ar үшін ұқсас теңсіздіктер бұзылуы мүмкін. Сондықтан k:=r қою керек және келесі итерацияда Ak элементінің ұлдары жоқ немесе ол үшін қажетті теңсіздіктер орындалғанға дейін сол әрекеттерді циклдік түрде қайталау керек. Бұл жағдайда Ak элементін елеу процесі аяқталады.
Егер пирамиданы екілік ағаш ретінде елестетсек, онда ол ағаштың бір бұтағының бойымен Ак элементінің "құлауы" сияқты болады.
Пирамиданың құрылысы элемент арқылы басталады, оның индексі k:= N div 2 (бұл ағашта ұлдары бар элементтердің ең оң жағы). Бұл элементті елегеннен кейін, k индексінен бастап массивтің соңына дейінгі ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
5
І СҰРЫПТАУ АЛГОРИТМДЕРІ
8
0.1 Алгоритм түсінігі
9
0.2 Іздеу және тандау алгоритмдері
13
0.3 Көпіршік алгоритмі
16
1.4 Қарапайым таңдау алгоритмі
18
1.5 Қарапайым кірістіру алгоритмі
18
1.6 Массивтерді сұрыптаудың жетілдірілген алгоритмдері
19
1.6.1 Шелл алгоритмі
19
1.6.2 Жылдам сұрыптау алгоритмі
20
1.6.3 Пирамидалық сұрыптау алгоритмі
22
1.6.4 Біріктіру алгоритмдері
24
ІІ САНДЫҚ МАССИВТЕРДІ СҰРЫПТАУ
26
0.1 Массив түсінігі
26
0.2 Массивтерді сұрыптау
31
2.2.1Таңдау арқылы сұрыптау
32
2.2.2Ауыстыру арқылы сұрыптау
34
2.2.3 Шейкерлік сұрыптау
39
2.2.4 Тікелей қосу сұрыптауы
44
2.2.5 Пирамидалық сұрыптау
53
2.3 Оқушылардың массивті сұрыптауға өз бетінше орындауына арналған тапсырмалар
57
ҚОРЫТЫНДЫ
60
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР
61
КІРІСПЕ
Қазіргі таңда заманымыздың цифрланған дәуірге қадам басқан кезеңінде көптеген мамандардың функционалдық міндеттерін сәтті орындауы көбінесе дербес компьютерлерді, байланыс құралдарын, қолданбалы бағдарламалардың кәсіби пакеттерін және әртүрлі зияткерлік ақпараттық технологияларды шебер қолдануымен анықталады.
Қоғамды ақпараттандыру процестері информатика және басқару процестерін компьютерлендіру саласындағы білімді қалыптастыруды қажет етеді.
Қазіргі уақытта жаңа ақпараттық технологиялар мамандандырылған ғана емес, сонымен қатар күнделікті өмірде де маңызды орын алады. Компьютерлер бизнесте, басқаруда, саудада, оқуда және адам қызметінің көптеген басқа салаларында қолданылады.
Компьютерлік технологиялар әртүрлі операцияларды орындау үшін өте ыңғайлы, бірақ әр түрлі қолдану салаларында бұл операциялар әртүрлі. Сондықтан нақты техникалық құралдарды қолданатын әрбір жеке сала компьютерлердің жұмысын қамтамасыз ететін өз бағдарламаларын қажет етеді.
Бағдарламалық жасақтаманы бағдарламалау сияқты ғылым саласы жасайды. Бұл соңғы уақытта барған сайын маңызды бола түсуде, өйткені күн сайын компьютер біздің өміріміздің қалыпты құбылысына айналуда.
Осылайша, жаңа ақпараттық технологиялар біздің заманымызда өте өзекті және кейінгі даму мен жетілдіруге көп көңіл бөлуді қажет етеді. Сонымен қатар, бағдарламалаудың да маңызы зор, ол информатиканың іргелі бөлімдерінің бірі болып табылады, сондықтан қазіргі таңда оған өте қатты көңіл бөлінуде.
Бағдарламалау бірқатар маңызды ішкі міндеттерді қамтиды.
Бағдарламалауда үлкен көлемдегі мәліметтерді өңдеумен байланысты тапсырмалар жиі кездеседі. Мәліметтердің бүкіл көлемін бағдарлама ішінде сақтау үшін массивтер қолданылады - құрылымдалған деректер түрлерінің қарапайым түрі.
Массив - бірдей элементтерді сақтайтын жад аймақтарының белгілі тізбегі. Әрбір осындай жад аймағы массив элементі деп аталады. Массивтерде олардың құрамындағы элементтердің саны, сондай ақ бағдарламада бір және көп өлшемді массивтерді сипаттау мүмкіндігін білдіретін өлшем бар. Массивтегі элементтер саны оның мөлшері деп аталады.
Бағдарламалаудың маңызды міндеттерінің бірі - сұрыптау мәселесі.
Сұрыптау есептері іздеу есептері сияқты базалық болып табылады. Практикалық жағдайда бұл міндеттер өзара байланысты. Сұрыптауға байланысты мәселелерді шешуге көптеген іргелі ғылыми зерттеулер, көптеген алгоритмдер жасалды.
Жалпы жағдайда сұрыптауды белгілі бір ретпен берілген объектілер жиынтығын қайта құру процесі деп түсіну керек. Көбінесе мәліметтердің ауқымды көлемін сұрыптау кезінде элементтердің өздерін қайта құру мүмкін емес, сондықтан мәселені шешу үшін элементтерді индекстер бойынша ретке келтіру жүзеге асырылады. Яғни, элементтердің индекстері оларға сәйкес келетін элементтердің мәндері мәселенің шарты бойынша сұрыпталатын ретпен құрылады.
Маманды қалыптастыру мектеп қабырғасынан басталады. Ендеше, орта білім беру мектептерінде 7-9 сыныптарда массивтер, оларды жариялау және өңдеу туралы жалпы түсінік ала отырып, баланың бағдарламалау туралы алғашқы идеялары туындап, қызығушылығы артатыны мүмкін екенін атап өтуге болады. Сонда оқытудың келесі кезеңінде мамандандырылған сыныптарда мұғалім мен оқушы бағдарламалық жасақтаманы жасау үшін мейлінше жан жақты қолданылатын, заманауи бағдарламалау тілін алады.
Осылайша, мұғалім массивтерді сұрыптауға, элементтерді іздеуге байланысты көптеген мәселелерді шешуге жақындай алады, бұл оқытудың мамандандырылған кезеңінде оқушыға қысқа мерзімде әр түрлі мәселелерді шешуге мүмкіндік береді.
Бұл жұмыста теориялық бөлімде тек мектеп информатикасы ғана емес жалпы информатикада қолданылатын сұрыптау алгоритмдері толық қамтылды.
Жұмыстың теориялық бөлігін орындау кезінде әр алгоритмнің қасиеттерін егжей-тегжейлі ашатын келесі сұрақтарға жауап беріледі, атап айтқанда:
қандай салыстыру элементтер жұбының реттілігін анықтайды?
қандай орын ауыстыру бірнеше элементті өзгертеді?
жиынтықтың барлық элементтері реттелгенге дейін элементтерді салыстыру мен қайта құруды жүзеге асыратын сұрыптау алгоритмі қандай?
Қарастырылған сұрыптау алгоритмдерінің бәріне қасиеттер ортақ деп айтуға болады. Олар көптеген алгоритмдерден таңдалады, өйткені біріншіден, олар жиі қолданылады, екіншіден, басқа алгоритмдердің көпшілігі осы алгоритмдердің әртүрлі сипатталған түрлері деп айтуға болады.
Практикалық бөлімде бағдарламалау тілін қолдана отырып, есептер шешуге бағдарлама құру арқылы бар білімімізді бекітеміз.
Сондай-ақ, бұл жұмыста деректерді практикалық тұрғыдан реттеу мәселесі, яғни сұрыптау әдістерінің артықшылықтары мен кемшіліктері айтылған.
Дипломдық жұмысты орындау кезінде ABC Pascal бағдарлама ортасын қолданылды. Және жұмыстың мәтіндік бөлігін орындауға Microsoft Word қосымшасын пайдаланылды.
Microsoft Word-бұл әртүрлі құжаттар мен деректерді құруға, өңдеуге, экранға шығаруға және басып шығаруға, сонымен қатар файл түрінде сақтауға арналған мәтіндік редактор. Ол аталған операциялармен қатар мәтінді форматтауға (құжаттың бүкіл және оның бір бөлігі бойынша), құжаттарды ресімдеудің әртүрлі стильдерін қалыптастыруға, қаріптердің көп санын пайдалануға, мәтін фрагменттерін бөлуге (курсивпен, астын сызумен, қалың қаріппен және басқа да құралдармен), мәтінді бағандар түрінде теруге, иллюстрацияларды мәтіндерге қосуға, әр түрлі көрсеткіштер мен сілтемелерді қалыптастыруға, беттердің жоғарғы және төменгі колонтитулдарын енгізуге, мәтін элементтерін автоматтандырылған іздестіруді жүргізуге және қателерді, мәтіннің кез-келген бөлігін басқа орынға көшіруге және орын ауыстыруға қабілетті.
Дипломдық жұмыс теориялық және практикалық бөлімнен тұрады. Теориялық бөлімде сұрыптау алгоритмдері жайлы толық ақпарат беріліп, практикалық бөлімде нақты есептерге қолданыстары келтіріліп, бағдарламалау тілінде бағдарламалары, олардың электронды есептегіш машинада орындалу нәтижесі, сандық массивтер үшін тестілеуден өткені толығымен көрсетілген. Соңында өз бетінше орындауға арнайы тапсырмалар келтірілген.
І СҰРЫПТАУ АЛГОРИТМДЕРІ
Сұрыптау (ағылш. sorting-жіктеу, ретке келтіру) - таңдалған өлшемге байланысты бір нәрсенің бірізді орналасуы немесе топтарға бөлінуі, анықталған рет бойынша элементтерді орналастыру процессі.
Сұрыптаудың мақсаты - сұрыпталған жиында элементтерді іздестіруді жеңілдету.
Сұрыптау әдістерінің классификациясын қарастыратын болсақ, ол сызықты құрылымдардағы сұрыптау және сызықты емес құрылымдардағы сұрыптау болып екіге бөлінеді.
Сызықтық іздеу - қажетті элементті массив элементтерін қарапайым бірінен кейін бірін эталонмен салыстыра отырып іздейтін процедура. Ол қою, таңдау және айырбастау болып бөлінеді.
Сызықты емес құрылымдардағы сұрыптау турнирлі және пирамидалы болып екі топқа ажыратылады.
Қою - қарапайым және бинарлық (екілік) қоюға, таңдау - қарапайым таңдау болып, айырбастау - стандартты, Шелл әдісі және Хоар әдістерінен құралады.
Сұрыптау әдістері
Сызықты құрылымдардағы сұрыптау
Сызықты емес құрылымдардағы сұрыптау
Қою
Таңдау
Айырбастау
Турнирлі
Пирамидалы
Қарапайым Стандартты
Қарапайым Шелл-әдісі
Бинарлы Хоар -әдісі
1-сурет. Сұрыптау алгоритмдері
Сұрыптау - бұл белгілі бір тәртіп қатынасына сәйкес: алфавит бойынша, өрістің сандық мәнінің өсуіне не кемуіне және т.б. кестенің жазбаларын немесе нақты жағдайда -массив элементтерін ретке келтіру.
Сұрыптау, біріншіден, массив элементтерін қажетті ретпен қарауға, өңдеуге мүмкіндік береді, екіншіден, массив элементтерін жылдам (екілік) іздеуге мүмкіндік береді.
Ол үшін жоғарыда байқағанымыздай, алгоритм қолданамыз. Ендеше алгоритм түсінігінен басталық.
2.1 Алгоритм түсінігі
Тарихи жағынан алгоритм термині ІХ ғасырда өмір сүрген шығыс математигі Мухаммед ибн Муса әл-Хорезми тегінен шыққан. Алғашында ол алгорифм деп аталды. Келе келе өзгеріске ұшырады - алгоритм.
Ол алғаш негізгі төрт арифметикалық амалдың ережесін құрастырған. Басында осы ережелер алгоритмдер деп аталып, кейіннен термин ары қарай дамуын ең алдымен математикада жалғастырды - алгоритм деп қандай-да бір бастапқы мәліметтер класына бірдей орындалатын есептеулер тәсілі атала бастады, мысалы, функцияның туындысын табу.
Математикаға оқытудың маңызды міндеттерінің бірі жалпы есептеу алгоритмдерін меңгерту болып табылады. Басқаша айтқанда, егер мектеп оқушысын екі санды бағанмен қосуға үйретсе, онда оған тек сол екі санды қосу ғана емес, жалпы кез-келген екі санды қосуға қолданылатын әмбебап тәсілді (алгоритмді) үйретуде дегенді білдіреді.
Мұндай мысалдарды көптеп келтіруге болады. Тек математикада ғана емес - алгоритм термині барлық салада қолданысқа ие болды.
Осыған байланысты сұрақ туындайды: алгоритмнің жалпы және нақты анықтамасын құруға болды ма (кез-келген алгоритм ұғымы )?
Мысалы, осы анықтаманы пайдаланып, қандай-да бір нұсқаулар жиынтығы алгоритм бола алатындығын немесе бола алмайтындығын анықтауға бола ма?
Егер дұрыс мағынада айтсақ, алгоритм дегеніміз - қандай-да бір класстың кез-келген есебін шешуді қамтамасыз ететін, бірмәнді нақты анықталған қарапайым әрекеттер тізбегі.
Бірақ бұл анықтаманы алгоритмнің қатаң анықтамасы ретінде қабылдауға болмайды. Себебі оның ішінде басқа анықталмаған ұғымдар қолданылған - бірмәнділік, қарапайымдылық және т.б.
Бұл ұғымдарды алгоритмге тән жалпы қасиеттерді көрсету арқылы жетілдіруге болады. Оларға төмендегі қасиеттер жатады:
1. Алгоритмнің дискреттілігі - алгоритмнің жеке қадамдарға бөлінетінін білдіреді, сол сияқты келесі қадамның орындалуы тек қана алдыңғы қадамдағы барлық амалдар орындалып болғаннан кейін ғана мүмкін болады. Мұнда аралық мәліметтер жиынтығы аяқталған және олар алдыңғы қадамдағы мәліметтерге қандай-да бір ережені қолдану арқылы алынады.
2. Алгоритмнің детерминерленгендігі - кез келген қадамдағы аралық шамалардың жиынтығы алдыңғы қадамда болған шамалар жүйесімен бірмәнді анықталатынын білдіреді. Бұл қасиет алгоритмнің нәтижесі оның орындаушысына байланысты емес, тек енгізілген мәліметтер мен алгоритмнің өзінің қадамдарына (әрекеттер тізбегіне) байланысты екенін білдіреді.
3. Қадамдардың қарапайымдылығы - келесі шамалар жиынтығын алдыңғыдан алу заңдылығы қарапайым әрі жергілікті болу керек. Қандай қадамды (әрекетті) қарапайым деп есептеуге болатыны алгоритм орындаушысының ерекшеліктеріне байланысты анықталады.
4. Алгоритмнің нәтижелілігі - егер қандай да бір бастапқы мәліметтерден келесі шамаларды алу тәсілі нәтижеге әкелмесе, онда алгоритм нәтижесі ретінде нені есептеу керектігі көрсетілуі керек.
5. Алгоритмнің жалпылығы - бастапқы шамалар жүйесі қандай да бір жиыннан таңдалынады. Бұл қасиет бір алгоритм, яғни бір әрекеттер жиынтығы, жалпы жағдайда, кандай-да бір есептер класын (яғни, көп есептерді) шешуге қолданылатынын білдіреді.
Практикада компьютерде есепті шешу үшін бұл қасиет маңызды, себебі, неғұрлым біртипті есептердің үлкен шеңберін шешуге мүмкіндік берсе, бағдарламаның пайдаланушылық құндылығы соғұрлым жоғары болады. Бірақ алгоритмдік теория құру үшін бұл қасиет қолданысқа ие емес және міндетті болып табылмайды.
Қасиеттерді көрсету арқылы анықталған алгоритм түсінігін қатаң деп есептеуге болмайды, себебі қасиеттерді айтқанда шама, тәсіл, қарапайым, жергілікті және басқа да нақты мағынасы ашылмаған терминдер пайдаланылды. Ары қарай бұл анықтаманы алгоритмнің қатаң емес түсінігі деп атаймыз.
Сұрақ туындайды: алгоритмнің нақты анықтамасын алу осыншама маңызды ма, егер онсыз да алгоритмдерді құрып, қолдануға болса (тіпті, терминнің өзін қолданбай-ақ)? Және де алгоритмнің интуитивті ұғымы қатаң болмаса да анық болды, тіпті ХХ ғасырға дейін қандай да бір процесстің алгоритм болатындығы немесе болмайтындығы туралы математиктер арасында дау туындаған жағдайы болған емес.
ХХ ғасырдың басында алгоритмдік шешілуі білінбейтін мәселелер туындаған кезде жағдай бірқатар өзгерді. Шынында да, алгоритмнің бар болуын дәлелдеу үшін белгілі бір тәсілдерді пайдаланып осы есепті шешу керек, немесе ол болмаса жаңа тәсілдерді ұсыну керек - мұндай жағдайда сипатталған процестің алгоритм екеніне көз жеткізу үшін алгоритмнің интуитивті ұғымы да жеткілікті.
Қандай да бір есепті немесе есептер класын шешу алгоритмін құрудың мүмкін еместігі фактісін дәлелдеу әлдеқайда күрделірек - алгоримнің нақты анықтамасынсыз бұл мәселе өзінің мағынасын жоғалтады.
Алгоритмнің нақты анықтамасын құруды қажет ететін басқа негіз - алгоритмдік әрекеттерді орындау кезінде қадамның қарапайымдылығы түсінігінің анықталмағандығы болып табылады.
Математика сандық объектілерді қарастырғанда олармен орындалатын әрекеттер есептеу амалдарының қандай да бір тізбегіне келтірілетін және арифметикалық амалдар, сол сияқты шамалар арасындағы қатынасты тексеруге байланысты бірнеше логикалық амалдар (теңдік, теңсіздік, кіші, үлкен және т.б.) элементар қадамдар деп есептелінеді.
Алайда математика кейінірек күрделі объектілердің (векторлар, матрицалар, жиындар, функциялар) қасиеттері мен оларға қолданылатын амалдарды зерттеуге көшті де, қадамның қарапайымдылығы түсінігі оңай көрінбейтін болды. Мысалы, интеграл алу немесе матрицаны транспонирлеуді қарапайым қадам деп қарастыруға бола ма?
Ақырында, есеп бірнеше алгоритм құруға мүмкіндік берген жағдайда теориялық және практикалық тұрғыдан алғанда оларды салыстыру және ең тиімдісін таңдау туралы сұрақ туындайды, бұл сұрақты шешу мәселесі де алгоритмнің қатаң анықтамасынсыз мүмкін емес.
Кез келген алгоритм ұғымының нақты анықтамасын, яғни, алгоритмнің барлық ойға келетін түрлері жатқызылатын максималды жалпы анықтамасын құру қажеттілігі осылайша туындады.
ХХ ғасырдың 20-шы жылдарында алгоритмнің нақты анықтамасын құру мәселесі маңызды математикалық мәселелердің біріне айналды. Бұл анықтама бір жағынан алгоритмнің интуитивті түсінігінің маңызына сәйкес келуі қажет болса, екінші жағынан формальды түрде қатаң болуы қажет болды. Осындай түсінікті құрастыру әрекеттері ХХ ғасырдың 30-шы жылдарында алгоритмдер теориясының өз алдына жеке ғылым болып қалыптасуына әкелді. Бұл ғылым математикалық логикамен бірге математиканың негізгі құралдарын - дәлелдеу тәсілдерін, аксиоматикалық теорияны құру тәсілдерін, математикалық процедуралардың қасиеттерін және т.б. қарастырады.
40-шы, 50-ші жылдарда есептеу техникасы мен оның функционалдануы мен қолданылуына байланысты ғылымдардың қарқынды дамуы кезінде осы ғылымдардың негізінде алгоритмдер теориясы жататыны анықталды, себебі компьютер алгоритмдер түрінде көрсетілетін процедураларды ғана жүзеге асыра алады.
Кез келген программа алгоритмнің орындаушы - компьютер түсінетін тілде жазылуы. Осылайша практикалық тұрғыдан алғанда да алгоритм ұғымын жетілдіру маңызды болып табылады.
Алгоритм түсінігін жетілдіру алгоритмдік модельдер аясында жүргізіледі. Модель есепті шешу кезінде қолдануға болатын құралдар жиынтығын көрсетеді, яғни, элементар қадамдар тізімін, келесі қадамды анықтау тәсілін, т.б.
Алгоритмдік модельдер теориялық және практикалық болуы мүмкін. Теориялық тұрғыдан алғанда модельдердің бір жағынан әмбебап болғаны, яғни, кез-келген алгоритмді сипаттауға мүмкіндік бергені, екінші жағынан неғұрлым қарапайым болғаны, яғни, есепті шешудің неғұрлым аз құралын пайдаланғаны ерекше қызығушылық тудырады. Қарапайымдылық талабы алгоритмнің нақты қажет элементтері мен қасиеттерін ерекшелеп, осы қасиеттер туралы жалпы тұжырымдарды дәлелдеуді қамтамасыз ету үшін маңызды. Практикалық және қолданбалы модельдерде программалаудың қолайлылығы мен есептеу тиімділігі маңыздырақ, сондықтан олардың құралдары (қарапайым қадамдар жиынтығы, т.б.) әлдеқайда көп және күрделірек, бұл теориялық анализді қиындатады.
Алгоритмнің қатаң анықтамасын құрудың теориялық қырларында тарихи жағынан негізгі үш бағыт бөлініп шықты.
Бірінші бағыт аргументтердің бүтін санды мәндеріне тәуелді сандық функциялардың мәндерін есептеуге мүмкіндік беретін алгоритмдерді қарастырумен байланысты - мұндай функциялар есептелінетін функциялар атауына ие болды. Есептелінетін функциялар ұғымы алгоритмдер ұғымы сияқты қатаң ұғым емес. Бірақ А.Черчтің, К.Гедельдің, С.Клинидің еңбектерінің арқасында барлық жерде анықталған есептелінетін функциялар класының қатаң анықталатын бөлікті рекурсиялы функциялар класымен ұқсастығы негізделді. Бұл алгоритмдік шешілу мәселесін есепті шешетін рекурсиялы функцияны құру мүмкіндігін (немесе мүмкін еместігін) дәлелдеуге келтіруге мүмкіндік берді. Дәл осы жолмен А.Черчке математикалық логиканың мәселелерінің бірі - предикаттардың ақиқаттығын есептеу мәселесінің шешілмейтіндігін дәлелдеудің сәті түсті.
Екінші бағыт машиналық математикамен байланысты.
Алгоритм орындаушысы - алгоритмде көрсетілген әрекеттер тізімін орындауға қабілетті субъект немесе құрылғы. Әрбір орындаушыға әрекеттерді орындауға нұсқау - арнайы тілдер арқылы беріледі. Мұнда әрекеттерді көрсететін қызметші сөздер, сол сияқты оларды біріктіретін синтаксикалық ережелер, командалар жиынтығы орындаушының командалар жиынтығын құрайды.
Дискретті информацияны өңдеудегі қарапайым бір белгіні екіншісімен ауыстыру болып табылады. Бірақ қарапайым әрекеттер тізімін орындайтын абстрактілі және шынайы құрылғы жасауға болады. Орындаушыға арналған мұндай алгоритм құру барысында интегралданған командалар тізбегін көрсету жеткілікті, ал оларды шын қарапайым командалар тізбегіне түрлендіруді орындаушы өзі атқарады. Мұндай алгоритмдеудің көпсатылылығы компьютерді басқару барысында көп қолданылады.
Шын қарапайым әрекет деп процессордың әрекеттерін айтуға болады. Қазіргі процессорларда олар бірнеше жүз немесе мыңға барады.
Оларды машиналық команда, ал белгіленуін машиналық кодтар деп атайды. Машиналық кодтардан бөлінген бірінші (төменгі) деңгейдегі ассемблер коды есептелінеді, яғни ішкі (аппараттық - тәуелді) тіл. Қарапайым әрекеттерді күрделі командаларға біріктіру бұл деңгейде әлі жүргізілмейді және ассемблердің жалпы командалар саны процессордың командалар санымен бірдей болады.
Бірақ машиналық пен процессор регистрлері-мнемоникаларда символдық бейнелеу формалары қолданылады. Бұл пайдаланушыға екілік машиналық кодтан қарағанда қолайлы.
Мнемониктерді машиналық командаларға аударуды - ассемблер программасы жүзеге асырады. Программист орындаушы ретінде осы тілмен жұмыс істейді. Қарапайым әрекеттерді біріктіретін командалар жоғары деңгейдегі программалау тілдерінде көрінеді. Мысалы, Write сөзін программа текстінде жазу жеткілікті. Ал транслятор оларды қарапайым қадамдарға айналдырады. Программистке қарағанда бұл жағдайда орындаушы программалау тілінің трансляторы есептеледі. Бұдан жоғары қарапайым интеграциялау деңгейлерін қолданбалы программалардан көреміз. Бұл жерде ақырғы пайдаланушыға қарағанда қолданбалы программа орындаушы болып тұр. Мұндау орындаушының командалар жүйесіне барлық басқару командалары кіреді, яғни меню, экрандық батырмалар және т.б. интерфейс элементтері.
Бір команданы орындау күрделі әрекеттердің тізімін орындауға әкеледі, мысалы текстің көп жолдарын туралау.
Осылайша алгоритмді жазу барысында алгоритмді көрсету тілі формальды болуы мүмкін, ал онда орындаушының өзімен шынайы қарапайым әрекеттерге аударылатын күрделі командалар қолданылады.
Сұрыптау есептері іздеу есептері секілді негізгі болып табылады. Практикада бұл есептер өзара байланысты. Сұрыптауға байланысты есептерді шешуге көптеген іргелі ғылыми зерттеулер, көптеген алгоритмдер жасалды.
Жалпы жағдайда сұрыптауды белгілі бір ретпен берілген объектілер жиынтығын қайта құру процесі деп түсіну керек. Көбінесе деректердің үлкен көлемін сұрыптау кезінде элементтердің өздерін қайта құру мүмкін емес, сондықтан мәселені шешу үшін элементтерді индекстер бойынша ретке келтіру жүзеге асырылады. Яғни, элементтердің индекстері оларға сәйкес келетін элементтердің мәндері мәселенің шарты бойынша сұрыпталатын ретпен құрылады.
Сұрыптау реттелген жиынтықтағы элементтерді табуды жеңілдету үшін қолданылады. Сұрыптау міндеті-бағдарламалаудағы негіздердің бірі.
Сұрыптау дегеніміз-бір типтегі мәліметтер жиынтығын өсу немесе кему бойынша реттеу.
Іздеу алгоритмінен басталық.
1.2 Іздеу және тандау алгоритмдері
Іздеу екіге бөлінеді: тізбектеліп іздеу, бинарлық іздеу.
1. Тізбектеліп іздеу
Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады.
Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп іздеу кез келген тізбек үшін қолайлы, тізбектеліп іздеудің орталық тиімділігі O(n) тең болады.
2. Бинарлық іздеу
Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады.
Бинарлық іздеудің алгоритмі:
1. Массивтің ортаңғы элементінің индексін табу: mid=(low+high)2.
2. Орталық элементтің мәнін кілтпен салыстыру Key. Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз.
3. Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз.
Мысалы: Бүтін сандардан тұратын А массиві берілсін. 33 кілті берілген элементі бар табу керек.
А элементтері:
0
1
2
3
4
5
6
7
8
-7
3
5
8
12
16
23
33
55
Low=0 High=8 mid=4
33A(mid)
0 1 2 3 4 5 6 7 8
-7
3
5
8
12
16
23
33
55
mid
Low=5
High=8
mid=6
33A(mid)
0 1 2 3 4 5 6 7 8
-7
3
5
8
12
16
23
33
55
mid
Low=7
High=8
mid=7
33=A(mid)
Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық іздеуде 3 салыстыру жүргізіледі.
Сұрыптау деректерді өңдеудің ең көп қолданылатын процедураларының бірі болғандықтан, сұрыптау алгоритмдерінің тиімділігіне өте жоғары талаптар қойылады.
Алгоритмдердің жұмысын теориялық тұрғыдан алынған бағалау арқылы да, эмпирикалық түрде де алгоритмдерді эксперименттік салыстыру арқылы бағалауға болады.
Теориялық өнімділік бағалары көбінесе сұрыпталған кесте жазбаларының санына байланысты сұрыптау уақытының өсу жылдамдығын бағалау түрінде көрінеді. Олар, мысалы: "бұл алгоритмде o(N2) рейтингі бар"дейді. Бұл N жазбаларының саны көбейген кезде, мысалы, 10 есе, алгоритмнің жұмыс уақыты шамамен 102 = 100 есе артады дегенді білдіреді. Бұл жағдайда максималды уақытты бағалауды (яғни, осы алгоритм үшін ең сәтсіз болған жағдайда) және орташа уақытты (яғни кездейсоқ кесте үшін сұрыптау уақытының математикалық күтуі) ажырату керек.
Үлкен мәндердегі алгоритмдердің мінез-құлқын салыстыру үшін "О-үлкенге дейінгі дәлдікпен" бағалаудың мағынасы бар, іс жүзінде үлкен N үшін O(N⋅log(N)) немесе осы мәнге жақын алгоритмдер қолайлы деп саналады, ал O(N2) бағалаумен сұрыптау алгоритмдері қолайсыз болып саналады.
Сонымен қатар, кестенің кішігірім өлшемдерінде, бірнеше ондаған жазбаны айталық, O(N2) бағалауы бар қарапайым алгоритмдер жақсы бағаланған күрделі алгоритмдерге қарағанда тезірек жұмыс істей алады.
Алгоритмдерді эксперименттік бағалау нақты нәтиже береді, бірақ бағаланатын бағдарламаның жұмыс уақыты алгоритмнің сапасына қосымша көптеген факторларға, атап айтқанда, компьютерлердің жұмысына және нақты сұрыпталған мәліметтерге байланысты, олар бірдей мөлшерде сыналған алгоритм үшін сәтсіздеу болуы мүмкін.
Эксперименттік бағалаудың компьютердің жұмысына тәуелділігін азайту үшін жұмыс уақытынан басқа, осы алгоритмге тән орындалған операциялардың санын жазып алған жөн. Сұрыптау үшін мұндай операциялар кесте элементтерінің кілттерін салыстыру және жазбаларды қайта құру (тағайындау) болып табылады. Сонымен қатар, зерттелген алгоритмді белгілі алгоритмдердің кез-келгенімен бірдей бастапқы деректермен салыстыру пайдалы.
Алгоритмді бағалауға нақты деректердің әсерін жою үшін кездейсоқ бастапқы деректермен сынақтарды бірнеше рет қайталау керек, алайда мұндай эксперименттер көп уақытты қажет етеді, сонымен қатар математикалық статистика әдістерін қолдана отырып нәтижелерді сауатты бағалау қажет.
Кестелерді сұрыптау кезінде жазу кілті (яғни жазбаларды салыстыру үшін қолданылатын жазбаның бөлігі) және кілттен басқа қосымша мәліметтер болуы мүмкін жазбаның өзі ерекшеленеді.
Сұрыптау алгоритмдері негізінен кілттерді салыстырудан және жазбаларды ауыстырудан тұрады және бір-бірінен салыстырылатын және ретке келтірілетін ретпен ерекшеленеді.
Массивтерді сұрыптау мәселесінде массив элементтерінің өздері кілттер болып табылады және олар қайта құрылады. Бұл айырмашылықтың маңыздылығы массивтер үшін сұрыптау алгоритмдерін зерттеуге мүмкіндік береді, Қажет болған жағдайда осы алгоритмдерді жалпы кестелер үшін оңай өзгертуге болады.
Енді ең танымал ішкі сұрыптау алгоритмдеріне қысқаша шолу жасалық.
Массивтерді сұрыптаудың қарапайым алгоритмдері
Қарапайым алгоритмдер, өкінішке орай, жоғары тиімділікпен ерекшеленбейтін келесі үш айқын және қарапайым алгоритмді қамтиды:
* Көпіршік алгоритмі (BubbleSort)
* Қарапайым таңдау алгоритмі (SelectionSort)
* Қарапайым кірістіру алгоритмі (InsertionSort)
1.3 Көпіршік алгоритмі (BubbleSort)
Көпіршік сұрыптау (көпіршік әдісімен сүрыптау) (Пузырьковая сортировка (сортировка методом пузырька); bublle sorting) -- реттелетін жиымның көрші элементтерін тізбектік орын ауыстырудан тұратын сұрыптау тәсілі.
Бұл әдіс тиімділік жағынан ең соңғы орынға ие болған, ең қарапайым ішкі әдістердің классына жатады. Бірақ, оған қарамастан, бұл әдіс кең танымал, өте тез еске сақталатын атының арқасында - судың бетіне шығатын көпіршік әдісі немесе батып бара жатқан доп әдісі.
Алгоритмнің идеясы келесідей:
Массивтің 1-ші және 2-ші индексті элементтерін салыстырамыз. Егер бірінші екіншіден артық болса, онда бұл элементтерді орындарымен ауыстырамыз. Одан соң 2 және 3-ші элементтерді, содан кейін 3 және 4-индексті элементтерді салыстырамыз (және қажет болса, өзгертеміз) т.с.с. Элементтерді салыстырғаннан кейін (N-1) және N алгоритмнің бірінші өтуі аяқталады. Осы өтуден кейін массивтің максималды элементі соңғы орында екендігіне кепілдік беруге болады (яғни, N индексі бар). Екінші жолда біз 1-ші және 2-ші, 2-ші және 3-ші жұптарын салыстырамыз ... (N-2) және (N-1). Әрі қарай осы іспеттес. N-1 өткеннен кейін барлық элементтер өздерінің заңды орындарын алады.
Келесі кезеңде қандай да бір орын ауыстыру жасалғанын арнайы белгімен белгілеп, өту санын азайтуға тырысуға болады. Егер бүкіл өту кезінде бірде-бір өзгеріс болмаса, онда массив қазірдің өзінде сұрыпталған және алгоритмнің жұмысын мерзімінен бұрын аяқтауға болады. Алайда, мұндай жағдай сирек айтарлықтай пайда әкеледі. Кездейсоқ толтырылған массив үшін 75% ықтималдылықпен алгоритмнің барлық өтуі әлі де орындалатынын көрсету қиын емес.
Мысалы. 6 элемент берілген болсын - 15, 33, 42, 07, 12, 19- бүтін сандар. Осы сандарды сұрыпталық (1-кесте).
Нәтижесінде, алты элемент үшін 5+4+3+2+1 = 15 салыстыру және 8 орын ауыстырулар өткізілді.
Көпіршікті алгоритмнің "шейкер сұрыптау"деп аталатын тағы бір модификациясы бар.
Бұл тақ жолдарда көпіршіктің солдан оңға қарай өтетіндігімен ерекшеленеді (циклдегі индекс артады), ал жұп жолдарда - оңнан солға (индекс азаяды). Осылайша, алғашқы екі өтуден кейін массивтің максималды және минималды элементтері өз орындарында болады.
Кесте 1. Сұрыптау амалдары
қадам
а1
а2
а3
а4
а5
а6
Амалдар
қадам1
15
33
42
07
12
19
салыстыру 19 және 12, ауыстыру жоқ
15
33
42
07
12
19
салыстыру 12 және 07, ауыстыру жоқ
15
33
07
42
12
19
салыстыру 07 және 42, орындарын ауыстырамыз
15
07
33
42
12
19
салыстыру 07 және 33, орындарын ауыстырамыз
07
15
33
42
12
19
салыстыру 07 және 15, орындарын ауыстырамыз; 07 - минималды
қадам 2
07
15
33
42
12
19
салыстыру 19 және 12, ауыстыру жоқ
07
15
33
12
42
19
салыстыру 12 және 42, орындарын ауыстырамыз
07
15
12
33
42
19
салыстыру 12 және 33, орындарын ауыстырамыз
07
12
15
33
42
19
салыстыру 12 және 15, орындарын ауыстырамыз, 12 - екінші минималды.
қадам3
07
12
15
33
19
42
салыстыру 19 және 42, орындарын ауыстырамыз
07
12
15
19
33
42
салыстыру 19 және 33, орындарын ауыстырамыз
07
12
15
19
33
42
салыстыру 19 және 15, ауыстыру жоқ, 15 - үшінші минималды.
қадам4
07
12
15
19
33
42
салыстыру 42 және 33, ауыстыру жоқ
07
12
15
19
33
42
салыстыру 33 және 19, ауыстыру жоқ, 19 - төртінші элемент.
қадам 5
07
12
15
19
33
42
салыстыру 42 және 33, ауыстыру жоқ, сұрыптау аяқталды
07
12
15
19
33
42
Бұл алгоритмнің негізгі мағынасы алмастыру бойынша сұрыптауға жатады. Айрымашылығы, алмастыру бойынша сұрыптау тек бір бағыт бойынша жүргізілетіндігін байқадық, ал бұл жағдайда бағыт әрбір рет өзгеріп тұрады. Бұл сұрыптауда ауыстырулар туралы және соңғы алмастыру жасалған орынды есте сақтап отырады. Базалық алгоритмде екілік сүзгі саны N div 2 - ге тең.
Біріншіден, егер массив бөлігінде қозғалыстарда орын ауыстырулар болмаса онда массивтің бұл бөлігі сұрыпталған болып есептеледі, сондықтан, оны қарастырудан алып тастауға болады.
Екіншіден, массивтің соңынан басына дейін өткенде минималды элемент бірінші позицияға тұрады, ал максималды элемент тек бір позицияға оң жаққа қарай қозғалады.
Массивтің жұмыс бөлігінің шектері әр итерацияның орын ауыстыруында орнықтырылады. Массив рет бойынша оң жақтан сол жаққа және сол жақтан оң жаққа кезек кезек қарастырылады.
Бұл сұрыптаудың үздік жағдайы -- сұрыпталған массив (О(n)), ең жаманы -- кері бағытта сұрыпталған массив (O(n²)).
Салыстырулар санының ең кіші мәні Шейкер-сұрыптауында C=N-1. Бұл сұрыпталған массивте тек бір өтуге сәйкес.
1.4 Қарапайым таңдау алгоритмі (SelectionSort)
Бұл алгоритмнің идеясы одан да қарапайым:
Массивтің минималды элементін табамыз және оны бірінші элементпен ауыстырамыз. Содан кейін сол процедураны қайталаймыз, массивтің екінші элементінен бастап, содан кейін үшіншіден бастап және т.б. N-1 өтуден кейін барлық элементтер орнында болады.
1.5 Қарапайым кірістіру алгоритмі (InsertionSort)
Идея келесідей:
Алгоритмнің белгілі бір сәтінде массивтің алғашқы k элементтері сұрыпталсын, яғни, өсу бойынша орналастырылған.
Келесі кезеңде біз (k+1) элементтерін сұрыптауға тырысамыз. Ол үшін R жұмыс айнымалысындағы элементтің мәнін (k+1) есте сақтаймыз және R-ны K, (k-1), (k-2) және т.б. элементтердің мәндерімен салыстырамыз.
Салыстыру R элементі орналастырылатын орын табылғанша жалғасады (бұл келесі салыстырылатын элемент R-ден кіші немесе оған тең болған кезде немесе массивтің басына жеткенде болады).
Осылайша, келесі кезеңде массивтің сұрыпталған бөлігі 1 элементке артады. K = 1 мәнінен бастап, N-1 өту үшін бүкіл массивті сұрыптауға болады.
Қарапайым кірістіру алгоритмін k+1 элементін кірістіру үшін орынды k-дан 1-ге дейінгі элементтерді дәйекті қарау арқылы емес, бинарлы іздеу арқылы жақсартуға болады (яғни R-ді J: = (k+1) div 2 элементімен салыстырыңыз, содан кейін аралықтардың бірінде іздеуді жалғастырыңыз [1..j-1] немесе [j + 1..k] және т.б.).
Бинарлы кірістіру алгоритмі деп аталатын бұл тәсіл салыстыру санын едәуір азайтады, бірақ, өкінішке орай, орын ауыстыру санына әсер етпейді.
Қарапайым алгоритмдерді салыстыру
Жоғарыда аталған үш алгоритмнің барлығы және олардың барлық модификациялары максималды және орташа бағалау O (N2), сондықтан үлкен массивтер немесе сұрыптау уақытына қатаң талаптар болмаған жағдайда ғана қолданылады.
Тәжірибелер көрсеткендей, көпіршікті алгоритм әдетте үшеуінің ішіндегі ең баяу, ал таңдау және кірістіру алгоритмдері шамамен бірдей сұрыптау уақытын береді.
Кейбір жағдайларда бастапқы массив "сұрыпталған дерлік" болады деп күтуге болады, яғни элементтердің аз ғана бөлігі тәртіпті бұзады.
Бұл, мысалы, егер массив бұрын сұрыпталған болса, бірақ содан кейін ондағы мәліметтер аздап өзгертілген. Бұл жағдайда сұрыпталған дерлік массивтерде өте жоғары жылдамдықты көрсететін алгоритмдері бәсекелестіктен тыс қалады.
Кірістіру алгоритмдерінің бұл ерекшелігі төменде сипатталған Шелл алгоритмінде қолданылады.
1.6 Массивтерді сұрыптаудың жетілдірілген алгоритмдері
Алгоритмдердің күрделенуі үлкен массивтерді сұрыптаудың тиімділігін едәуір арттырады. Біз осы кластың ең танымал алгоритмдерін атап өтелік.
1.6.1 Шелл алгоритмі
Бұл әдіс Дональд Л. Шелл ұсынған, орналасқан жері бойынша тұрақсыз сұрыптау болып табылады. Шелл әдісі қосулар әдісінің жақсартылған нұсқасы.
Сұрыпталған массивтің элементтерін h тізбектеріне бөлеміз, олардың әрқайсысы бір бірінен h қашықтықта орналасқан элементтерден тұрады (мұнда h-ерікті натурал сан).
Бірінші тізбекте 1, h+1, 2h+1, 3h+1 және т.б. индекстері бар элементтер болады, екіншісі - 2, h+2, 2h+2 және т. б., соңғы тізбек - h, 2h, 3h және т. б.
Бұл үшін қарапайым кірістіру әдісін қолдана отырып, әр тізбекті бөлек массив ретінде сұрыптаймыз.
Содан кейін біз жоғарыда айтылғандардың барлығын h - тың бірқатар мәндері үшін орындаймыз, ал соңғы рет - h=1 үшін.
Осыдан кейін массив сұрыпталатыны анық.
h1-дегі барлық жолдар уақытты ысырап етпегені анық емес. Алайда, үлкен h-тағы элементтердің алыс қашықтықтары массивті сұрыпталған күйге жақындатқаны соншалық, соңғы өту кезінде өте аз жұмыс қалады.
Тәжірибелер көрсеткендей, үлкен мәндер үшін алгоритмнің орташа жұмыс уақытын бағалау шамамен O(N 1.26). Бұл қарапайым алгоритмдер үшін O(N2)-ге қарағанда әлдеқайда жақсы.
Шелл алгоритмінің тиімділігі үшін h мәндерінің кему тізбегін сәтті таңдау үлкен мәнге ие. Көршілес k мәндерімен hk мәндері бір-біріне еселік болмағаны жөн.
Әдебиеттерде, әдетте, екі тізбектің біреуін қолдану ұсынылады:
h k+1 = 3hk + 1 немесе hk+1 = 2hk+1.
Екі жағдайда да бастапқы hk ретінде барлық сұрыпталған тізбектердің ұзындығы кемінде 2 болатын тізбектен осындай мән таңдалады.
Пайдалану үшін, мысалы, осы формулалардың біріншісін алдымен h1:=1 қою керек, содан кейін келесі hk үшін hk =(N - 1) div 3 теңсіздігі орындалғанға дейін hk+1: = 3*hk+1 формуласы бойынша циклде h мәнін арттыру керек.
Бұл hk мәні алгоритмнің бірінші жолында қолданылуы керек, содан кейін кері формула бойынша келесі мәндерді алуға болады:
h k-1 := (hk-1) div 3, h1=1 дейін.
Неғұрлым күрделі формулалар Седжвик тізбегін анықтайды:
hk=9∙2k-9∙2k2+1, егер k-тақ болса8∙2k-6∙2k+12+1, егер k-жұп болса
hk - ны Седжвик бойынша таңдау кезінде алгоритмнің орташа жұмыс уақыты O(N76), ал максимум O(N43) болатындығы дәлелденген.
Практикада Седжвик тізбегінің жеткілікті мүшелерін тек бір рет есептеу ыңғайлы
(олар: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929,16001, 36289, 64769, 146305, 260609, 587521, 1045505, ...),
содан кейін берілген N бойынша k таңдаймыз, онда hk = (N - 1) div 3, содан кейін циклде k кемуі бойынша hk тізбегінің мәндерін таңдаймыз.
1.6.2 Жылдам сұрыптау алгоритмі (QuickSort)
Бұл әдісті 1962 жылы Оксфорд университетінің профессоры К.Хоар жасап шығарған.
Бұл алгоритм массивті бөлу операциясына негізделген.
Айталық, x-сұрыпталатын массивтің кездейсоқ таңдалған элементі болсын (элементті бөлу).
Бөлу операциясы массив элементтерін алдымен x-тен кіші немесе оған тең (міндетті түрде өсу ретімен емес), содан кейін x-тен үлкен немесе оған тең болатын элементтер болатындай етіп өзгертуге бағытталған.
Бөлуді орындау үшін массив элементтерін солдан оңға қарай қарап, x-тен үлкен немесе оған тең элементтердің біріншісіне тоқталайық. сол элементтің индексі i болсын. Біз i және j элементтерін ауыстырамыз, содан кейін i-ден оңға және j-ден солға қарай жүре береміз, орнында тұрмаған элементтердің жұптарын ауыстырамыз.
Бөлу ij болған кезде аяқталады.
Жылдам сұрыптау алгоритмін келесідей түрде сипаттауға болады.
X массивінің кез келген элементін алып, оны бөлу әрекетін орындаймыз. Егер массивтің сол жәненемесе оң сегменттерінде бірден артық элемент болса, онда біз осы кесіндінің әрқайсысы үшін массивке орындалған барлық әрекетті орындаймыз (яғни, еркін элементті таңдаймыз, бөлуді орындаймыз және т.б.).
Жоғарыда келтірілген бірнеше мәрте бөлу операциясын орындауды ұйымдастырудан көрі рекурсивті айқындау рәсімі көмегімен сұрыптау оңайырақ.
Алгоритмнің рекурсивті емес сипаттамасы қиынырақ, өйткені қажет болған жағдайда бөлінгеннен кейін пайда болған массивтің екі аралығын сұрыптау керек, екіншісі сұрыпталған кезде аралықтардың бірін (дәлірек айтқанда, оның индекстерінің екі шекаралық мәні) стекке нақты сақтау керек. Сонымен қатар, рекурсивті емес нұсқа әдетте тиімдірек болады және, ең бастысы, пайдаланылған стек тереңдігін азайтуға мүмкіндік береді.
Мұны істеу үшін біз әрқашан сұрыпталатын массивтің екі аралығынан ұзағырақ стекке әкелуісіз керек. Бұл жағдайда бір уақытта стекте орналасқан аралықтардың максималды саны log2(N) - нен аспауы керек.
Жылдам сұрыптау алгоритмінің тиімділігіне таңдау да әсер етеді.
Теориялық тұрғыдан алғанда, x еркін түрде таңдалуы мүмкін, бірақ егер бастапқы массив сұрыпталған немесе сұрыпталғанға жақын болса, бірінші немесе соңғы элементтің x ретінде таңдау өте нашар нәтижелерге әкелетінін көруге болады. Осыған байланысты x ретінде массивтің ортасынан элементті немесе кездейсоқ таңдалған индексі бар элементті таңдау әдеттегідей.
Кейде сәл күрделі ереже қолданылады: массивтің бірінші элементін, соңғы элементті, массивтің ортасынан элементті алып, осы үшеуінің орташа мәнін x ретінде таңдаңыз.
QuickSort алгоритмінде O(n⋅log(N)) орташа уақыт бағасы бар және іс жүзінде ол басқаларға қарағанда тезірек болады, алайда болмаған жағдайда ол O(N2) ретіне сәйкес уақытты қажет етуі мүмкін.
Кейбір жағдайларда QuickSort-ты көпіршікті алгоритммен біріктіру орынды болуы мүмкін. Шындығында, бөлу процедурасы массивтің бөлінген сегменттері қысқа болған кезде өте аз пайдалы жұмыс жасайды. Ұзындығы L-ден аспайтын сегменттерді бөлуге болмайды, содан кейін "көпіршіктің"L-1 өтуін орындау арқылы массивті сұрыптауға болады. Көптеген қысқа массивтер үшін "көпіршіктің" жеке өтуін ұйымдастырудың қажеті жоқ, сұрыпталған массивте "көпіршікті" өткізіп жіберу оңайырақ.
Тәжірибе көрсеткендей, L мәні 3 - 4-тен аспайды.
1.6.3 Пирамидалық сұрыптау алгоритмі (HeapSort)
Бұл алгоритм пирамида ұғымына негізделген.
Оны 1964 жылы америкалық ғалымдар Дж. У. Дж. Уильямс мен Р.У. Флойд ұсынған еді.
A1, A2, ... AN массиві пирамида деп аталады, егер:
2k = N болатын барлық k үшін Ak = A2k;
2k+1 = n болатын барлық k үшін Ak = A2k+1 болса.
Пирамиданы массив түрінде ұсынылған екілік ағаш ретінде қарастыруға болады, оның ата-аналық шыңмен байланысты мәні ұлдармен байланысты мәндерден кем емес. Сонымен қатар, A1-ағаштың тамыры, A2 және A3-оның ұлдары, A4, ... A7-немерелері және т. б.
Сұрыптау алгоритмі екі кезеңнен тұрады: пирамида салу және пирамиданы сұрыпталған массивке айналдыру. Әрбір фазаның негізінде пирамида арқылы элементтерді електен өткізу операциясы жатыр.
Електен өткізу операциясының мәні келесідей.
Жоғарыда келтірілген теңсіздіктер бұзылуы мүмкін элементтердің тек біреуі үшін "дұрыс" пирамида бар делік. Пирамиданың дұрыстығын қалпына келтіру үшін алдымен Ak ұлдарын, яғни A2k және A2k+1 элементтерін салыстыру керек. Осы элементтердің үлкен санын r әрпімен белгілеңіз. Енді сіз Ar-ді әкемен (ak элементімен) салыстыруыңыз керек, егер Ak = Ar теңсіздігі бұзылса, онда Ak және Ar-ді ауыстырыңыз.
Енді Ak үшін екі теңсіздік орындалады, бірақ Ar үшін ұқсас теңсіздіктер бұзылуы мүмкін. Сондықтан k:=r қою керек және келесі итерацияда Ak элементінің ұлдары жоқ немесе ол үшін қажетті теңсіздіктер орындалғанға дейін сол әрекеттерді циклдік түрде қайталау керек. Бұл жағдайда Ak элементін елеу процесі аяқталады.
Егер пирамиданы екілік ағаш ретінде елестетсек, онда ол ағаштың бір бұтағының бойымен Ак элементінің "құлауы" сияқты болады.
Пирамиданың құрылысы элемент арқылы басталады, оның индексі k:= N div 2 (бұл ағашта ұлдары бар элементтердің ең оң жағы). Бұл элементті елегеннен кейін, k индексінен бастап массивтің соңына дейінгі ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz
Реферат
Курстық жұмыс
Диплом
Материал
Диссертация
Практика
Презентация
Сабақ жоспары
Мақал-мәтелдер
1‑10 бет
11‑20 бет
21‑30 бет
31‑60 бет
61+ бет
Негізгі
Бет саны
Қосымша
Іздеу
Ештеңе табылмады :(
Соңғы қаралған жұмыстар
Қаралған жұмыстар табылмады
Тапсырыс
Антиплагиат
Қаралған жұмыстар
kz