Массивтерді сұрыптаудың қарапайым алгоритмдері


- Алгоритм түсінігі
- Іздеу және тандау алгоритмдері
- Көпіршік алгоритмі
1. 4 Қарапайым таңдау алгоритмі
1. 5 Қарапайым кірістіру алгоритмі
1. 6 Массивтерді сұрыптаудың жетілдірілген алгоритмдері
1. 6. 1 Шелл алгоритмі
1. 6. 2 Жылдам сұрыптау алгоритмі
1. 6. 3 Пирамидалық сұрыптау алгоритмі
1. 6. 4 Біріктіру алгоритмдері
- Массив түсінігі
- Массивтерді сұрыптау
2. 2. 1Таңдау арқылы сұрыптау
2. 2. 2Ауыстыру арқылы сұрыптау
2. 2. 3 Шейкерлік сұрыптау
2. 2. 4 Тікелей қосу сұрыптауы
2. 2. 5 Пирамидалық сұрыптау
2. 3 Оқушылардың массивті сұрыптауға өз бетінше орындауына арналған тапсырмалар
КІРІСПЕ
Қазіргі таңда заманымыздың цифрланған дәуірге қадам басқан кезеңінде көптеген мамандардың функционалдық міндеттерін сәтті орындауы көбінесе дербес компьютерлерді, байланыс құралдарын, қолданбалы бағдарламалардың кәсіби пакеттерін және әртүрлі зияткерлік ақпараттық технологияларды шебер қолдануымен анықталады.
Қоғамды ақпараттандыру процестері информатика және басқару процестерін компьютерлендіру саласындағы білімді қалыптастыруды қажет етеді.
Қазіргі уақытта жаңа ақпараттық технологиялар мамандандырылған ғана емес, сонымен қатар күнделікті өмірде де маңызды орын алады. Компьютерлер бизнесте, басқаруда, саудада, оқуда және адам қызметінің көптеген басқа салаларында қолданылады.
Компьютерлік технологиялар әртүрлі операцияларды орындау үшін өте ыңғайлы, бірақ әр түрлі қолдану салаларында бұл операциялар әртүрлі. Сондықтан нақты техникалық құралдарды қолданатын әрбір жеке сала компьютерлердің жұмысын қамтамасыз ететін өз бағдарламаларын қажет етеді.
Бағдарламалық жасақтаманы бағдарламалау сияқты ғылым саласы жасайды. Бұл соңғы уақытта барған сайын маңызды бола түсуде, өйткені күн сайын компьютер біздің өміріміздің қалыпты құбылысына айналуда.
Осылайша, жаңа ақпараттық технологиялар біздің заманымызда өте өзекті және кейінгі даму мен жетілдіруге көп көңіл бөлуді қажет етеді. Сонымен қатар, бағдарламалаудың да маңызы зор, ол информатиканың іргелі бөлімдерінің бірі болып табылады, сондықтан қазіргі таңда оған өте қатты көңіл бөлінуде.
Бағдарламалау бірқатар маңызды ішкі міндеттерді қамтиды.
Бағдарламалауда үлкен көлемдегі мәліметтерді өңдеумен байланысты тапсырмалар жиі кездеседі. Мәліметтердің бүкіл көлемін бағдарлама ішінде сақтау үшін массивтер қолданылады - құрылымдалған деректер түрлерінің қарапайым түрі.
Массив - бірдей элементтерді сақтайтын жад аймақтарының белгілі тізбегі. Әрбір осындай жад аймағы массив элементі деп аталады. Массивтерде олардың құрамындағы элементтердің саны, сондай ақ бағдарламада бір және көп өлшемді массивтерді сипаттау мүмкіндігін білдіретін өлшем бар. Массивтегі элементтер саны оның мөлшері деп аталады.
Бағдарламалаудың маңызды міндеттерінің бірі - сұрыптау мәселесі.
Сұрыптау есептері іздеу есептері сияқты базалық болып табылады. Практикалық жағдайда бұл міндеттер өзара байланысты. Сұрыптауға байланысты мәселелерді шешуге көптеген іргелі ғылыми зерттеулер, көптеген алгоритмдер жасалды.
Жалпы жағдайда сұрыптауды белгілі бір ретпен берілген объектілер жиынтығын қайта құру процесі деп түсіну керек. Көбінесе мәліметтердің ауқымды көлемін сұрыптау кезінде элементтердің өздерін қайта құру мүмкін емес, сондықтан мәселені шешу үшін элементтерді индекстер бойынша ретке келтіру жүзеге асырылады. Яғни, элементтердің индекстері оларға сәйкес келетін элементтердің мәндері мәселенің шарты бойынша сұрыпталатын ретпен құрылады.
Маманды қалыптастыру мектеп қабырғасынан басталады. Ендеше, орта білім беру мектептерінде 7-9 сыныптарда массивтер, оларды жариялау және өңдеу туралы жалпы түсінік ала отырып, баланың бағдарламалау туралы алғашқы идеялары туындап, қызығушылығы артатыны мүмкін екенін атап өтуге болады. Сонда оқытудың келесі кезеңінде мамандандырылған сыныптарда мұғалім мен оқушы бағдарламалық жасақтаманы жасау үшін мейлінше жан жақты қолданылатын, заманауи бағдарламалау тілін алады.
Осылайша, мұғалім массивтерді сұрыптауға, элементтерді іздеуге байланысты көптеген мәселелерді шешуге жақындай алады, бұл оқытудың мамандандырылған кезеңінде оқушыға қысқа мерзімде әр түрлі мәселелерді шешуге мүмкіндік береді.
Бұл жұмыста теориялық бөлімде тек мектеп информатикасы ғана емес жалпы информатикада қолданылатын сұрыптау алгоритмдері толық қамтылды.
Жұмыстың теориялық бөлігін орындау кезінде әр алгоритмнің қасиеттерін егжей-тегжейлі ашатын келесі сұрақтарға жауап беріледі, атап айтқанда:
- қандай салыстыру элементтер жұбының реттілігін анықтайды?
- қандай орын ауыстыру бірнеше элементті өзгертеді?
- жиынтықтың барлық элементтері реттелгенге дейін элементтерді салыстыру мен қайта құруды жүзеге асыратын сұрыптау алгоритмі қандай?
Қарастырылған сұрыптау алгоритмдерінің бәріне қасиеттер ортақ деп айтуға болады. Олар көптеген алгоритмдерден таңдалады, өйткені біріншіден, олар жиі қолданылады, екіншіден, басқа алгоритмдердің көпшілігі осы алгоритмдердің әртүрлі сипатталған түрлері деп айтуға болады.
Практикалық бөлімде бағдарламалау тілін қолдана отырып, есептер шешуге бағдарлама құру арқылы бар білімімізді бекітеміз.
Сондай-ақ, бұл жұмыста деректерді практикалық тұрғыдан реттеу мәселесі, яғни сұрыптау әдістерінің артықшылықтары мен кемшіліктері айтылған.
Дипломдық жұмысты орындау кезінде ABC Pascal бағдарлама ортасын қолданылды. Және жұмыстың мәтіндік бөлігін орындауға Microsoft Word қосымшасын пайдаланылды.
Microsoft Word-бұл әртүрлі құжаттар мен деректерді құруға, өңдеуге, экранға шығаруға және басып шығаруға, сонымен қатар файл түрінде сақтауға арналған мәтіндік редактор. Ол аталған операциялармен қатар мәтінді форматтауға (құжаттың бүкіл және оның бір бөлігі бойынша), құжаттарды ресімдеудің әртүрлі стильдерін қалыптастыруға, қаріптердің көп санын пайдалануға, мәтін фрагменттерін бөлуге (курсивпен, астын сызумен, қалың қаріппен және басқа да құралдармен), мәтінді бағандар түрінде теруге, иллюстрацияларды мәтіндерге қосуға, әр түрлі көрсеткіштер мен сілтемелерді қалыптастыруға, беттердің жоғарғы және төменгі колонтитулдарын енгізуге, мәтін элементтерін автоматтандырылған іздестіруді жүргізуге және қателерді, мәтіннің кез-келген бөлігін басқа орынға көшіруге және орын ауыстыруға қабілетті.
Дипломдық жұмыс теориялық және практикалық бөлімнен тұрады. Теориялық бөлімде сұрыптау алгоритмдері жайлы толық ақпарат беріліп, практикалық бөлімде нақты есептерге қолданыстары келтіріліп, бағдарламалау тілінде бағдарламалары, олардың электронды есептегіш машинада орындалу нәтижесі, сандық массивтер үшін тестілеуден өткені толығымен көрсетілген. Соңында өз бетінше орындауға арнайы тапсырмалар келтірілген.
І СҰРЫПТАУ АЛГОРИТМДЕРІ
Сұрыптау (ағылш. sorting-жіктеу, ретке келтіру) - таңдалған өлшемге байланысты бір нәрсенің бірізді орналасуы немесе топтарға бөлінуі, «анықталған рет» бойынша элементтерді орналастыру процессі.
Сұрыптаудың мақсаты - сұрыпталған жиында элементтерді іздестіруді жеңілдету.
Сұрыптау әдістерінің классификациясын қарастыратын болсақ, ол сызықты құрылымдардағы сұрыптау және сызықты емес құрылымдардағы сұрыптау болып екіге бөлінеді.
Сызықтық іздеу - қажетті элементті массив элементтерін қарапайым бірінен кейін бірін эталонмен салыстыра отырып іздейтін процедура. Ол қою, таңдау және айырбастау болып бөлінеді.
Сызықты емес құрылымдардағы сұрыптау турнирлі және пирамидалы болып екі топқа ажыратылады.
Қою - қарапайым және бинарлық (екілік) қоюға, таңдау - қарапайым таңдау болып, айырбастау - стандартты, Шелл әдісі және Хоар әдістерінен құралады.
Сұрыптау әдістері
Сызықты құрылымдардағы сұрыптау
Сызықты емес құрылымдардағы сұрыптау
Қою
Таңдау
Айырбастау
Турнирлі
Пирамидалы
Қарапайым Стандартты
Қарапайым Шелл-әдісі
Бинарлы Хоар -әдісі
1-сурет. Сұрыптау алгоритмдері
Сұрыптау - бұл белгілі бір тәртіп қатынасына сәйкес: алфавит бойынша, өрістің сандық мәнінің өсуіне не кемуіне және т. б. кестенің жазбаларын немесе нақты жағдайда -массив элементтерін ретке келтіру.
Сұрыптау, біріншіден, массив элементтерін қажетті ретпен қарауға, өңдеуге мүмкіндік береді, екіншіден, массив элементтерін жылдам (екілік) іздеуге мүмкіндік береді.
Ол үшін жоғарыда байқағанымыздай, алгоритм қолданамыз. Ендеше алгоритм түсінігінен басталық.
- Алгоритм түсінігі
Тарихи жағынан «алгоритм» термині ІХ ғасырда өмір сүрген шығыс математигі Мухаммед ибн Муса әл-Хорезми тегінен шыққан. Алғашында ол «алгорифм» деп аталды. Келе келе өзгеріске ұшырады -алгоритм.
Ол алғаш негізгі төрт арифметикалық амалдың ережесін құрастырған. Басында осы ережелер алгоритмдер деп аталып, кейіннен термин ары қарай дамуын ең алдымен математикада жалғастырды - алгоритм деп қандай-да бір бастапқы мәліметтер класына бірдей орындалатын есептеулер тәсілі атала бастады, мысалы, функцияның туындысын табу.
Математикаға оқытудың маңызды міндеттерінің бірі жалпы есептеу алгоритмдерін меңгерту болып табылады. Басқаша айтқанда, егер мектеп оқушысын екі санды бағанмен қосуға үйретсе, онда оған тек сол екі санды қосу ғана емес, жалпы кез-келген екі санды қосуға қолданылатын әмбебап тәсілді (алгоритмді) үйретуде дегенді білдіреді.
Мұндай мысалдарды көптеп келтіруге болады. Тек математикада ғана емес - «алгоритм» термині барлық салада қолданысқа ие болды.
Осыған байланысты сұрақ туындайды: алгоритмнің жалпы және нақты анықтамасын құруға болды ма («кез-келген алгоритм» ұғымы ) ?
Мысалы, осы анықтаманы пайдаланып, қандай-да бір нұсқаулар жиынтығы алгоритм бола алатындығын немесе бола алмайтындығын анықтауға бола ма?
Егер дұрыс мағынада айтсақ, алгоритм дегеніміз - қандай-да бір класстың кез-келген есебін шешуді қамтамасыз ететін, бірмәнді нақты анықталған қарапайым әрекеттер тізбегі.
Бірақ бұл анықтаманы алгоритмнің қатаң анықтамасы ретінде қабылдауға болмайды. Себебі оның ішінде басқа анықталмаған ұғымдар қолданылған - бірмәнділік, қарапайымдылық және т. б.
Бұл ұғымдарды алгоритмге тән жалпы қасиеттерді көрсету арқылы жетілдіруге болады. Оларға төмендегі қасиеттер жатады:
1. Алгоритмнің дискреттілігі - алгоритмнің жеке қадамдарға бөлінетінін білдіреді, сол сияқты келесі қадамның орындалуы тек қана алдыңғы қадамдағы барлық амалдар орындалып болғаннан кейін ғана мүмкін болады. Мұнда аралық мәліметтер жиынтығы аяқталған және олар алдыңғы қадамдағы мәліметтерге қандай-да бір ережені қолдану арқылы алынады.
2. Алгоритмнің детерминерленгендігі - кез келген қадамдағы аралық шамалардың жиынтығы алдыңғы қадамда болған шамалар жүйесімен бірмәнді анықталатынын білдіреді. Бұл қасиет алгоритмнің нәтижесі оның орындаушысына байланысты емес, тек енгізілген мәліметтер мен алгоритмнің өзінің қадамдарына (әрекеттер тізбегіне) байланысты екенін білдіреді.
3. Қадамдардың қарапайымдылығы - келесі шамалар жиынтығын алдыңғыдан алу заңдылығы қарапайым әрі жергілікті болу керек. Қандай қадамды (әрекетті) қарапайым деп есептеуге болатыны алгоритм орындаушысының ерекшеліктеріне байланысты анықталады.
4. Алгоритмнің нәтижелілігі - егер қандай да бір бастапқы мәліметтерден келесі шамаларды алу тәсілі нәтижеге әкелмесе, онда алгоритм нәтижесі ретінде нені есептеу керектігі көрсетілуі керек .
5. Алгоритмнің жалпылығы - бастапқы шамалар жүйесі қандай да бір жиыннан таңдалынады . Бұл қасиет бір алгоритм, яғни бір әрекеттер жиынтығы, жалпы жағдайда, кандай-да бір есептер класын (яғни, көп есептерді) шешуге қолданылатынын білдіреді.
Практикада компьютерде есепті шешу үшін бұл қасиет маңызды, себебі, неғұрлым біртипті есептердің үлкен шеңберін шешуге мүмкіндік берсе, бағдарламаның пайдаланушылық құндылығы соғұрлым жоғары болады. Бірақ алгоритмдік теория құру үшін бұл қасиет қолданысқа ие емес және міндетті болып табылмайды.
Қасиеттерді көрсету арқылы анықталған алгоритм түсінігін қатаң деп есептеуге болмайды, себебі қасиеттерді айтқанда «шама», «тәсіл», «қарапайым», «жергілікті» және басқа да нақты мағынасы ашылмаған терминдер пайдаланылды. Ары қарай бұл анықтаманы алгоритмнің қатаң емес түсінігі деп атаймыз.
Сұрақ туындайды: алгоритмнің нақты анықтамасын алу осыншама маңызды ма, егер онсыз да алгоритмдерді құрып, қолдануға болса (тіпті, терминнің өзін қолданбай-ақ) ? Және де алгоритмнің интуитивті ұғымы қатаң болмаса да анық болды, тіпті ХХ ғасырға дейін қандай да бір процесстің алгоритм болатындығы немесе болмайтындығы туралы математиктер арасында дау туындаған жағдайы болған емес.
ХХ ғасырдың басында алгоритмдік шешілуі білінбейтін мәселелер туындаған кезде жағдай бірқатар өзгерді. Шынында да, алгоритмнің бар болуын дәлелдеу үшін белгілі бір тәсілдерді пайдаланып осы есепті шешу керек, немесе ол болмаса жаңа тәсілдерді ұсыну керек - мұндай жағдайда сипатталған процестің алгоритм екеніне көз жеткізу үшін алгоритмнің интуитивті ұғымы да жеткілікті.
Қандай да бір есепті немесе есептер класын шешу алгоритмін құрудың мүмкін еместігі фактісін дәлелдеу әлдеқайда күрделірек - алгоримнің нақты анықтамасынсыз бұл мәселе өзінің мағынасын жоғалтады.
Алгоритмнің нақты анықтамасын құруды қажет ететін басқа негіз - алгоритмдік әрекеттерді орындау кезінде «қадамның қарапайымдылығы» түсінігінің анықталмағандығы болып табылады.
Математика сандық объектілерді қарастырғанда олармен орындалатын әрекеттер есептеу амалдарының қандай да бір тізбегіне келтірілетін және арифметикалық амалдар, сол сияқты шамалар арасындағы қатынасты тексеруге байланысты бірнеше логикалық амалдар (теңдік, теңсіздік, кіші, үлкен және т. б. ) элементар қадамдар деп есептелінеді.
Алайда математика кейінірек күрделі объектілердің (векторлар, матрицалар, жиындар, функциялар) қасиеттері мен оларға қолданылатын амалдарды зерттеуге көшті де, «қадамның қарапайымдылығы» түсінігі оңай көрінбейтін болды. Мысалы, интеграл алу немесе матрицаны транспонирлеуді қарапайым қадам деп қарастыруға бола ма?
Ақырында, есеп бірнеше алгоритм құруға мүмкіндік берген жағдайда теориялық және практикалық тұрғыдан алғанда оларды салыстыру және ең тиімдісін таңдау туралы сұрақ туындайды, бұл сұрақты шешу мәселесі де алгоритмнің қатаң анықтамасынсыз мүмкін емес.
Кез келген алгоритм ұғымының нақты анықтамасын, яғни, алгоритмнің барлық ойға келетін түрлері жатқызылатын максималды жалпы анықтамасын құру қажеттілігі осылайша туындады.
ХХ ғасырдың 20-шы жылдарында алгоритмнің нақты анықтамасын құру мәселесі маңызды математикалық мәселелердің біріне айналды. Бұл анықтама бір жағынан алгоритмнің интуитивті түсінігінің маңызына сәйкес келуі қажет болса, екінші жағынан формальды түрде қатаң болуы қажет болды. Осындай түсінікті құрастыру әрекеттері ХХ ғасырдың 30-шы жылдарында алгоритмдер теориясының өз алдына жеке ғылым болып қалыптасуына әкелді. Бұл ғылым математикалық логикамен бірге математиканың негізгі құралдарын - дәлелдеу тәсілдерін, аксиоматикалық теорияны құру тәсілдерін, математикалық процедуралардың қасиеттерін және т. б. қарастырады.
40-шы, 50-ші жылдарда есептеу техникасы мен оның функционалдануы мен қолданылуына байланысты ғылымдардың қарқынды дамуы кезінде осы ғылымдардың негізінде алгоритмдер теориясы жататыны анықталды, себебі компьютер алгоритмдер түрінде көрсетілетін процедураларды ғана жүзеге асыра алады.
Кез келген программа алгоритмнің орындаушы-компьютер «түсінетін» тілде жазылуы. Осылайша практикалық тұрғыдан алғанда да алгоритм ұғымын жетілдіру маңызды болып табылады.
Алгоритм түсінігін жетілдіру алгоритмдік модельдер аясында жүргізіледі. Модель есепті шешу кезінде қолдануға болатын құралдар жиынтығын көрсетеді, яғни, элементар қадамдар тізімін, келесі қадамды анықтау тәсілін, т. б.
Алгоритмдік модельдер теориялық және практикалық болуы мүмкін. Теориялық тұрғыдан алғанда модельдердің бір жағынан әмбебап болғаны, яғни, кез-келген алгоритмді сипаттауға мүмкіндік бергені, екінші жағынан неғұрлым қарапайым болғаны, яғни, есепті шешудің неғұрлым аз құралын пайдаланғаны ерекше қызығушылық тудырады. Қарапайымдылық талабы алгоритмнің нақты қажет элементтері мен қасиеттерін ерекшелеп, осы қасиеттер туралы жалпы тұжырымдарды дәлелдеуді қамтамасыз ету үшін маңызды. Практикалық және қолданбалы модельдерде программалаудың қолайлылығы мен есептеу тиімділігі маңыздырақ, сондықтан олардың құралдары (қарапайым қадамдар жиынтығы, т. б. ) әлдеқайда көп және күрделірек, бұл теориялық анализді қиындатады.
Алгоритмнің қатаң анықтамасын құрудың теориялық қырларында тарихи жағынан негізгі үш бағыт бөлініп шықты.
Бірінші бағыт аргументтердің бүтін санды мәндеріне тәуелді сандық функциялардың мәндерін есептеуге мүмкіндік беретін алгоритмдерді қарастырумен байланысты - мұндай функциялар есептелінетін функциялар атауына ие болды. Есептелінетін функциялар ұғымы алгоритмдер ұғымы сияқты қатаң ұғым емес. Бірақ А. Черчтің1, К. Гедельдің2, С. Клинидің3 еңбектерінің арқасында барлық жерде анықталған есептелінетін функциялар класының қатаң анықталатын бөлікті рекурсиялы функциялар класымен ұқсастығы негізделді. Бұл алгоритмдік шешілу мәселесін есепті шешетін рекурсиялы функцияны құру мүмкіндігін (немесе мүмкін еместігін) дәлелдеуге келтіруге мүмкіндік берді. Дәл осы жолмен А. Черчке математикалық логиканың мәселелерінің бірі - предикаттардың ақиқаттығын есептеу мәселесінің шешілмейтіндігін дәлелдеудің сәті түсті.
Екінші бағыт машиналық математикамен байланысты.
Алгоритм орындаушысы - алгоритмде көрсетілген әрекеттер тізімін орындауға қабілетті субъект немесе құрылғы. Әрбір орындаушыға әрекеттерді орындауға нұсқау - арнайы тілдер арқылы беріледі. Мұнда әрекеттерді көрсететін қызметші сөздер, сол сияқты оларды біріктіретін синтаксикалық ережелер, командалар жиынтығы орындаушының командалар жиынтығын құрайды.
Дискретті информацияны өңдеудегі қарапайым бір белгіні екіншісімен ауыстыру болып табылады. Бірақ қарапайым әрекеттер тізімін орындайтын абстрактілі және шынайы құрылғы жасауға болады. Орындаушыға арналған мұндай алгоритм құру барысында интегралданған командалар тізбегін көрсету жеткілікті, ал оларды шын қарапайым командалар тізбегіне түрлендіруді орындаушы өзі атқарады. Мұндай алгоритмдеудің «көпсатылылығы» компьютерді басқару барысында көп қолданылады.
Шын қарапайым әрекет деп процессордың әрекеттерін айтуға болады. Қазіргі процессорларда олар бірнеше жүз немесе мыңға барады.
Оларды машиналық команда, ал белгіленуін машиналық кодтар деп атайды. Машиналық кодтардан бөлінген бірінші (төменгі) деңгейдегі ассемблер коды есептелінеді, яғни ішкі (аппараттық -тәуелді) тіл. Қарапайым әрекеттерді күрделі командаларға біріктіру бұл деңгейде әлі жүргізілмейді және ассемблердің жалпы командалар саны процессордың командалар санымен бірдей болады.
Бірақ машиналық пен процессор регистрлері-мнемоникаларда символдық бейнелеу формалары қолданылады. Бұл пайдаланушыға екілік машиналық кодтан қарағанда қолайлы.
Мнемониктерді машиналық командаларға аударуды - ассемблер программасы жүзеге асырады. Программист орындаушы ретінде осы тілмен жұмыс істейді. Қарапайым әрекеттерді біріктіретін командалар жоғары деңгейдегі программалау тілдерінде көрінеді. Мысалы, «Write» сөзін программа текстінде жазу жеткілікті. Ал транслятор оларды қарапайым қадамдарға айналдырады. Программистке қарағанда бұл жағдайда орындаушы программалау тілінің трансляторы есептеледі. Бұдан жоғары қарапайым интеграциялау деңгейлерін қолданбалы программалардан көреміз. Бұл жерде ақырғы пайдаланушыға қарағанда қолданбалы программа орындаушы болып тұр. Мұндау орындаушының командалар жүйесіне барлық басқару командалары кіреді, яғни меню, экрандық батырмалар және т. б. интерфейс элементтері.
Бір команданы орындау күрделі әрекеттердің тізімін орындауға әкеледі, мысалы текстің көп жолдарын туралау.
Осылайша алгоритмді жазу барысында алгоритмді көрсету тілі формальды болуы мүмкін, ал онда орындаушының өзімен шынайы қарапайым әрекеттерге аударылатын күрделі командалар қолданылады.
Сұрыптау есептері іздеу есептері секілді негізгі болып табылады. Практикада бұл есептер өзара байланысты. Сұрыптауға байланысты есептерді шешуге көптеген іргелі ғылыми зерттеулер, көптеген алгоритмдер жасалды.
Жалпы жағдайда сұрыптауды белгілі бір ретпен берілген объектілер жиынтығын қайта құру процесі деп түсіну керек. Көбінесе деректердің үлкен көлемін сұрыптау кезінде элементтердің өздерін қайта құру мүмкін емес, сондықтан мәселені шешу үшін элементтерді индекстер бойынша ретке келтіру жүзеге асырылады. Яғни, элементтердің индекстері оларға сәйкес келетін элементтердің мәндері мәселенің шарты бойынша сұрыпталатын ретпен құрылады.
Сұрыптау реттелген жиынтықтағы элементтерді табуды жеңілдету үшін қолданылады. Сұрыптау міндеті-бағдарламалаудағы негіздердің бірі.
Сұрыптау дегеніміз-бір типтегі мәліметтер жиынтығын өсу немесе кему бойынша реттеу.
Іздеу алгоритмінен басталық.
1. 2 Іздеу және тандау алгоритмдері
Іздеу екіге бөлінеді: тізбектеліп іздеу, бинарлық іздеу.
- Тізбектеліп іздеу
Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады.
Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп іздеу кез келген тізбек үшін қолайлы, тізбектеліп іздеудің орталық тиімділігі O(n) тең болады.
- Бинарлық іздеу
Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады.
Бинарлық іздеудің алгоритмі:
... жалғасы- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.

Ақпарат
Қосымша
Email: info@stud.kz