Массивті сұрыптауды тармақпен орындайтын бағдарлама

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

Қазақстан Республикасы білім және ғылым министрлігі
Қарағанды мемлекеттік техникалық университеті

АТҚ кафедрасы

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

Пәні: С++ бағдарламалау семинары, курстық жұмыс

Тақырыбы: Хоара әдісін қолдана отырып, массивті сұрыптау.

______________
(баға)

Комиссия мүшелері:

______________Сайлауқызы Ж._
(қолы,Т,Ә,А)
Шодырова Б.Х
(қолы,Т,Ә,А)

Қабылдаған:

Дүйсенбекова С.Д .
(тегі, инициалы)
___________________________
(қолы, уақыты)

Орындаған:

Бидаулет Ж.
(тегі, инициалы)
СИБ 19-3
(тобы)

Қарағанды 2020
Қазақстан Республикасының білім және ғылым министрлігі Қарағанды мемлекеттік техникалық университеті

Факультет ИТ БЕКІТЕМІН
Кафедра АТҚ Кафедра меңг.
(қолы)
20 ж.

КУРСТЫҚ ЖОБАҒА ТАПСЫРМА

С++ бағдарламасы бойынша практикум пәні бойынша СИБ 19-2 тобының студенті Сағилаш Бағлан
Тақырып: Массивті сұрыптауды тармақпен орындайтын бағдарлама
Бастапқы мәліметтер: Массивті сұрыптауды тармақпен орындайтын бағдарламаны жасаңыз. Қарапайым алмасуға (көпіршік) негізделген классикалық іске асырумен қатар, қарапайым кірістіруге негізделген опцияны жасаңыз. Массивті толтыру нұсқалары: кездейсоқ сандар, толығымен сұрыпталған, толығымен кері ретпен сұрыпталған. Әр түрлі сатыларда сұрыптау, массивті әр түрлі толтыру, қарапайым сұрыптаудың әр түрлі нұсқалары бойынша статистикалық бақылау жүргізу. Қадам мәні, массивті толтыру опциялары және қарапайым сұрыптау опциясы пернетақтадан енгізу.

Тапсырма берілді 07 сәуір 2020 ж. Жетекші Дүйсенбекова қолы
Студент Бидаулет .Ж. қолы

Анықтама

Берген жұмыс бойынша онлайн тексеріс

Автор: Бидаулет Ж
Кафедра: АТҚ
Топ нөмірі: СИБ 19-2
Жұмыс түрі: Курстық жұмыс
Пән: С++ бағдарламалау

Пән жетекшісі: Оспанова.А

Кафедра жетекшісі: Коккоз М.М.

Мазмұны:

I. Кіріспе 4
II. Негізгі бөлім 6
Тапсырма сипаттамалары 6
Теориялық бөлім 8
Бағдарламалар 15
Бағдарламалық қамтамасыз ету 23
I. Қорытынды 28
II. Пайдаланылған әдебиеттер тізімі 29

КІРІСПЕ.

Жaлпы бұл курстық жұмыстың негізгі мақсаттарының бірі массивті тиімді тәсілді таңдай отырып сұрыптау болып табылады, сонымен қатар бұл курстық жұмыста массив дегеніміз не?, массивті сұрыптау дегеніміз не?, массивті сұрыптау түрлері осындай мағынадағы сұрақтарға жауап ала-аламыз. Бұл әрекеттердің барлығы С++ программалау тілінде жүзеге асырылады. Жалпы, жұмыстың барысын түсіндіре өтсем: ең алдымен титулды парақ әзірленді, кейін курстық жұмысқа тапсырма алынды, кейінгі бетте жұмыстың мазмұны орналасты, келесі бөлім кіріспе,негізгі бөлім (тармақтары: тапсырма сипаттамалары, теориялық бөлім, программалық қамтамасыз ету, әдістемелік бөлім), қорытынды бөлім, пайдаланылған әдебиеттер тізімі, ең соңғы бөлім бағдарламалар бөлімі. Жалпы бұл бөлімдердің және бөлімдердің ішіндегі бөлімшелердің мазмұнын қысқаша түсіндіре өтсем.
Негізгі бөлім-негізгі бөлімде мен негізгі керек дүниелерді орналастырдым, бірқ программаның кодын және нәтижесін бұл бөлімге кіргізбедім, менің ойымша бұл көрнекіліктің бұзылуына әкеп соғады. Сол себепті бұл бөлімге басқа мәтіндегі негізгі дүниелерді енгізуді жөн санадым. Жалпы негізгі бөлімге:
тапсырма сипаттамалары,
теориялық бөлім,
бағдарламалық қамтамасыз ету,
әдістемелік бөлім-атты кішкентай мазмұнды бөлімшелерді кіргізуді жөн санадым. Осы бөлімшелерге тоқтала кетсем.
Тапсырма сипаттамалары бөлімшесінде тапсырманың сипаттамаларын, ерекшеліктерін, қаншалықты маңыздылығын және тапсырманың қаншалықты қиындығын қолымнан келгенше жеткізуге тырыстым.
Ал, одан кейінгі орынға теориялық бөлімшені қойуға бел байладым. Бұл бөлімшеде тапсырманың әр сөзіне тоқталып, толық мағлұмат беріп, программаның қалай жұмыс жасайтынын түсіндірдім.
Келесі бөлімшені бағдарламалық қамтамасыз ету деп атауымның себебі ең соңғы бетте жазылған бағдарлама кодтарының осы бөлімшеде түсіндіру туралы жазғанымнан. Жалпы бұл жерде түзілген бағдарлама кодтарын егжей-тегжейлі түсіндіріп, оны оқыған адамға жеңіл болуы үшін қолымнан келге дүниені жасадым. Әдістемелік бөлімшеде менің тапсырмам бойынша жасалып шыққан программаның орындалу маңыздылығы, қолдану маңыздылығы, неге
керектігі, басқа жолмен жасалған программадан қандай артықшылықтары бары жайлы толықтай түсіндіріп өттім деп ойлаймын.
Қорытынды бөлім жайлы айтар болсам, бұл бөлімде мен жасаған осы курстық жұмыстан мен қандай білім ала-алдым, алға қойылған нәтижеге жеттімбе, жетсем қаншалықты дәрежеде, қандай жаңа білімдер арттырдым, және өз білімімді қай жағынан жаңғырттым деген сұрақтарға толықтай жауап
бердім.
Бұл курстық жұмыс әдеби жағынан осалдау болмау үшінде, ғылыми-көркем еңбек болу үшін тырысып бақтым, жәнеде келесі бөлімді пайдаланылған әдебиеттер тізімі болуын қаладым. Осы бөлімнің арқасында мен бұл курстық жұмысым әйгілі ғалымдардың еңбектеріне негізделген көркем ғылыми еңбек болып шыға келді. Осы себепті бұл бөлімде өзім қолданған ғылыми көркем еңбектер тізімдерін көрсетуді жөн көрдім.
Негізі осы бөлімдермен барлығын аяқтағым келген бірақ, ең соңына мен өзімнің тапсырмама сәйкес жазылған, құрылған бағдарламамның кодын (листинг программы) орналастыруды жөн көрдім. Және бұл бөлімді Бағдарламалар деп атадым. Бұлай атауымның себебі менің тапсырмама сәйкес жазылған код, яғни бағдарлама жазылғандықтан. Бұл бөлімде бағдарлама кодынан басқа ешнәрсе жазбадым тек қана оның қасына шыарылған нәтижелерді орналастырдым және осымен менің бөлімдерім мен бөлімшелерім аяқталды.
Сонымен Кіріспе бөліміндегі жазғаным осы курстық жұмыстың қысқаша мазмұны болды, және сіздерге түсінікті болды деп ойлаймын. Келесі бөлімге көшсек

НЕГІЗГІ БӨЛІМ.
1.1. Тапсырма сипаттамалары.
Маған берілген тапсырма: Массивті сұрыптауды тармақпен орындайтын бағдарламаны жасаңыз. Қарапайым алмасуға (көпіршік) негізделген классикалық іске асырумен қатар, қарапайым кірістіруге негізделген опцияны жасаңыз. Массивті толтыру нұсқалары: кездейсоқ сандар, толығымен сұрыпталған, толығымен кері ретпен сұрыпталған. Әр түрлі сатыларда сұрыптау, массивті әр түрлі толтыру, қарапайым сұрыптаудың әр түрлі нұсқалары бойынша статистикалық бақылау жүргізу. Қадам мәні, массивті толтыру опциялары және қарапайым сұрыптау опциясы пернетақтадан енгізу.
Жалпы тапсырманы өзім түсінгенімдей сипаттап өтсем. Тапсырмада 3 түрлі жолмен массивті сұрыптау керек, және 3 түрлі жолмен массивті толтыру керек. Бұлар жасалды, яғни массивті толығымен сұрыптадым, толығымен кері ретпенн сұрыптадым, қарапайым сұрыптауларды жасадым, және массивті 3 түрлі жолмен, яғни атап өтсем, кездейсоқ сандар арқылы, сұрыпталған ретпен, толық кері сұрыпталған ретпен толтырылды. Сонымен қатар сандардың ұзындығы, толтырылу түрлері, сұрыпталу түрлері, яғни қарапайым сұрыптау опциясы пернетақтадан енгізілді. Тапсырма бойынша оларға статистикалық бақылау жүргізілді, яғни қанша уақытта орындалатыны көрсетілді. Осы тапсырма бойынша барлық келтірілген функциялар қолданылды, яғни тапсырма бойынша барлық дүниелер орындалды деп айта аламын.
Мен осы тапсырмаға сәйкес массивті 3 түрлі жолмен сұрыптауым керек болды. Олар:
толығымен сұрыпталған,
толығымен кері ретпен сұрыпталған,
қарапайым сұрыптаулар, болды. Бұл сұрыптауларға төменде теориялық бөлімде тоқтала кетемін. Және бұл тапсырмада массивті 3 түрлі жолмен толтыру керек болды, яғни бұл тапсырманы орындағанда функциялар қолдануға тура келді. Ал өздеріңіз білетіндей функция тақырыбы С++ тіліндегі ең қиын тақырып болғандықтан, маған бұл тапсырманы орындау оңайға соқпады. Тапсырмада қиыншылық туындаған кезеңдерді атап өтсем. Ең алдымен мен тапсырмаға кіріспес бұрын өзім білмейтін терминдермен таныстым. Олар: көпіршікті алмасу, толығымен сұрыптау, толығымен кері ретпен сұрыптау, секілді ұғымдармен таныстым. Осы терминдерді ретімен орындау барысында қиындық туды. Неге? деген сұраққа мен бұл терминдерді бірінші рет естіп, қолданып отырғандықтан деп жауап бергім келеді. Және де бұл қиыншылықтардан өтіп келесі қиындыққа тап болдым, яғни маған статистикалық бақылау жүргізу қиындық тудырды. Әрине, бұл статистикалық бақылауды өзім жасаған бағдарламаларда қолданып көрмеген
едім. Міне, бұл тапсырма маған қаншалықты қиынға соққанын түсіндіңіздер деп ойлаймын. Ендеше, олай болса тапсырманың басқа жолмен жасалғандардан ерекшелігін түсіндіріп кетсем.
Біріншіден. Менің тапсырмам С++ тілінде жасалғандықтан оны компьютердіңде, адамныңда түсінуіне жеңіл болды. Мен ойлаймын осы тапсырма Python, Java Script, Pascal тілдерінде жасалсада болатын еді, бірақ Python-тілі қолданушыға оңайлық тудырғанымен компьютерге аздап қиындық тудырады,ал, Java Script-тілі компьютерге қолайлық болғанымен, қолданушыға аздап қиындық тдурады, Pascal-тілінде мұндай күрделі тапсырмаларды орындау менімше өте қиын.
Екіншіден. Менің тапсырмамның 3 түрде массивті сұрыптауы және 3 түрде массивті толтыру түрлері орын алды, яғни бәрімізге белгілі массивті сұрыптаудың түрлері көп-ақ, бірақ соның ішіндегі ең танымалдары менің тапсырмамда болғандықтан олардың арасында өзара статистикалық бақылау жүргізе алдым. Және бұл статистикалық бақылауымда айтарлықтай нәтижеге қол жеткіздім, яғни бағдарламада 1 сұрыпталу түрін көрсетсем бағдарламаның орындалу уақыты ұзағырақ болады, ал 2 сұрыпталу түрін көрсетсем оны орындау компьютерге қиынға соқпайтынына көзім жетті.
Үшіншіден. Менің тапсырмама сәйкес массивті сұрыптаудыңда, оны толтырудыңда түрлерін пернетақтадан енгізуге мүмкіндік алдым, яғни бұл дегеніміз қай жолмен жасауды қолданушының еркіне тапсырылды деген сөз. Әрине, бұл ерекшеліктер мен сияқты жас, бастаушы бағдарламаушыларға өте үлкен жетістік деп санаймын. Менің тапсырмам несімен ерекше екенін көресете алсам, келесі пунктке көшейік.
Бұл пункт мен үшін бұл тапсырманың маңыздылығы қаншалықты деп аталады. Мен үшін бұл тапсырманың маңыздылығы өте зор, яғни бұл тапсырманы орындауда мен аитарлықтай жетістіктерге қол жеткізіп, өз білімімді толықтырған жерлерім көп болды, мен үшін бұл тапсырма оңай көрінгенімен, орындау барысында қиын екендігін түсініп, білімімді толықтырған жерлерім өте көп болды. Бұл тапсырманың маңыздылығы мен сияқты бағдарламалауды үйренуді енді бастағандарға үлкен, сонымен қатар сұрыптау тақырыбында ізденіп жүрген тұлғаларға да тигізер пайдасының үлесі зор, яғни мен бұл тапсырмада жоғарыда айтқанымдай статисткалық бақылаулар жүргізіп қайсы түрі жеңіл, қолданушығада өз кезегінде компьютерге де оңай келетін түрлерін анықтадым. Осымен бұл тапсырманың мен үшін қаншалықты маңыздылығын, мен үшін ғана емес тіпті басқа бағдарламалаушыларға қаншалықты маңызды екенін түсінген боларсыздар.
1.2.Теориялық бөлім.
.
Бұл бөлімде тапсырмадағы барлық терминдерге түсініктеме беріп өтсем. Ең алдымен массив дегеніміз не? Массивтер деп жалпы атау бойынша жүгінуге болатын біртипті мәліметтер жиынын айтады. Массивтер статикалық және динамикалық болады. Статикалық массивтерде жады бағдарлама компиляциясы кезінде бөлінеді. Динамикалық массивтер үшін жады бағдарламаны орындау үрдісінде бөлінеді. Бір массивке жататын айнымалылар осы массив элементтері деп аталады. Массив элементін бір мәнді идентификациялау үшін массив атауы мен массивтегі элемент позициясын (орналасуын) білу керек. Массивтегі элементтер позициясы бүтін санды индекстер көмегімен анықталады. Бір өлшемді массив - бұл элементтер идентификациясы бір индекс көмегімен жүзеге асатын массив.
Бір өлшемді массивті хабарлау үшін массив элементтеріне жататын тип пен массив атауын, сонымен қатар массивке кіретін элементтер санын білу керек. Бір өлшемді массивті хабарлау синтаксисі келесідей: тип массивтің аты[өлшемі]; алдымен массив элементтерінің типі көрсетіледі. Массив үшін тип идентификаторынан кейін бос тік жақшалар қойылады. Кейін массив атауы, тағайындау операторы,new жадының динамикалық бөліну нұсқаулығы, тағы да массив элементтерінің типі жүреді және тік жақшада массив өлшемі . Мысалы, int nums=new int[20] командасы 20 элементтен тұратын nums бүтінсанды массивін хабарлайды.
Басқаша айтқанда, мұнда көрсетілген массивті хабарлау командасы екі команда симбиозы болып табылады: int[] командасы nums айнымалысын хабарлау және массивке жады бөлу nums=new int[20] командасы және осы массивке nums айнымаласын тағайындау сілтемесі. Массивті хабарлау үрдісін екі командамен орындауға болады:int[] nums; nums=new
Тік жақшаларды массив типінің атауынан кейін немесе массив атауынан кейін көрсетуге болады. Мысалы, int[] nums командасының орнына int nums[] командасын қолдануға болады. Бір өлшемді массив элементіне жүгіну тік жақшаларда элемент индексін көрсетумен массив атауы арқылы жүзеге асады. Массив элементтерінің индексациясы нөлден басталады. Осылайша, nums массивінің бірінші элементіне сілтеме nums[0] түрінде болады. Егер массивте 20 элемент болса, онда массивтің соңғы эле-менті 19 индексіне ие болады, яғни nums[19].
Массив ұзындығын length қасиеті көмегімен көрсетуге болады. Бұл массивті хабарлау кезінде пайда болатын айнымалы және оның мәні массив элементтерінің саны болып табылады. Әрбір массив үшін жеке length
айнымалысы құрылатындықтан, мұндай айнымалыларға жүгіну массив атауын біруақытта көрсетумен жүзеге асады. Атап айтсақ, алдымен массив
атауы көрсетіледі, кейін нүкте арқылы length айнымалысының атауы ілеседі. Мысалы, бағдарламада nums массивінің ұзындық мәнін білу үшін nums.length нұсқаулығын қолдануға болады. Массивтің соңғы элементіне сілтеме nums[nums.length-1] ретінде жазылуы мүмкін, себебі соңғы элемент индексі массив ұзындығынан бірге кем.
Массивті хабарлау кезінде оған жады бөлінеді. C++тілінде массив элементтері нөлдік мәндермен автоматты түрде іске қосылады - белгіленген ұяшықтар нөлге келеді, ал бұл ұяшықтар мәні массив типіне байланысты интерпретацияланады. Дегенмен мұндай автоматты іске қосуға сеніп керек емес. Массив элементтерін айқын түрде іске қосу дұрыс. Бұл үшін цикл нұсқаулығын қолданады немесе массив хабарлау кезінде элементтер мәнінің тізімін береді.
Массивтің мәндер тізімімен іске келуі кезінде массив айнымалысын хабарлағаннан соң одан кейін (тағайнднау операторы арқылы) тік жақшаға жабылған мәндер тізімі көрсетіледі. Мысалы:
int[] data={3,8,1,7};
Егер тік жақшада массив өлшемі көрсетілмесе, ол мәндер тізіміндегі элементтер санына сәйкес автоматты түрде анықталады. Берілген жағдайда data[0]=3, data[1]=8, data[2]=1 және data[3]=7 мәндерімен төрт элементтен тұратын data бүтін санды массиві құрылады. Келесі командаларды қолданумен тура сол нәтижеге жетуге болады:
int[] data;
data=new int[]{3,8,1,7};
int[] data бірінші командасымен массив айнымалысы хабарланады. new int[]{3,8,1,7} командасмыен төрт бүтін саннан тұратын массив құрылады, ал бұл массивке сілтеме data айнымалысының мәні ретінде data=new int[] {3,8,1,7} командасымен тағайындалады.
С++ тілінде массивтер бірліктен артық өлшемдікке ие болуы мүмкін. Бірақ тәжірибеде екіден жоғары өлшемдік массивтері сирек қолданылады. алдымен екі өлшемді массивтердің хабарлану әдістерін, іске қосылуын және қолданылуын қарастырамыз.
С++ тілінде екі өлшемді массив техникалық көзқарас тұрғысынан бір өлшемді массив болып табылады, оның элементтері де бір өлшемді. Бірінші қарағанла елеусіз жағдай екі өлшемді массив секілді осындай құрылымдарды қолдануда ерекше ыңғайлыққа әкеледі.
Сұрыптау- массив элементтерін белгілі бір заңдылықпен орындарын
ауыстырып реттеу процессін айтамыз. Мысалы, сандар массивін өсуі, кемуі
бойынша сұрыптау, жолдар массивін алфавит бойынша сұрыптау және тағы басқа. Сұрыптау мақсаты - көптеген сұрыпталған обьектінің ішінен белгілі бір элементті іздеуді оңайлату. Ақпараттық жүйелерде мәліметтерді сұрыптаудың маңызы өте зор.
Сұрыптаудың негізгі түріне тоқатала кетейік:
1. Ауыстырмалы сұрыптау (көпіршік әдісі)
Алгоритм 1-ші мен 2-ші элементтерді салыстырудан басталады. Егер 2-ші элемент 1-шіден кіші болса, онда оларды орындарымен алмастырылады. Бұл процесс қатар тұрған әр жұп элементтері үшін қайталанады, процесс бүкіл N элементтері өңделмейінше қайталанады. Массивтің бір өтімінен кейін ең үлкен элемент ең артқы (N-ші) орынға тұрғызылады. Алгоритм жалғаса береді, сонда p-ші өтім кезінде алғаш (N-p) элементтері оң жақтағы көрші элементтерімен салыстырылады. Егер келесі бір өтімде алмастырулар болмаса, алгоритм өз жұмысын тоқтатады. Соңында ең жеңіл элементтер алгоритм орындалуы барысында біртіндеп қалқып шығады.
Бұл әдістің ерекшелігі - әр элементті массивтің басқа элементетрімен салыстырып шығу емес, көрші екі элементпен салыстыру. Көпіршікті сұрыптаудың кемімелі алгоритмінің мәні мынада: М массивін біртіндеп төменнен жоғары қарай қарап шығу. Егер көрші элементтері шарт орындалатындай, онда осы элементтердің мәндері ауысады.
Массивті инициализациялаудың бір тәсілі элементтерді кездейсоқ сандар арқылы анықтау болып табылады. Кездейсоқ сандармен жұмыс жасау үшін Random класы қолданылады. Random.Next әдісі нөлден бастап int типінің ең үлкен мәніне дейінгі аралықта кездейсоқ санды құрады. Нөлден бастап қандай да бір басқа оң санға дейінгі аралықта кездейсоқ санды құру үшін Random.Next() әдісінің жүктемесі қолданылады. Бұл әдістің жалғыз параметрі аралықтың жоғарғы шегін көрсетеді, ал шектің өзі аралыққа кірістірілмейді. Басқа аралықтағы кездейсоқ санды құру үшін Random.Next() әдісінің жүктемесі қолданылады, бірінші аргумент аралықтың төменгі, ал екіншісі - жоғарғы шегін береді.
Индекстері арқылы сұрыптау - сұрыптаудың бірден-бір түрі. n элементтен тұратын А сандар массиві берілген. Массивті индекстері (индекстер массивін жасақтау) арқылы элементтерінің өсуі бойынша сұрыптайық.
Өлшемі n болатын А массивін толтыру және экранға шығару;
i:=1;
Индекс i-ден басталатын массив элементтерінің ішінен ең кішісін (индексі j) таңдап алу;
A[i] және A[j] элементтерінің орындарын ауыстыру;
i:=i+1 мәні үшін i:=n болғанға дейін 3 және 4 қадамдарды қайталау;
Сұрыпталған А массивін экранға шығару.
1. Барлық әдістерді статикалық және динамикалық деп қарастыруға болады. Массивтен статикалық әдіспен іздеу кезінде оның мәндері өзгермейді. Массивтен динамикалық әдіспен іздеу кезінде оның өлшемі өзгеруі мүмкін, себебі ол қайтадан сұрыпталады. Біз көбінде статикалық әдісті қолданамыз, ... жалғасы

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