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

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 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.

Ананий В. Левитин Глава 11. Преодоление ограничений: Метод деления пополам // [= 0-201-74395-7 Алгоритмы: введение в разработку и анализ] = Introduction to The Design and Analysis of Aigorithms -М. :Вильямс, 2006. -С. 476-480.
Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. -М. :МИФИ, 1982.
Кузнецов С. Д. Методы сортировки и поиска. www. lib. csu. ru/dl/bases/prg/citforum/theory/sorting/sorting1. shtm1
https://kk. m. wikipedia. org
https://stud. kz

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н қарастырамыз.

Сұрыптау мақсаты - көптеген сұрыпталған обьектінің ішінен белгілі бір элементті іздеуді оңайлату. Ақпараттық жүйелерде мәліметтерді сұрыптаудың маңызы өте зор. Бүгінгі таңда сұрыптаудың көптеген ә дістер і белгілі. Олар:

Енгiзу (қою) арқылы сұрыптау
Таңдау арқылы сұрыптау
Алмастыру арқылы сұрыптау
Индекстері арқылы сұрыптау
Енгізу арқылы сұрыптау
Тiкелей бiрiгу əдiсi
Табиғи бiрiгу əдiсi
Сұрыптаудың хоор әдісі
Пузырёк тәсілі
Шелл сұрыптауы

Массивтерді сұрыптау - басты талап - жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі) . Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау) . Бұл сұрыптау жылдам сұрыпталу - сұрыпталған ең тезі және ең Бөліктеу арқылы Тізбекте қажетті элементтерді жақсысы болып есептеледі. Іздестіруді жеңілдетеді табылады. Мәліметтерді тез сұрыптауға мүмкіндік беретін алгоритм, атап айтқанда, сандық мәліметтерді өсу реті бойынша немесе мәтіндік мәліметтерді алфавит ретімен орналастыру. Алгоритм тізіммен берілген әрекетті орындайды және тізімнің әр жерінде орналасқан мәліметтерді салыстырады. Бірнеше жүз элементген тұратын айтарлыктай үлкен тізімдер үшін қолданылады. Бұл сұрыптаудың өте қолайлы түрі, әдеттеАлгоритмі:Өлшемі n болатын А массивін толтыруi:=1; Индексі i-ден басталатын массив элементтерінің ішіненA[i] және A[j] элементтерінің орндарын ауыстыру; i:=i+1 мәні үшін i:=n болғанға дейінСұрыпталған A массивін экранға шығару; 7 131 n=8; type MasType = array [1. . n] var i, idx, k:integer; A: MasType; Function MinMas(j: integer) : integer; Var p, min: integer; BeginFor p:=j to n doIf (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

i=2:

23

i=3: 5

i=4:

65

i=5:

44

i=6:

33

i=7: 1

i=8: 6

: i=2

8

i=2:

23

i=3: 5

i=4:

65

i=5:

44

i=6:

33

i=7: 1

i=8: 6

: i=3

8

i=2:

23

i=3: 5

i=4:

65

i=5:

44

i=6:

33

i=7: 1

i=8: 6

8

: 5

i=2:

23

i=3:

65

i=4:

44

i=5:

33

i=6: 1

i=7: 6

5

: 8

i=2:

23

i=3:

65

i=4:

44

i=5:

33

i=6: 1

i=7: 6

: i=4

5

i=2: 8

i=3:

23

i=4:

65

i=5:

44

i=6:

33

i=7: 1

i=8: 6

: i=5

5

i=2: 8

i=3:

23

i=4:

65

i=5:

44

i=6:

33

i=7: 1

i=8: 6

5

: 8

i=2:

23

i=3:

44

i=4:

65

i=5:

33

i=6: 1

i=7: 6

: i=6

5

i=2: 8

i=3:

23

i=4:

44

i=5:

65

i=6:

33

i=7: 1

i=8: 6

5

: 8

i=2:

23

i=3:

44

i=4:

33

i=5:

65

i=6: 1

i=7: 6

5

: 8

i=2:

23

i=3:

33

i=4:

44

i=5:

65

i=6: 1

i=7: 6

: i=7

5

i=2: 8

i=3:

23

i=4:

33

i=5:

44

i=6:

65

i=7: 1

i=8: 6

5

: 8

i=2:

23

i=3:

33

i=4:

44

i=5: 1

i=6:

65

i=7: 6

5

: 8

i=2:

23

i=3:

33

i=4: 1

i=5:

44

i=6:

65

i=7: 6

5

: 8

i=2:

23

i=3: 1

i=4:

33

i=5:

44

i=6:

65

i=7: 6

5

: 8

i=2: 1

i=3:

23

i=4:

33

i=5:

44

i=6:

65

i=7: 6

5

: 1

i=2: 8

i=3:

23

i=4:

33

i=5:

44

i=6:

65

i=7: 6

1

: 5

i=2: 8

i=3:

23

i=4:

33

i=5:

44

i=6:

65

i=7: 6

: i=8

1

i=2: 5

i=3: 8

i=4:

23

i=5:

33

i=6:

44

i=7:

65

i=8: 6

1

: 5

i=2: 8

i=3:

23

i=4:

33

i=5:

44

i=6: 6

i=7:

65

1

: 5

i=2: 8

i=3:

23

i=4:

33

i=5: 6

i=6:

44

i=7:

65

1

: 5

i=2: 8

i=3:

23

i=4: 6

i=5:

33

i=6:

44

i=7:

65

1

: 5

i=2: 8

i=3: 6

i=4:

23

i=5:

33

i=6:

44

i=7:

65

1

: 5

i=2: 6

i=3: 8

i=4:

23

i=5:

33

i=6:

44

i=7:

65

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

Алгоритм

Ең үлкен (не ең кіші) элемент таңдалынады.
Ола[1] бiрiншi элементімен алмастырылады. Нəтижеде ең үлкен (не ең кіші) элемент бiрiншi орынға жылжытылады.
Əрi қарай массивтiң тек іріктелмеген бөлiгi қарастырылады.

1-3 іс-əрекеттер əрекеттер (n-1), (n-2), … элементерi үшiн ең кiшi элемент анықталғанша қайталап орындалады.

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

2-кесте

Бастапқы тізбек

23

65

44

33

Бастапқы тізбек:

1-қадам

8: 1

23:

23

5: 5

65:

65

44:

44

33:

33

1: 8

6: 6

Бастапқы тізбек:

2-қадам

8: 1

23: 5

23

65:

65

44:

44

33:

33

1: 8

6: 6

Бастапқы тізбек:

3-қадам

8: 1

23: 5

5: 6

65:

65

44:

44

33:

33

1: 8

23

Бастапқы тізбек:

4-қадам

8: 1

23: 5

5: 6

65: 8

44:

44

33:

33

65

23

Бастапқы тізбек:

5-қадам

8: 1

23: 5

5: 6

65: 8

44:

33

33:

44

65

23

Бастапқы тізбек:

6-қадам

8: 1

23: 5

5: 6

65: 8

44:

23

33:

44

65

33

Бастапқы тізбек:

7-қадам

8: 1

23: 5

5: 6

65: 8

44:

23

33:

33

65

44

Бастапқы тізбек:

8-қадам

8: 1

23: 5

5: 6

65: 8

44:

23

33:

33

44

65

3. Көпіршікті сұрыптау əдісі

Бұл əдiс қатар орналасқан 2 элементтi салыстыруға негiзделген. Егер де массив элементтері тік бағытта, баған құрай орналасса, онда оларды шыны ыдыстағы көпіршіктер ретінде елестетуге болады. Бұл жағдайда əрбір көпіршік өзінің салмағына қарай тиісті биіктікке дейін көтеріліп, орналасады. Көпіршікті сұрыптау атауына осыған қатысты ие болған. Сұрыптаудың мəні:

Алғашқы 2 элемент салыстырады. Егер 1-элемент 2-элементтен кiшi болса, онда олардың орындары ауыстырылады.
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. Кемшіліктері:

Егер қандай да б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;

А[і] >А[і+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. Индекстері арқылы сұрыптау - сұрыптаудың бірден-бір түрі. н элементтен тұратын А сандар массиві берілген. Массивті индекстері (индекстер массивін жасақтау) арқылы элементтерінің өсуі бойынша сұрыптайық.

Алгоритм

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

Программалау

Program Aikesha_lay;

Const n=8;

var i, j, k: integer;

A, IDX:array [1. . n] of integer;

Begin

Randomize; Writeln('Берілген сандар массиві:') ;

For i:=1 to n do

Begin A[i] :=Random(40) ; IDX[I] :=1; Write(A[i] :4) ; end;

For i:=n downto 2 do

For j:=i - 1 downto 1 do

If A[i] <A[j] then IDX[j] :=IDX[j] +1 else

IDX[i] :=IDX[i] +1;

writeln;

writeln('Өсуіне қарай сұрыптау индекстері:') ;

For i:=1 to n do

Write(IDX[i] :4) ;

readln;

end.

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

Енгізу арқылы сұрыптау

Алгоритм

1. Өлшемі н болатын А массивін толтыру және экранға шығару;

2. і:=2;

3. ж:=і-1;

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

Программалау

Program Aikesha_lay;

Const n=8;

var i, j, k: integer;

A:array [1. . n] of integer;

Begin

Randomize; Writeln('Берілген сандар массиві:') ;

For i:=1 to n do

Begin A[i] :=Random(30) ; Write(A[i] :4) ; end;

For i:=2 to n do

begin

j:=i-1;

Repeat

If A[j+1] <=A[j] then begin k:=A[j] ; A[j] :=A[j+1] ; A[j+1] :=k; j:=j-1;

end else j:=0;

until j=0;

end;

writeln;

writeln('Өсуіне қарай сұрыптау нәтижелері:') ;

For i:=1 to n do

Write(A[i] :4) ;

readln;

end.

6. Тiкелей бiрiгу əдiсi

а1, а2 . . . , ап жазуларынан тұратын А тiзбектi файлы берiлсiн жəне n саны 2-нiң дəрежесi болсын. Əрбiр жазуда сұрыптаудың кiлтi анықталған бiр ғана өрiс болсын. Сұрыптаудың барысында əрқайсысының өлшемi n/2 болатын В жəне С қосалқы файлдары құрылады (А файлы: 8, 23, 5, 65, 44, 33, 1, 6) .

Алдымен, А файлы В жəне С файлдарына бөлiнедi де, соңынан қайтадан А файлына біріктіріледі (ВUC=А) .

-қадам. Афайлыныңа1, а3, . . . , ап-1жазуларыВфайлына, ала2, а4, . . . , апжазуларыСфайлына жазылады. Алғашқы бiрiгу(а1, а2), (а3, а4), . . . , (ап-1, ап) жұптарының арасында жүргiзiледі де, нəтижеАфайлына жазылады (11. 1-сурет) .

В В файлы: 8 5 44 1

С файлы: 23 65 33 6

8

23

5

65

44

33

1

6

А файлы:

8

23

5

65

33

44

1

6

-сурет. АфайлынВ, Сфайлдарына бірінші рет бөліктеу жəнеА

файлына қайта біріктіру.

-қадам. Афайлы қайта оқылып, оның тақ нөмiрi жазулары жұбынВфайлына, жұп нөмiрлi жазулары жұбынСфайлына сақталынады. НəтижедеАфайлының төрт жазуы реттелiп орналасады (11. 2-сурет) .

В файлы:

В

8

23

33

44

8 23 5 65 33 44 1 6 С файлы:

5

65

1

6

С А файлы:

5

8

23

65

1

6

33

44

-сурет. АфайлынВ, Сфайлдарына екінші рет бөліктеу жəнеА

файлына қайта біріктіру.

3-қадам. Өлшемдерi п/2 болатын В, С файлдарының элементтерi реттелiп орналасады. Бiрiктiру арқылы толық реттелген А файлы құрылады (11. 3-сурет) .

В файлы:

5

8

23

65

С файлы:

5

8

23

65

1

6

33

44

1

6

33

44

А файлы:

С

1

5

6

8

23

33

44

65

-сурет. АфайлынВ, Сфайлдарына үшінші рет бөліктеу жəнеА

файлына қайта біріктіру.

Сонымен сыртқы сұрыптаудың тiкелей бiрiгу əдiсiнде компьютер жадында қосымша В, С файлдары құрылып, сақталынады. А, В жəне С файлдарының əрқайсысы О(logn) рет оқылып, сонша рет сақталынады.

7. Табиғи бiрiгу əдiсi

Тiкелей бiрiгу əдiсiнде бастапқы файлдардың алдын-ала сұрыптаулы бөлiгi ескерiлмейдi.

... жалғасы

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