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

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

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ СЕМЕЙ ҚАЛАСЫНЫҢ ШӘКӘРІМ АТЫНДАҒЫ МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ

СӨЖ

Тақырыбы: Сұрыптау есептері. Сұрыптау алгоритмі.

Орындаған: Сапенова Ш.

Тобы: Т-341

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

Семей қаласы,

2015 жыл.

Жоспар:

Сұрыптау алгоритмі. Алгоритм деген неСұрыптау алгоритмі, түрлері.
Сұрыптау есептері, мысалдары.

Алгоритм (ағылшынша: algorіthm, algorіsmus - Әл-Хорезмидің атынан шыққан) - бастапқы берілген мәліметтермен бір мәнде анықталатын нәтиже алу үшін қай амалды (жұмысты) қандай ретпен орындау қажеттігін белгілейтін есептерді (мәселелерді) шешу (математикалық есеп-қисаптар орындау, техникалық объектілерді жобалау, ғылыми-зерттеу жұмысын жүргізу т. б. ) тәсілдерінің дәл сипаттамасы. Алгоритм - математика мен кибернетиканың негізгі ұғымдарының бірі. Агоритмді орындау алгоритмдік процесс деп аталады.

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

Алгоритм - қазіргі математикада, оның ішінде электронды есептеуіш машинада қолданылатын негізгі ұғымдардың бірі. Белгілі бір теңдеу түбірінің жуық мәнін кез келген дәлдікпен табу оған арналған Алгоритммен есептеледі. Компьютердің кең қолданылуына байланысты Алгоритм жаңа мағынаға ие болды. Берілген есепті шешу барысында орындаушыға біртіндеп қандай әрекеттер жасау керектігін түсінікті әрі дәл көрсететін нұсқау да Алгоритм деп аталады. Алогритмді орындаушы - адам, ЭЕМ немесе робот. Әрбір нұсқау - бұйрық. Ал орындаушының жүзеге асыра алатын бұйрықтар жиыны бұйрықтар жүйесі деп аталады. Мысалы, у = (ax + b) (cx - d) функциясын есептеу ЭЕМ-да мынадай әрекеттерден құралады:

а-ны x-ке көбейту R1 деп,
оған b-ны қосу нәтижесі R2 деп,
с-ны х-ке көбейту R3 деп,
сх-тан d-ны алу R4 деп,
R2-ні R4-ке көбейту у деп белгіленеді.

Алгоритмнің бұйрықтары бірінен кейін бірі кезекпен орындалады. Бағдарлама Алгоритм тілінде жазу, бейнелеу мағынасын береді. Компьютерде Алгоритмнің сызықты, тармақты, циклді, логикалық, модельдік, параллельдік, тізбекті т. б. түрлері қолданылады.

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

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

Сұрыптау барлық программалау саласында қолданылады. Сұрыптау бұл ақпараттық объектілердің мәндерін өсу немемсе кему бойынша реттелуін іске асыратын процесс. Мысалы, егер i<= i<= . . . <= i болса, онда n - элементтеріндегі i тізімдері өсу бойынша сұрыпталады. Сұрыптау алгоритмнің екі түрі бар: операциялық жадыда немесе дискідегі файл түрінде орналастырылған массивтердің сұрыпталуы және магниттік ленталардағы немесе дисктерде орналасқан кезекті файлдардың сұрыпталуы.

Массивтерді және кезекті файлдарды сұрыптаудың негізгі ерекшелігі - массивтің әрбір элементі әр уақытта жеңіл беріледі. Ол әр уақытта массивтің кез келген элементі басқа бір массивтің элементімен салыстырылады да, массивтің кез келге екі элементтері орындарымен ауыстырылуы мүмкін. Ал кезекті файлда әрбір уақытта тек қана бір элемент беріледі. Осындай айырмашылықтардан сұрыптаудың тәсілдерінде бір-бірінен үлкен өзгерістері бар.

Кестелермен жұмыс істегенде оның негізгі операциялары - ол жазбаларды реттеу және берілген шарт бойынша жазба кестелерінде барлау жасау.

Сұрыптау - бұл кейбір критерийлері бойынша жазбаны кестелерде нақты бір тәртіппен реттеуоперациясы. Сұрыптау барлық жазбалар кілттерінің мәндерімен сәйкес іске асады (мыс., алфавит бойынша аттарын реттеу немесе сандарды өсу бойынша реттеу) . Сұрыптаудың көптеген бір-бірінен айрықша тәсілдері бар. Егер де кесте бүтіндей ЭЕМ-нің жедел жадында орналасса, онда оның реттелуі ішкі деп аталады. Ал егер де реттелген мәліметтерді сақтау үшін сыртқы есте сақтау құрылғысы пайдаланса, онда бұндай реттелу сыртқы деп аталады. Операцияларды салыстырудың орташа саны, сұрыптаудың тәсілінен байланысты, және де рационалды тәсілді таңдаған кезде кейбіреулері минимумға жетеді. Ішкі сұрыптау тәсілдерін екі топқа бөлуге болады:

Резервтік жадыны қажет ететін тәсілдер
Резервтік жадыны қажет етпейтін тәсілдер

Бірінші топқа таңдау, енгізу, көпіршік (пузырька), Шелл тәсілдері жатса, екінші топқа квадраттық таңдау, қосылу тәсілі және т. б жатады. Қарапайым сұрыптау тәсілдері (таңдау, енгізу, ауыстыру) шамамен n**2 салыстыруынталап етеді. Әдетте одан да қиынырақ алгоритмдер орташа n*log2(n) салыстыруларында нәтиженің берілуін қамтамасыз етеді. Бірақ та кез келген жағдайларда қолайлы сұрыптау жоқ, себебі олардың тиімділігі кестедегі кілттердің түріне және олардың алдын ала реттелуіне байланысты.

Сұрыптаудың мақсаты - сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету.

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

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

Бүгінгі таңда сұрыптаудың көптеген тәсілдері белгілі. Олар:

Таңдау арқылы сұрыптау - бұл сұрыптаудың ең қолайлы түрі. Әдетте бұл әдіс кестені реттеуді қажет еткен адам ойына ең бірінші келеді. Бұның мәні мынада, мысалы n элементтен тұратын А сандар массиві берілген. Оны таңдау әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет. Алгоритмі:

Өлшемі n болатын А массивін толтыру және экранға шығару;
i:=1;
Индекс i-ден басталатын массив элементтерінің ішінен ең кішісін (индексі j) таңдап алу;
A[i] және A[j] элементтерінің орындарын ауыстыру;
i:=i+1 мәні үшін i:=n болғанға дейін 3 және 4 қадамдарды қайталау;
Сұрыпталған А массивін экранға шығару.

Алмастыру арқылы сұрыптау - алгоритмдік сұрыптаудың ең жеңіл түрі болып табылады. Бұл алгоритмдік сұрыптау өте жеңіл, әрі оңай, себебі бұл сұрыптау улкен емес массивтерге қолданылады. Алгоритмнің қиындығы: O( n ²) .

Қайтсе де сұрыптаудың кез-келген әдісі алмастырумен, яғни жадыда екі элементтін орын ауыстырумен байланысты. Бірақ басқа әдістер үшін бұл әрекет көмекші болса, алмастыру сұрыптауы үшін бұл - процесстің басты сипаты болып табылады. Алмастыру арқылы сұрыптаудың мәні кестенің қатар тұрған элементтерін қос-қостан көптеп салыстырып және осы элементтерді берілген ретпен орын ауыстыруда. Бұның мәні мынада, Мысалы n элементтен тұратын А сандар массиві берілген. Оны алмастыру әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет. Алгоритмі:

Өлшемі n болатын А массивін толтыру және экранға шығару;
i:=1;
A[i] >A[i+1] элементтерінің орындарын ауыстыру;
i:=i+1 мәні үшін i:=n болғанға дейін 3 қадамды қайталау;
Сұрыпталған А массивін экранға шығару.

Индекстері арқылы сұрыптау - сұрыптаудың бірден-бір түрі. n элементтен тұратын А сандар массиві берілген. Массивті индекстері (индекстер массивін жасақтау) арқылы элементтерінің өсуі бойынша сұрыптайық. Алгоритмі:

Өлшемі n болатын А массивін толтыру және экранға шығару;
i:=1;
Индекс i-ден басталатын массив элементтерінің ішінен ең кішісін (индексі j) таңдап алу;
A[i] және A[j] элементтерінің орындарын ауыстыру;
i:=i+1 мәні үшін i:=n болғанға дейін 3 және 4 қадамдарды қайталау;
Сұрыпталған А массивін экранға шығару.

Енгізу арқылы сұрыптау - бұл массивтің сұрыпталмаған бөлігінен сұрыпталған бөлігіне элементтерді енгізу болып табылады. Енгізілген элемент массив бөлігінің сұрыпталуын бұзбау қажет. Ол үшін енгізілген элемент өз орнын тапқанша, сұрыпталған бөлігінің элементтерімен орын ауыстырып отыруы тиіс. Өлшемі n болатын А массивін толтыру және экранға шығару;

i:=2;
j:=i-1;
Егер A[j+1] =A[j] болса, онда олардың орындарын ауыстырамыз және j:=j-1, әйтпесе j:=0;
j:=0 болғанға дейін 3 және 4 қадамдарды қайталау;
i:=i+1;
i:=n болғанға дейін 3, 4, 5, 6 қадамдарды қайталау;

Біріктіру арқылы сұрыптау - массив элементтерін бөліктерген бөліп, бөлек-бөлек сұрыптау.