“Крест пен ноль” ойыны

МАЗМҰНЫ

1. Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...3

2. Есептің қойылымы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4

3. Теориялық мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..4
3.1 Сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .4
3.2 Сұрыптау тәсілдері ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .4

4. Ішкі сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .5
4.1 Таңдау сұрыптауы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..5
4.1.2 Есептеуішпен берілген сызықтық таңдау ... ... ... ... ... ... ... ... ... ... ... ...6
4.2 Көпіршік тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...7
4.3 Енгізу тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...10
4.3.1 Модификацияланған енгізу тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..11
4 .4 Шелл тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...12
4.5 Бөлу сұрыптауы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...15
4.6 Бірігу тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...15

5. Сыртқы сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...16
5.1 Тура бірігу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .16
5.2 Кәдімгі бірігу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 17

6. Есептің мақсаты ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..18

7. Программаның баяндалуы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 19
7.1 Жалпы мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...19
7.2 Функционалдық қолдануы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 19

8. Программаның алгоритмі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..20

9. Блок.схема

10. Қолданылған техникалық жабдықтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..26

11. Шақырылуы және жүктелуі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 26

12. Қорытынды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .27

13. Әдебиеттер тізімі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .28

КІРІСПЕ
Қазіргі уақытта есептеуіш техника адамзат өміріндегі барлық әрекет өрісіне енді. Көбінесе бұл жағдай – мини әсіресе микро ЭЕМ-нің қарқынды дамуымен түсіндіріледі. Қазір компьютерлерді университет лабораторияларында ғана емес, сонымен бірге мектеп сыныптарында да көруге болады. Біздің уақытта компютерлерге көптеген адамдардың, мамандығы программист болмаса да, қолы жететін мүмкіндіктері пайда болды.
1980 жылдары барлық ойындар және оқытатын программалар MS-DOS операциялық жүйеге арнап жазылған болатын, оның себебі – графикалық редакторлардың әлсіздігі және де жадының жетіспеушілігі. Кейін жаңа WINDOWS операциялық жүйелері пайда болды да, олардың графикалық редакторлары мықты болып, оқытатын программалар барлық ғылыми және техникалық мекемелерде пайда болды, сонымен қатар кішкентай балаларды оқытатын ойын программалары пайда болды.
Қазіргі таңда компьютерлік ойындарды жасау кең орын алып отыр. TGF және The Pie GCS сияқты программаларда ойындарды санаулы сағаттар ішінде жасай алады. Бұл программаларда осындай мүмкіндікті тұрғызатын құралдар өте жоғары деңгейде дамыған. Ол жерде ойын жасап жүрген шеберлер өздерінің барлық мүмкіндіктерін көрсете алады, жас бағдарламаушылар да тез меңгеріп кетеді.

2. Есептің қойылымы

Бұл программаны орындау үшін Паскаль тілінің мүмкіндіктерін қолданамыз. Бұл ойын “Крест пен ноль” деп аталады. Негізінде осы ойынның ешқандай қиындығы жоқ. Ойынды бастаудан бұрын берілген инструкциясын оқыңыз.

Есептің шарты:
Алаңшада компьютер мен ойыншы ойнайды. Баған немесе жол бойынша крест немесе нольді тізіп қойып шыққан ойыншы жеңеді. Және олар бір-біріне солай қойып шығуына бөгет жасай отырып, өз мақсаттарына жету керек.

3. Теориялық мағлұматтар

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

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

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

ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ

1) Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск Москва, Мир,1978
2) Зуев Е.А.
Язык программирования Turbo Pascal 6.0 Москва,Унитех 1992
3) Фаронов В.В. Turbo Pascal 7.0, Москва,Нолидж,1990
4) Гусева А.И. Учимся программировать: Turbo Pascal. Москва, Диалог-Мифи,2000
5) Е.М.Епанешников, В.А.Епанешников
Turbo Pascal 7.0,Москва,Диалог-Мифи,2000

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

Мазмұны

1.
Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ... ... ... ...3

2. Есептің
қойылымы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... 4
3. Теориялық
мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... .4
3.1 Сұрыптау
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... .4
3.2 Сұрыптау
тәсілдері ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ..4
4. Ішкі
сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ..5
4.1 Таңдау
сұрыптауы ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ...5
4.1.2 Есептеуішпен берілген сызықтық
таңдау ... ... ... ... ... ... ... . ... ... ... ... ..6
4.2 Көпіршік
тәсілі ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... .7
4.3 Енгізу
тәсілі ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... .10
4.3.1 Модификацияланған енгізу
тәсілі ... ... ... ... ... ... ... . ... ... ... ... ... ... ... .11
4 .4 Шелл
тәсілі ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... .12
4.5 Бөлу
сұрыптауы ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... 15
4.6 Бірігу
тәсілі ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... .15
5. Сыртқы
сұрыптау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ...16
5.1 Тура
бірігу ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... 16
5.2 Кәдімгі
бірігу ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ..17
6. Есептің
мақсаты ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... .18
7. Программаның
баяндалуы ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... .19
7.1 Жалпы
мағлұматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ..19
7.2 Функционалдық
қолдануы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... 19
8. Программаның
алгоритмі ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ...20
9. Блок-схема
10. Қолданылған техникалық
жабдықтар ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... 26
11. Шақырылуы және
жүктелуі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... 26
12.
Қорытынды ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ...27
13. Әдебиеттер
тізімі ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ...28

Кіріспе
Қазіргі уақытта есептеуіш техника адамзат өміріндегі барлық әрекет
өрісіне енді. Көбінесе бұл жағдай – мини әсіресе микро ЭЕМ-нің қарқынды
дамуымен түсіндіріледі. Қазір компьютерлерді университет лабораторияларында
ғана емес, сонымен бірге мектеп сыныптарында да көруге болады. Біздің
уақытта компютерлерге көптеген адамдардың, мамандығы программист болмаса
да, қолы жететін мүмкіндіктері пайда болды.
1980 жылдары барлық ойындар және оқытатын программалар MS-DOS операциялық
жүйеге арнап жазылған болатын, оның себебі – графикалық редакторлардың
әлсіздігі және де жадының жетіспеушілігі. Кейін жаңа WINDOWS операциялық
жүйелері пайда болды да, олардың графикалық редакторлары мықты болып,
оқытатын программалар барлық ғылыми және техникалық мекемелерде пайда
болды, сонымен қатар кішкентай балаларды оқытатын ойын программалары пайда
болды.
Қазіргі таңда компьютерлік ойындарды жасау кең орын алып отыр. TGF және The
Pie GCS сияқты программаларда ойындарды санаулы сағаттар ішінде жасай
алады. Бұл программаларда осындай мүмкіндікті тұрғызатын құралдар өте
жоғары деңгейде дамыған. Ол жерде ойын жасап жүрген шеберлер өздерінің
барлық мүмкіндіктерін көрсете алады, жас бағдарламаушылар да тез меңгеріп
кетеді.

2. Есептің қойылымы

Бұл программаны орындау үшін Паскаль тілінің мүмкіндіктерін
қолданамыз. Бұл ойын “Крест пен ноль” деп аталады. Негізінде осы ойынның
ешқандай қиындығы жоқ. Ойынды бастаудан бұрын берілген инструкциясын
оқыңыз.

Есептің шарты:
Алаңшада компьютер мен ойыншы ойнайды. Баған немесе жол бойынша крест
немесе нольді тізіп қойып шыққан ойыншы жеңеді. Және олар бір-біріне солай
қойып шығуына бөгет жасай отырып, өз мақсаттарына жету керек.

3. Теориялық мағлұматтар

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

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

4
Сұрыптау - бұл кейбір критерийлері бойынша жазбаны кестелерде нақты бір
тәртіппен реттеу операциясы. Сұрыптау барлық жазбалар кілттерінің
мәндерімен сәйкес іске асады (мыс., алфавит бойынша аттарын реттеу немесе
сандарды өсу бойынша реттеу). Сұрыптаудың көптеген бір – бірінен айрықша
тәсілдері бар. Егер де кесте бүтіндей ЭЕМ – нің жедел жадында орналасса,
онда оның реттелуі ішкі деп аталады. Ал егер де реттелген мәліметтерді
сақтау үшін сыртқы есте сақтау құрылғысы пайдаланса, онда бұндай реттелу
сыртқы деп аталады. Операцияларды салыстырудың орташа саны, сұрыптаудың
тәсілінен байланысты, және де рационалды тәсілді таңдаған кезде
кейбіреулері минимумға жетеді. Ішкі сұрыптау тәсілдерін екі топқа бөлуге
болады:
• Разервтік жадыны қажет ететін тәсілдер
• Резервтік жадыны қажет етпейтін тәсілдер
Бірінші топқа таңдау, енгізу, көпіршік (пузырька), Шелл тәсілдері жатса,
екінші топқа квадраттық таңдау, қосылу тәсілі және т.б. жатады. Қарапайым
сұрыптау тәсілдері (таңдау, енгізу, ауыстыру) шамамен n**2 салыстыруын
талап етеді. Әдетте одан да қиынырақ алгоритмдер орташа n*log2(n)
салыстыруларында нәтиженің берілуін қамтамасыз етеді. Бірақ та кез келген
жағдайларда қолайлы сұрыптау жоқ, себебі олардың тиімділігі кестедегі
кілттердің түріне және олардың алдын ала реттелуіне байланысты. Ішкі
сұрыптаудың ең кең қолданылатын тәсілдерін қарастырайық.

4. Ішкі сұрыптау
4.1 Таңдау сұрыптауы
(тік таңдау, сызықты таңдау)
Осы метод бойынша, кестедегі бірінші жазбадан бастап, ең кішкентай
мәні бар кілттің элементтерін іздеуге болады. Осындай орын-ауыстырудың
нәтижесінде, кілттің ең кішкентай мәні бар жазбаны кестедегі бірінші
позицияға орналасытырады. Одан кейін кестедегі екінші элементтен бастап,
екінші ең кіші мәні бар кілттің ізденуі жүзеге асады. Табылған элемент
кестедегі екінші элементпен орын ауыстырады. Бұл процесс кілттің кодтары
өсу реті бойынша реттелмейінше тоқтамайды. Осы тәсілдегі салыстыру саны n(n-
1)2 –ге тең, мұндағы n – кестедегі жазбалардың саны. Осындай сұрыптау
кезінде орын ауыстырудың ең үлкен саны (n-1) – ге тең. Келесі кілттердің
мәндері бар кесте үшін алгоритмдік қадамдарын мысал ретінде қарастырамыз:

5
23 11 4 56 9 35 7

Берілген кесте әртүрлі кезеңіндегі реттелуін көрсетеді

(орын ауыстыратын элементтердің асты сызылған):
23 11 4 56 9 35 7
4 11 23 56 9 35 7
4 7 23 56 9 35 11
4 7 9 56 23 35 11
4 7 9 11 23 35 56

4.1.2 Есептеуішпен берілген сызықтық таңдау

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

Бастапқы кесте және есептеуіштің массиві:
Индекстер Кілттер Есептеуіштер
0 9 0
1 5 0
2 10 0
3 2 0
Қараулар нәтижесінде массивтің өзгеруін қарастырайық:
1-ші 2-ші 3-ші Нәтижелі кесте (кілттер)
2 2 2 2
0 1 1 5
1 2 3 9
0 0 0 10
6
4.2 Көпіршік тәсілі
Осы тәсілді пайдаланған кезде (n-1) – дің ең үлкен өтулері керек.
Кестенің бірінші өтуі кезінде бірінші және екінші жазбаның К1 және К2
кілттері салыстырылады, егер де олардың арасындағы тәртіп бұзылса, онда
R1және R2 жазбалары орындарын ауыстырады. Содан кейін осы процесс R2 және
R3, R3 және R4 т.с.с. үшін қайталанады. Осы тәсіл аз кілттері бар
жазбаларды қозғалтуға және білінуге мәжбүр етеді. Бірінші өтүден кейін ең
көп мәні бар жазбадағы кілт кестенің n-ші позициясында тұрады. Әрбір
келесі өтулер кезінде ең көп мәндері бар келесі жазбалардағы кілттер n-1,
n-2, ...,2 позицияларында орналасады, нәтижесінде сұрыпталған кесте шығады.
Әрбір өтулерден кейін осы өтулер кезінде ауыстырулар болда ма, жоқ па
деген тексеруді да істеуі мүмкін. Егер де ауыстырулар жоқ болса, онда ол
кесте сұрыпталғаны екені және де одан арғы өтулерді қажет етпейтінін
білдіреді. Сонымен қатар, соңғы ауыстырудың индексін есте сақтауға болады.
Бұл келесі қадамдағы қарайтын қосалқы кестені кішірейтуге мүмкіндік береді.
Көпіршік тәсілімен сұрыптағандағы сипаттамасы ең болмағанда n(n-1)2
салыстыруларын және n(n-1)2 ауыстыруларын құрайды. Салыстырудың және
ауыстырудың орташа саны n**2 рет.
Паскаль тілінде Көпіршік тәсілін іске асыратын процедура төменде
келтірілген:

Type
Rec=Record
f1 : char;
f2 : integer;
f3 : integer
End;
Table = Array[1..100] Of Rec;
procedure bubble(var T:Table;
n:integer);
{ T - кесте; n – оның өлшемі }
{ f3 ауданы бойынша сұрыптау}
var
i:integer;
temp:Rec;
witch:boolean;
begin
repeat

7
switch:=false;
for i:=1 to n-1 do
if T[i].f3T[i+1].f3 then
begin
switch:=true;
temp:=T[i];
T[i]:=T[i+1];
T[i+1]:=temp
end
until not(switch)
end

Бұл тәсіл ауыстыру тәсілімен сұрыптауды пайдаланады. Ол салыстыру
операцияларының циклында орындалуында және көршілес тұрған элементтерін
ауыстыруға қажеттігіне негізделген. Оның аталуы сумен толтырылған
резервуардағы көпіршіктердің қозғалу кезіндегі процесске ұқсас болғандықтан
олай аталды. Әрбір көпіршік өз жиегін табады. Төменде көпіршік тәсілімен
сұрыптаудың ең қарапайым программаның формасы көрсетліген:

{Көпіршік тәсілімен сұрыптаудың басталуы}
procedure Bubble(var item: DataArray; count:integer);
var
i,j: integer;
x: DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1]item[j] then
begin
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
end;
end;
end;
{ Көпіршік тәсілімен сұрыптаудың аяқталуы }

Бұл мысалда берілген item Dataitem элементінің массиві болып табылады.
Ол сұрыпталады да, ал берілген count массивінде элементтердің саны бар.
8
Көпіршік тәсілімен сұрыптаудың екі циклі бар. Массив элементінің саны
count айнымалымен берілгендіктен, сыртқы цикл count массивінің қаралуын !
рет ғана шақырады. Бұл процедура аяқталғаннан кейін әрбір элементтің өз
позициясында тапқанын қамтамасыз етеді. Ішкі цикл салыстыру және ауыстыру
операцияның шындығымен орындалатынына негізделген. Көпіршік тәсілімен
сұрыптаудың осы версиясы символдық массивтегі элементтердің мәндерін өсу
реті бойынша сұрыптай алады. Мысалы, келесі қысқа программа test.dat
дисктік файлынан оқитын жолды сұрыптайды:

program SortDriver;
{бұл программа test.dat дисктік файлынан 80 немесе одан да аз символдарын
сұрыптайды да, нәтижені экранға шығарады }

type
DataItem = char;
DataArray = array [1..80] of char;
var
test: DataArray;
t, t2: integer;
testfile: file of char;
{ Көпіршік тәсілімен сұрыптау}
procedure Bubble(var item: DataArray; count:integer);
var
i,j: integer;
x: DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1]item[j] then
begin
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
end;
end;
end;

9
begin
Assign(testfile, 'test.dat');
Reset(testfile);
t := 1;

{ сұрыптауға кететін символдарды оқу}

while not Eof(testfile) do begin
read(testfile, test[t]);
t := t+1;
end;
t := t-2; {есептелген элементтердің санын дұрыстау }

Bubble(test, t); { массивті сұрыптау}

{ сұрыпталған сиволдық массивтің шығарылуы }
for t2 := 1 to t do write(test[t2]);
WriteLn;
end.
Көпіршік тәсілімен сұрыптауының бір ерекшелігі бар: массивтің соңындағы өз
орнында тұрмаған элемент (мысалы, dcab массивіндегі а элементі) бір өту
арқылы өз орнына жетеді, ал массивтің басында орналасқан элемент (мысалы,
d элементі), өз орнына өте баяу жетеді. Барлық қарауларын бір бағытта
істеу міндетті емес. Оның орнына әрбір келесі қарауын қарама-қарсы бағытта
істеуге болады. Бұл жағдайа өз орнынан қатты алыстап кеткен элементтер тез
арада өз орнына жылжиды.

4.3 Енгізу тәсілі

Бұл тәсіл келесі ереже бойынша жұмыс істейді: R[j] жазбаны
қарастырғанға дейін алдағы R[1], R[2],...,R[j-1] жазбалар да реттелген және
R[j] тиісті орнына енгізіледі. Кестенің сұрыпталуы екінші жазбадан
басталады. Оның кілті бірінші жазбаның кілтімен салысытырылады да, егер де
реттелуі бұзылса, онда R[1] және R[2] жазбалары орындарын ауыстырады.
Одан кейін R[3] жазбаның кілті R[1] және R[2] жазбалардың кілттерімен
салыстырылады. J-ші қадамда K[j] кезекпен K[j-1], K[j-
2],...(K[1]=K[2]=...=K[j-1]) – мен K[j]K[i] (i=j-1,j-2,...)
шарттары орындалғанда ғана немесе қосалқы кестенің (i=1, K[j]K[1])
реттелген сол жағындағы соңы жеткенде ғана салыстырылады.
10
K[j]=K[i] шарты орындалғанда, бұл R[j] жазбаны R[i] және R[i+1] арасына
енгізу керек екенін білдіреді. Онда R[i+1], R[i+2],...,R[j-1] жазбалары бір
позицияға жылжиды да, R[j] жазбасы i+1 позициясына енгізіледі. Салыстыру
және орын-ауыстыру операцияларын қосуға қолайлы. Төменде j-ші қадамның
сұрыпталуы қалай іске асатынын көрсетіледі:

5 8 10 14 6 2 11 ¦ j=5, i=4, 6 14
-~~ ¦
5 8 10 6 14 2 11 ¦ i=3, 6 10
-~~ ¦
5 8 6 10 14 2 11 ¦ i=2, 6 8
-~~ ¦
5 6 8 10 14 2 11 ¦ i=1, 6 5
Енгізу методы үшін салыстыру операциясының саны келесі формула арқылы
есептеледі:
С=

Сұрыпталған кестедегі элементтердің саны көп болған жағдайда, мына
формуланы қолдануға болады:

C=n**24

Осы методты пайдаланғанда орын-ауыстырудың максималды саны n**24 – ге тең.
Енгізу тәсілімен реттелген кестенің ішіне жазбалар енгізгенде көп
қолданылады. Жаңа жазба кестенің ішіне бар реттің ешбір өзгеріссіз
енгізілуі керек.

4.3.1 Модификацияланған енгізу тәсілі (бинарлық кірістіру)
Тура қосу тәсілін жақсарту үшін, кестенің кезекті элементін реттелген
қосалқы кестеге енгізу, оны бинарлық іздеу тәсілінің (дихотамикалық,
екілік, логарифмдік) көмегімен жүзеге асыруға болады.
Сұрыптаудың j-ші қадамы:
5 6 8 10 14 18 9 2 ¦ i = 62 = 3; 9 8
~~~ ~~~~~~ ~~ ¦
тасталынады қарасытырлады ¦
--¬ ¦
. . . 10 14 18 9 2 ¦ i = (4+6)2 = 5;
~~ ~~~~~ ¦ 9 14
тасталынады қарасытырлады ¦
. . . 9 10 14 18 2 ¦ i = 4; 9 10

11

4.4 Шелл тәсілі
Салыстырылатын элементтердің арасындағы ара-қашықтығын азайтатын
принципті қолданып, енгізу сұрыптауын пайдаланатын жалпы тәсіл.1 суретте
abcdef массиві үшін Шелл сұрыптауы көрсетіліп тұр. Біріншіден бір-бірінен
үш позицияға жылжыған барлық элементтер сұрыпталады. Одан соң екі позицияға
жылжыған барлық элементтер сұрыпталады. Ең соңында барлық көрші элементтер
сұрыпталады.

1-сурет. Шелл сұрыптауы

{ Шелл сұрыптауы }
procedure Shell(var item: DataArray; count:integer);
const
t = 5;
var
i, j, k, s, m: integer;
h: array[1..t] of integer;
x: DataItem;
begin
h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
for m := 1 to t do
begin

k:=h[m];
s:=-k;
for i := k+1 to count do
begin
x := item[i];

12
j := i-k;
if s=0 then
begin
s := -k;
s := s+1;
item[s] := x;
end;
while (xitem[j]) and (jcount) do
begin
item[j+k] := item[j];
j := j-k;
end;
item[j+k] := x;
end;
end;
end; { Шелл сұрыптауының соңы }

Бірінші жағынан алгоритмге қарағанда, оның жақсы нәтижені және нәтижесінде
сұрыпталған массив шығатынын айтуға болмайды. Бірақ, ол біріншісін де,
екіншісін де береді. Осы алгоритмнің эффектісі әрбір өту кезінде
элементтердің үлкен емес сандары пайдаланады немесе массивтің элементтері
салыстырмалы тәртіпте тұрғаны, ал реттелуі әрбір мәліметтерді жаңадан
қараған кезде көбеетінімен түсіндіріледі.
Салыстырлатын элементтердің арасындағы ара-қашықтық әртүрлі өзгеруі мүмкін.
Ең соңғы қадам бірге тең екені міндетті болу керек. Мысалы, 9,5,3,2,1
Қадамдарының жүйелілігі жақсы нәтижені береді. Екінші дәрежелі жүйелерінен
құтылу керек, себебі күрделі математикалық есептеулердің нәтижесінде,
сұрыптау алгоритмнің эффектісі төмендейді.
Ішкі циклдің екі тексеру шарты бар. "хitem[j]" шарты, элементтерді реттеу
үшін қажет. "j0" және "j= count" item массивінің шетіне шығуына
кедергі жасайды. Осы қосымша тексеру бір жағынан Шелл сұрыптауын
нашарлатады. Шелл сұрыптаудың жай ғана өзгертілген версиялары сұрыптауға
берілген ақпараттың бөлігі емес болып табылатын басқару ... жалғасы

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