Сұрыптау әдіс тәсілдері

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

ОҢТҮСТІК ҚАЗАҚСТАН МЕМЛЕКЕТТІК ПЕДАГОГИКАЛЫҚ
УНИВЕРСИТЕТІ

Физика-математика_______________ факультеті

Информатика ________________кафедрасы

КУРСТЫҚ ЖҰМЫС

Тақырыбы: Сұрыптау әдістері_________________________

Пәні : Информатиканың теориялық негіздері ___________

Мамандығы: Физика-информатика ____________________

Орындаған : Дармен И.______________________________

Қабылдаған: т.ғ.к Қалдарова Б._______________________

Комиссия мүшелері: Жамалова К._____________________

Aлиева А._______________________

Шымкент 2019

Оңтүстік Қазақстан мемлекеттік педагогикалық университеті

Физика-математика_________ факультеті
Информатика ____________кафедрасы

БЕКІТЕМІН
Кафедра меңгерушісі
Сулейменова Л.
(қолы) (аты-жөні)
___ ________ 20__ ж.

Студенттің курстық жұмысына берілетін
ТАПСЫРМА
Дармен Индира Мұратқызы
1. Жұмыстың тақырыбы: Сұрыптау әдістері___________________________
2. Жұмыстың аяқталу уақыты: 06.05.2019ж________________________ ____
3. Жұмысқа керек материалдар: ғылыми әдістемелік журналдар, оқулықтар, интернет.
4. Жұмыстың мазмұны (әдебиеттік және патенттік ізденісі, экспериментальдық бөлім, заттың шығу сипаттамасы ,эксперименттік әдістемесі ,экспериментальдық материалдарға талдау ,қорытынды)________________________ __
5. Кеспелік және графикалық материалдардың тізімі
6. Әдебиеттер тізімі:

1. Программалар мен алгоритмдердің анализдері және құрылымдары
А.Ө. Муртазина, Б.Б. Тусупова Алматы 2001

2. Программирование на языке Си В.В. Подбельский , С.С. Фомин
Москва , Финансы и статистика 1998

3. Работаем на языке СИ В.К. Потоцкий Москва , Малип 1992

4. Основы Turbo Pascal 7.0 В.В. Фаронов Москва 2000

5. Введение в язык Pascal В.Г. Абрамов Москва , Наука 1992
6 . Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching - 2-е изд. -М.:Вильямс, 2007. -С. 824.
1. Ананий В. Левитин Глава 11. Преодоление ограничений: Метод деления пополам [= 0-201-74395-7 Алгоритмы: введение в разработку и анализ] = Introduction to The Design and Analysis of Aigorithms -М.:Вильямс, 2006. -С. 476-480.
2. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. -М.:МИФИ, 1982.
3. Кузнецов С.Д. Методы сортировки и поиска. www.lib.csu.rudlbasesprgcitforu mtheorysortingsorting1.shtm1
4. https:kk.m.wikipedia.org
5. https:stud.kz
6.

7. Тапсырманың берілген уақыты:

8. Курстық жұмыстың жетекшісі:_________ т.ғ.к Қалдарова Б_____________

9. Тапсырманы алған студент:____________Дармен Индира 128-16 тобы ____

Мазмұны

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
I Сұрыптау алгоритмі ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... .
1.1 Ішкі сұрыпталу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
1.2 Сыртқы сұрыпталу ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ...
II. Сұрыптау әдіс тәсілдері :
2.1 Енгiзу (қою) арқылы сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
2.2 Таңдау арқылы сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
2.3 Алмастыру арқылы сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
2.4 Индекстері арқылы сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
2.5 Енгізу арқылы сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
2.6 Тiкелей бiрiгу əдiсi ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
2.7 Табиғи бiрiгу əдiсi ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
2.8 Сұрыптаудың Хоар әдісі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
2.9 Пузырёк тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
2.10 Шелл сұрыптауы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
III. Сұрыптаудың альтернативтiк əдiстерi
Қорытынды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
Пайдаланған әдебиеттер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
КІРІСПЕ

Жаңа реттеулер енгізуден қиын, сәттілігі жағынан күдікті, жүзеге
асыруы жағынан қауіпті жұмыс жоқ .
Никколо Макьявелли (1513)

Біз барлық автомобильдердің нөмірін қарастырып үлгермейміз,- деді Дрейк. Ал бізге оны істеп қажеті жоқ, Пол. Біз тек ғана оларды реті бойынша қойып,олардың бірдейлерін іздейміз.
"The Case of Angry Mourner" (1951)

Бұл айтылған пікірлердің барлығы программалаудың ең бір қажетті мүмкіндіктері сұрыптау мен іздеуге арналған. Сұрыптау мен іздеуді кез-келген программада қолдануға болады.олардың мүмкіндіктері шексіз. Осы мүмкіндіктерді пайдалана отырып, программа алгоритімін қарапайым жолмен жеңілдетуге болады. Негізінен сұрыптау мен іздеудің түрлері өте көп.
Кез-келген күнделікті жағдайда біз сұрыптау және іздеу үрдістерімен жұмыс жасаймыз. Әр адамда неліктен деген сұрақ туады. Жауап өте қарапайым. Себебі бұл үрдістермен жұмыс жасау өте ыңғайлы. Тіпті өзіміздің күнделікті қолданып жүрген персоналды компьютерімізде сол принциппен жұмыс істейді. Олар сіз енгізген мәліметтерді сұрыптап қояды да сіз оларды іздегенде лезде тауып бере қояды. Сұрыптау мен іздеу тәсілдерін кеңінен қолданады. Бұл тәсілдерді қарапайым студентте кәсіпқой программистте қолдана алады. Жалпы алғанда кез-келген программа сұрыптаудан басталады. Ал тез сұрыптап қажет элементті табу үшін сұрыптау және іздеу тәсілдерін жетік білген жөн. Сондықтан сұрыптау мен іздеу тәсілдерін қарастырып көрейік.

Сұрыптау (Селекция; селецтіон; Сортировка; сортінг) - массив элементтерін белгілі бір заңдылықпен орындарын ауыстырып реттеу процессін айтамыз. Сұрыптауды көбіне массивтерді және файлдарды сұрыптағанда көп қолданады. Бұл екеуін әдетте ішкі және сыртқы сұрыптаулар деп атайды. Массивтер "ішкі" (жедел) жадыда орналасатындықтан, ішкі сұрыптау болады. Бұл жадыға тез қатынаймыз, ал файлдар бұдан бәсеңдеу, бірақ сыйымдылығы үлкендеу "сыртқы" жадыда, яғни есте сақтау құрылғыларында (диск, лента т.б.) сақталатындықтан, оны сыртқы сұрыптау деп атаймыз.
Ішкi сұрыптау алгоритмінің тиiмдiлiгiн анықтауда кiлттiк өрiстiң мəнiн салыстыру саны (С) мен элементтердi алмастыру саны (М) негiзге алынады.
Ішкі сұрыптау тәсілдерін екі топқа бөлуге болады:резервтік жадыны қажет ететін тәсілдер және резервтік жадыны қажет етпейтін тәсілер.Бірінші топқа таңдау,енгізу,Шелл тәсілдері жатса,екінші топқа квадраттық таңдау,қосылу тәсілі жатады.Қарапайым Сұрыптау тәсілдері (таңдау,енгізу,ауыстыру ) шамамен n**2 салыстыруын талап етеді.Әдетте одан 0иыныра0 алгоритмдер орташа n*log2(п) салысьтыруында нәтиже шығаруын қамтиды.Бірақ кез-келген жағдайға қолайлы сұрыпталу жоқ.
Сыртқы сұрыптау
Сыртқы жадта орналасқан файлдар тiзбегiн сұрыптау - сыртқы сұрыптау делінеді. Негiзiнен, сыртқы сұрыптау Берілгендер қорын басқару жүйелерінде (БҚБЖ-де) сұраныстарды орындауда қолданы- лады. БҚБЖ-нiң өнiмдiлiгi қолданылатын əдiстiң тиiмдiлiгiне қарай анықталады.
Сыртқы сұрыптау əдiстерi сыртқы жад үшiн магниттiк ленталар қолданыла бастаған кезеңде пайдаланынады. Мұндай ленталарда мəлiметтер тiзбектей сақталады. Бiрақ магниттiк дискi түрiндегi есте сақтау құрылғылары пайда болуымен, əрбiр ақпарат блогына тiкелей енуге мүмкiндiк туды. Файлдар дискiге жолшалар мен секторлар бойынша жазылатындықтан, бiр файл дискiге бiрнеше бөлiкшемен сақталуы мүмкiн. Ал бұл мəлiметтердi дискiге жазу жəне оқу бастиегiн (головка) көбiрек қозғалысқа түсіредi. Қазiргi кезде файл блоктарын мүмкiндiгiнше дискiде бiр-бiрiне жақын орналастыру жағдайлары қарастырылуда. Мысалы, дискiнi оптимизациялау, дефрагментациялау программалары осы мақсатта қолданылады. Сондықтан файлдың блоктары дискiде тiзбектей орналасқанда ғана, бастиек азырақ қозғалысқа түсiп, аз уақыт шығындалады. Қазiргi кездегi БҚБЖ-лер тек осындай файлдарды іріктейді.
Сыртқы сұрыптаудың жылдамдығына жедел жадтың буферiнің өлшемi де ықпал етедi. Бiз, мүмкiндiгiнше, оперативтік жадтан аз орын талап ететiн негiзгi сырттай сұрыптау əдiстерiн қарастырамыз.

Сұрыптау мақсаты - көптеген сұрыпталған обьектінің ішінен белгілі бір элементті іздеуді оңайлату. Ақпараттық жүйелерде мәліметтерді сұрыптаудың маңызы өте зор.Бүгінгі таңда сұрыптаудың көптеген әдістері белгілі. Олар:
1. Енгiзу (қою) арқылы сұрыптау
2. Таңдау арқылы сұрыптау
3. Алмастыру арқылы сұрыптау
4. Индекстері арқылы сұрыптау
5. Енгізу арқылы сұрыптау
6. Тiкелей бiрiгу əдiсi
7. Табиғи бiрiгу əдiсi
8. Сұрыптаудың хоор әдісі
9. Пузырёк тәсілі
10. Шелл сұрыптауы

1. Массивтерді сұрыптау - алгоритмдеріне
қойылатын басты талап - жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау,
таңдаумен сұрыптау, алмасумен сұрыптау (көбікше әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау),
бөліктеу арқылы сұрыптау (жылдам сұрыптау).
Бұл сұрыптау жылдам сұрыпталу - сұрыпталған ең тезі және ең Бөліктеу арқылы Тізбекте қажетті элементтерді жақсысы болып есептеледі.
Іздестіруді жеңілдетеді табылады. Мәліметтерді тез сұрыптауға мүмкіндік беретін алгоритм, атап айтқанда, сандық мәліметтерді өсу реті бойынша немесе мәтіндік мәліметтерді алфавит ретімен орналастыру. Алгоритм тізіммен берілген әрекетті орындайды және тізімнің әр жерінде орналасқан мәліметтерді салыстырады. Бірнеше жүз элементген тұратын айтарлыктай үлкен тізімдер үшін қолданылады.
Бұл сұрыптаудың өте қолайлы түрі, әдетте
Алгоритмі:
Өлшемі n болатын А массивін толтыру
i:=1;
Индексі i-ден басталатын массив элементтерінің ішінен
A[i] және A[j] элементтерінің орндарын ауыстыру;
i:=i+1 мәні үшін i:=n болғанға дейін
Сұрыпталған A массивін экранға шығару;
7 13
1 13
13
13
1
Программалау
Program
Const n=8;
type MasType = array [1..n]
var i, idx, k:integer;
A: MasType;
Function MinMas(j: integer): integer;
Var p,min: integer;
Begin
For p:=j to n do
If (p=j) or (A[p]MinMas:=min;
End;

1.Енгiзу (қою) арқылы сұрыптау
Əдіс - қарапайым iшкi сұрыптау əдісіне жатады. Берiлген а[1], а[2],...,а[n] массивінiң екiншi элементiнен бастап əрбiр элементi өзiмен қатар орналасқан индексi кiшi элементпен салыстырылады. а[i] элементi a[i-1], a[i-2] элементтерiмен тiзбектей салыстырады.
Егер де а[j] келесi элементi үшiн а[j]a[i] теңсіздігі орындалса, онда а[i] мен а[j] элементтерінің орындары алмастырылады.
Егер де а[j] үшiн а[j] a[i] теңсіздігі орындалса не массивтiң соңғы элементi салыстырылса, онда процесс а[i+1] үшiн жүргiзiледi.
А массивінің 2-элементі таңдалынады. Əрбiр а[i] жаңа элементi a[1],a[2],...,a[i-1] реттелген тiзбегiнiң тиісті орнына орналастыры- лады. Бұл орын а[i] элементін а[1],a[2],...,a[i-1] реттелген элемент- терімен жеке-жеке салыстыру барысында анықталады. Əрбiр элементтi қажеттi орынға орналастыру барысында өзге элементтер 1 орынға (позицияға) жылжытылады.
Енгiзу арқылы сұрыптау əдiсiн элементтерінің саны 10 аспайтын, не жартылай іріктеліп қойған массивтерді сұрыптауда қолданған тиімді. Кемшілігі - алгоритмнің күрделілігі өте жоғары, O(n2) арқылы бағаланады.
Мысалы, 8,23,5,65,44,33,1,6 тізбегі н енгiзу арқылы сұрыптау
қажет болсын (.1-кесте).

i=2
i=3
i=4
i=5
i=6
i=7
i=8
Бастапқы тізбек
8
23
5
65
44
33
1
6
i=2
8
23
5
65
44
33
1
6

i=3
8
23
5
65
44
33
1
6

8
5
23
65
44
33
1
6

5
8
23
65
44
33
1
6
i=4
5
8
23
65
44
33
1
6
i=5
5
8
23
65
44
33
1
6

5
8
23
44
65
33
1
6
i=6
5
8
23
44
65
33
1
6

5
8
23
44
33
65
1
6

5
8
23
33
44
65
1
6

i=7
5
8
23
33
44
65
1
6

5
8
23
33
44
1
65
6

5
8
23
33
1
44
65
6

5
8
23
1
33
44
65
6

5
8
1
23
33
44
65
6

5
1
8
23
33
44
65
6

1
5
8
23
33
44
65
6

i=8
1
5
8
23
33
44
65
6

1
5
8
23
33
44
6
65

1
5
8
23
33
6
44
65

1
5
8
23
6
33
44
65

1
5
8
6
23
33
44
65

1
5
6
8
23
33
44
65

2.Таңдау арқылы сұрыптау - бұл сұрыптаудың ең қолайлы түрі. Әдетте бұл әдіс кестені реттеуді қажет еткен адам ойына ең бірінші келеді. Бұның мәні мынада, мысалы н элементтен тұратын Асандар массиві берілген. Оны таңдау әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет
Алгоритм
1. Ең үлкен (не ең кіші) элемент таңдалынады.
2. Ол а[1] бiрiншi элементімен алмастырылады. Нəтижеде ең үлкен (не ең кіші) элемент бiрiншi орынға жылжытылады.
3. Əрi қарай массивтiң тек іріктелмеген бөлiгi қарастырылады.
1-3 іс-əрекеттер əрекеттер (n-1), (n-2),... элементерi үшiн ең кiшi элемент анықталғанша қайталап орындалады.

Мысалы, 8,23,5,65,44,33,1,6 тізбегі н таңдау арқылы сұрыптау қажет болсын (2-кесте).
2-кесте
Бастапқы тізбек
8
23
5
65
44
33
1
6
1-қадам
1
23
5
65
44
33
8
6
2-қадам
1
5
23
65
44
33
8
6
3-қадам
1
5
6
65
44
33
8
23
4-қадам
1
5
6
8
44
33
65
23
5-қадам
1
5
6
8
33
44
65
23
6-қадам
1
5
6
8
23
44
65
33
7-қадам
1
5
6
8
23
33
65
44
8-қадам
1
5
6
8
23
33
44
65

3. Көпіршікті сұрыптау əдісі
Бұл əдiс қатар орналасқан 2 элементтi салыстыруға негiзделген. Егер де массив элементтері тік бағытта, баған құрай орналасса, онда оларды шыны ыдыстағы көпіршіктер ретінде елестетуге болады. Бұл жағдайда əрбір көпіршік өзінің салмағына қарай тиісті биіктікке дейін көтеріліп, орналасады. Көпіршікті сұрыптау атауына осыған қатысты ие болған. Сұрыптаудың мəні:
1. Алғашқы 2 элемент салыстырады. Егер 1-элемент 2-элементтен кiшi болса, онда олардың орындары ауыстырылады.
2. 2-шi мен 3-элемент, 3-шi мен 4-элемент жəне т.с.с. салыстырылып, қажет болған жағдайда олардың орындары алмастырылады. Нəтижеде ең кiшi элемент соңғы орынға ауыстырылады.
Массив элементтерiн толық іріктеп орналастыруда осы əрекет
(n-1) рет орындалады. Мұндағы n - массив элементтерінің саны.
Əр қайталануда алмастырудың орындалуын сипаттайтын айнымалы мəнiн енгiзiп, процестiң аяқталғанын (аяқталмағанын) бақылап отыруға болады.
Кейде бұл əдiс - Алмастыру арқылы сұрыптау əдісі деп те аталады. Бұл əдiс бойынша салыстырулар саны n(n-1)2 -ге тең.
Əдiс жетiлдiрудi қажет етедi. Кемшіліктері:
1. Егер қандай да бiр қадамда ешқандай алмастыру орындалмаса, онда алгоритм жұмысы тоқтатылуы тиiс.
2. Ағымдық қадамда алмастыру жасалған массив индексiнiң ең кiшi мəнi есте сақталуы тиiс. Массивтiң осы индекстi элементiне дейінгі бастапқы элементтерi сұрыпталып қойғандықтан, массивтiң аталған индекстi элементі мен көршi элементiн салыстырудың қажетi жоқ.

Мəнi кiшi элементтер бір ғана алмастырудан кейiн қажеттi орынға қойылса, мəнi үлкен элементтер тек алгоритм толық орындалғаннан кейiн ғана қажеттi орынға орналастырылуы мүмкін.
Алмастыру арқылы сұрыптау - алгоритмдік сұрыптаудың ең жеңіл түрі болып табылады.Бұл алгоритмдік сұрыптау өте жеңіл, әрі оңай, себебі бұл сұрыптау улкен емес массивтерге қолданылады. Алгоритмнің қиындығы: О(н²).
Қайтсе де сұрыптаудың кез-келген әдісі алмастырумен, яғни жадыда екі элементтін орын ауыстырумен байланысты. Бірақ басқа әдістер үшін бұл әрекет көмекші болса, алмастыру сұрыптауы үшін бұл - процесстің басты сипаты болып табылады. Алмастыру арқылы сұрыптаудың мәні кестенің қатар тұрған элементтерін қос-қостан көптеп салыстырып және осы элементтерді берілген ретпен орын ауыстыруда. Бұның мәні мынада, Мысалы н элементтен тұратын А сандар массиві берілген. Оны алмастыру әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет.
Алмастыру арқылы сұрыптау
Алгоритм
Өлшемі н болатын А массивін толтыру және экранға шығару;
і:=1;
А[і] А[і+1] элементтерінің орындарын ауыстыру;
і:=і+1 мәні үшін і:=н болғанға дейін 3 қадамды қайталау;
Сұрыпталған А массивін экранға шығару.
Программалау
----------------------------------- ----------------------------------- ----------
Program Aikesha_lay;
----------------------------------- ----------------------------------- ----------
Const n=8;
----------------------------------- ----------------------------------- ----------
var i, j, k: integer;
----------------------------------- ----------------------------------- ----------
A:array [1..n] of integer;
----------------------------------- ----------------------------------- ----------
p:boolean;
----------------------------------- ----------------------------------- ----------
Begin
----------------------------------- ----------------------------------- ----------
Randomize; Writeln('Берілген сандар массиві:');
----------------------------------- ----------------------------------- ----------
For i:=1 to n do
----------------------------------- ----------------------------------- ----------
Begin A[i]:=Random(25); Write(A[i]:4); end;
----------------------------------- ----------------------------------- ----------
Repeat
----------------------------------- ----------------------------------- ----------
p:=true;
----------------------------------- ----------------------------------- ----------
For i:=1 to n-1 do
----------------------------------- ----------------------------------- ----------
If A[i]A[i+1] then begin
----------------------------------- ----------------------------------- ----------
k:=A[i]; A[i]:=A[i+1]; A[i+1]:=k;
----------------------------------- ----------------------------------- ----------
p:false;
----------------------------------- ----------------------------------- ----------
end;
----------------------------------- ----------------------------------- ----------
until p;
----------------------------------- ----------------------------------- ----------
writeln;
----------------------------------- ----------------------------------- ----------
writeln('Өсуіне қарай сұрыптау нәтижесі:');
----------------------------------- ----------------------------------- ----------
For i:=1 to n do
----------------------------------- ----------------------------------- ----------
Write(A[i]:4);
----------------------------------- ----------------------------------- ----------
readln;
----------------------------------- ----------------------------------- ----------
end.
4.Индекстері арқылы сұрыптау - сұрыптаудың бірден-бір түрі. н элементтен тұратын А сандар массиві берілген. Массивті индекстері ... жалғасы

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