Программалауда массивтерді сұрыптау

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

Қ. Жұбанов атындағы Ақтөбе өңірлік университеті.

Техникалық факультеті.

“Мұнай-газ ісі” кафедрасы.

РЕФЕРАТ

Пән:Бағдарламалау және алгоритмдеу негіздері.

Тақырыбы: Массивтерді сұрыптау әдістері.

Орындаған: Утебаев Марлен

Тобы: АжБк-202

Тексерген:

Ақтөбе 2023

Массивтерді сұрыптау әдістері.

Қазіргі уақытта жаңа ақпараттық технологиялар тек мамандандырылған ғана емес, өмірдің күнделікті салаларында да маңызды орын алады. Компьютерлер бизнесте, менеджментте, саудада, құқықта және адам қызметінің көптеген басқа салаларында қолданылады.

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

Бағдарламалық қамтамасыз етуді әзірлеу - бағдарламалау деп аталатын ғылым саласы. Соңғы кездері оның маңыздылығы арта түсті, өйткені компьютер күн сайын қажет, біздің өміріміздің күнделікті құбылысына айналады. Өйткені, өткен жылдардағы компьютерлік технология толығымен дерлік таусылды және адамзат алдында пайда болған қажеттіліктерді қанағаттандырмайды.

Осылайша, жаңа ақпараттық технологиялар біздің заманымызда өте өзекті және кейінгі даму мен жетілдіру үшін көбірек назар аударуды қажет етеді. Сонымен қатар бағдарламалаудың да маңызы зор. Бұл технология бірқатар маңызды ішкі тапсырмаларды қамтиды. Бағдарламалаудың маңызды мәселелерінің бірі сұрыптау мәселесі болып табылады. Сұрыптау алгоритмі - тізімдегі элементтерді ретке келтіру алгоритмі. Тізім элементінде бірнеше өрістер болса, реттілік шарты ретінде қызмет ететін өріс сұрыптау кілті деп аталады. Іс жүзінде сан жиі кілт ретінде пайдаланылады, ал қалған өрістерде алгоритмнің жұмысына ешқандай әсер етпейтін кейбір деректер сақталады. Сол курстық жұмыста массивтерді сұрыптауды параллельдеу технологиясы талқыланады.

Программаны параллелизациялау технологиясының принциптері

Бағдарламаларды параллелизациялау - бұл параллель архитектуралық есептеу жүйесінде (соңғы уақытта, әдетте, көп процессорлы есептеу жүйесінде) тиімді орындалуы үшін бағдарламалар түрінде жазылған алгоритмдерді бейімдеу процесі. Ол бағдарламаларды параллелизмді сипаттайтын және мақсатты компьютерлік жүйенің аудармашыларына түсінікті арнайы тілге қайта жазудан немесе арнайы белгілеулерді енгізуден (мысалы, MPI немесе OpenMP нұсқауларынан) тұрады [1] .

Параллельдеу қолмен, автоматтандырылған немесе жартылай автоматтандырылған болуы мүмкін. Оның сапасының тиімділігін бағалау үшін келесі критерийлер қолданылады:

- жеделдету - идеалды жағдайда (параллелизмді ұйымдастыру үшін үстеме шығынсыз) процессорлар санына тең;

- load - пайдаланылатын процессорлардың үлесін көрсетеді. Ең дұрысы 1 немесе 100% тең.

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

Параллелизацияның тиімділігі ең алдымен есептеу алгоритмін ұйымдастыруға және жүйелі және параллельді программа блоктарының арақатынасына байланысты [2] .

Компьютер архитектурасының екі түрлі түрі параллельді есептеулерді ұйымдастырудың кем дегенде екі түрлі әдісін ұсынады:

- векторизация;

- параллелизация.

Векторизация - деректерді параллелизациялаудың бір түрі, яғни. бір параллель нұсқау әртүрлі деректер ағындарына әсер етеді. Жалпы жағдайда параллелдеу кеңірек мүмкіндіктер береді: деректер бойынша параллелизациямен қатар процестер бойынша параллельдеу мүмкін - әртүрлі командалық ағындардың басқаруымен әртүрлі деректер ағындары есептеу процесіне қатысады.

Векторизацияға жататын циклдерге қойылатын қажетті талаптар:

- цикл ең ішкі болуы керек;

- цикл денесінің ішінде тармақталуға жол берілмейді;

- цикл денесінен сыртқы функциялар мен процедураларды шақыруға рұқсат етілмейді;

- цикл денесінде векторлар немесе массивтер элементтерінің рекурсиясы болмауы керек.

Параллелдеу деректер бойынша да, процестер арасында да мүмкін. Сонымен қатар, екі жағдайда да параллельдеу үшін бірдей бағдарламалық құралдарды пайдалануға болады.

Параллельдеу әдістерін келесідей бөлуге болады:

- оптимизациялаушы компилятордың директивалары;

- тілдің параллелизация мүмкіндіктерін кеңейтетін арнайы директивалар;

- параллельді программалау тілдері;

- байланыс құралдары, процессор интерфейсі құралдары.

1. 1 Программалауда массивтерді сұрыптау

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

Сұрыптау алгоритмі - тізімдегі элементтерді ретке келтіру процедурасы. Әдетте біз жазбаларды (кез келген мәліметтерді қамтитын) кілттер бойынша сұрыптау туралы айтамыз - реттілік қатынасына мүмкіндік беретін осы жазбалардың фрагменттері [3] .

Сұрыптау әдісін ақылға қонымды таңдау үшін біз алгоритмдер бағаланатын параметрлерді қарастырамыз.

Сұрыптау уақыты алгоритмнің өнімділігін сипаттайтын негізгі параметр болып табылады. Есептеу күрделілігі деп те аталады.

Жад - бірқатар алгоритмдер мәліметтерді уақытша сақтау үшін қосымша жадты бөлуді талап етеді. Пайдаланылатын жадты бағалау кезінде бастапқы массив алатын кеңістік және енгізу ретіне тәуелсіз шығындар, мысалы, бағдарлама кодын сақтауға арналған шығындар ескерілмейді.

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

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

Алгоритмнің тағы бір маңызды қасиеті - оның қолданылу аясы. Сұрыптаудың екі негізгі түрі бар:

1) Ішкі сұрыптау кез келген ұяшыққа кездейсоқ қол жеткізумен жедел жадқа толығымен сәйкес келетін массивтермен жұмыс істейді. Деректер әдетте бір жерде, қосымша шығындарсыз сұрыпталады.

2) Сыртқы сұрыптау үлкен сақтау құрылғыларымен жұмыс істейді, бірақ қол жеткізу кездейсоқ емес, дәйекті (файлдарды сұрыптау), яғни қазіргі уақытта біз тек бір элементті «көреміз» және жадымен салыстырғанда кері орау шығындары негізсіз жоғары. Бұл алгоритмге кейбір қосымша шектеулер қояды және әдетте қосымша дискілік кеңістікті пайдаланатын арнайы сұрыптау әдістеріне әкеледі. Сонымен қатар, медиадағы деректерге қол жеткізу ЖЖҚ-мен операцияларға қарағанда әлдеқайда баяу.

Сұрыптаудың көптеген әдістері бар, олардың әрқайсысының өзіндік артықшылықтары мен кемшіліктері бар. 1. 1. 1 Жылдам сұрыптау

QuickSort - бұл тікелей алмасуды сұрыптау алгоритмінің айтарлықтай жақсартылған нұсқасы (оның нұсқалары көпіршікті сұрыптау және шайқаушы сұрыптау деп аталады), ол басқа нәрселермен қатар өзінің төмен тиімділігімен танымал. Негізгі айырмашылық мынада: алдымен ауыстырулар ең үлкен қашықтықта жасалады және әрбір өтуден кейін элементтер екі тәуелсіз топқа бөлінеді. Қызықты факт: ең тиімсіз тікелей сұрыптау әдісін жетілдіру ең тиімді жақсартылған әдістердің біріне әкелді[4] .

Алгоритмнің жалпы идеясы келесідей:

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

- барлық басқа элементтерді сілтеме элементімен салыстырыңыз және массивті бір-бірінен кейінгі үш үзіліссіз сегментке бөлу үшін оларды массивте қайта реттеңіз: «анықтамадан кіші», «тең және үлкен».

- «кіші» және «үлкен» мәндердің сегменттері үшін сегменттің ұзындығы біреуден үлкен болса, бірдей әрекеттер тізбегін рекурсивті түрде орындаңыз.

Іс жүзінде массив әдетте үшке емес, екі бөлікке бөлінеді: мысалы, «анықтамадан кіші» және «тең және үлкен». Бұл тәсіл әдетте тиімдірек, өйткені ол бөлу алгоритмін жеңілдетеді.

Хоар бұл әдісті машиналық аударма үшін әзірледі. Сөздік магниттік таспада сақталды және өңделген мәтіннің сөздерін сұрыптау олардың аудармаларын кері орамсыз таспаның бір айналымында алуға мүмкіндік берді.

Жылдам сұрыптау - бөлу және жеңу алгоритмі.

Алгоритм үш қадамнан тұрады:

1) Массивтен элементті таңдаңыз. Оны қолдау деп атаймыз.

2) Бөлу: массивтегі элементтерді оның алдына сілтемеден кіші элементтер және одан кейін үлкен немесе тең элементтер орналастырылатындай етіп қайта бөлу.

3) Алғашқы екі қадамды айналмалы элементтің сол және оң жағындағы екі ішкі массивке рекурсивті түрде қолданыңыз. Рекурсия тек бір элементі бар немесе элементтері жоқ массивке қолданылмайды.

Асимптотика: O(n*logn) орташа және ең жақсы жағдайда, O(n2) . Қолдау элементін таңдау сәтсіз болған кезде ең нашар бағалауға қол жеткізіледі.

1. 1. 2 Біріктіру сұрыптау

Біріктіру сұрыптауы - тізімдерді (немесе элементтеріне тек дәйекті түрде қол жеткізуге болатын басқа деректер құрылымдарын, мысалы, ағындар) белгілі бір ретпен реттейтін сұрыптау алгоритмі. Бұл сұрыптау бөлу және жеңу принципін қолданудың жақсы мысалы болып табылады. Біріншіден, тапсырма бірнеше кіші қосалқы тапсырмаларға бөлінеді. Содан кейін бұл мәселелер рекурсивті шақыру арқылы шешіледі немесе олардың өлшемі жеткілікті кішкентай болса тікелей. Соңында олардың шешімдері біріктіріліп, бастапқы есептің шешімі алынады [5] .

Біріктіру сұрыптау алгоритмін қарастырайық. Жиымды екіге бөлейік, бөліктерді рекурсивті сұрыптаймыз, содан кейін біріктіру процедурасын орындаймыз: біз екі көрсеткішті сақтаймыз, біреуі бірінші бөліктің ағымдағы элементіне, екіншісі екінші бөліктің ағымдағы элементіне. Осы екі элементтің ішінен ең азын таңдап, оны жауапқа енгізіңіз және көрсеткішті минимумға сәйкес жылжытыңыз. Біріктіру O(n), жалпы logn деңгейлерінде жұмыс істейді, сондықтан асимптотика O(n*logn) болады. Уақытша массивті алдын ала жасап, оны функцияға аргумент ретінде беру тиімді. Бұл сұрыптау жылдам сияқты рекурсивті, сондықтан элементтердің аз санымен квадратқа ауысуға болады.

1. 1. 3 Shellsort

Қабық сұрыптауы - кірістіру сұрыптасының жетілдірілген нұсқасы болып табылатын сұрыптау алгоритмі. Shell әдісінің идеясы жақын жерде ғана емес, сонымен қатар бір-бірінен белгілі бір қашықтықта орналасқан элементтерді салыстыру болып табылады. Басқаша айтқанда, бұл алдын ала «дөрекі» өтулері бар кірістіру сұрыптауы. Көпіршікті сұрыптауды жақсартудың ұқсас әдісі тарақпен сұрыптау деп аталады [6] .

Shell сұрыптау кезінде бір-бірінен белгілі d қашықтықта орналасқан мәндер алдымен салыстырылады және сұрыпталады. Осыдан кейін процедура d-ның кейбір кішірек мәндері үшін қайталанады және Shell сұрыптауы элементтерді d=1 (яғни, кәдімгі кірістіру сұрыптауы) бойынша ретке келтіру арқылы аяқталады. Белгілі бір жағдайларда Shell сұрыптауының тиімділігі элементтердің орнына «тезірек» түсуімен қамтамасыз етіледі (қарапайым сұрыптау әдістерінде, мысалы, көпіршікті сұрыптау, екі элементтің әрбір қайта реттелуі тізімдегі инверсиялар санын максимумға азайтады) . 1 және Shell сұрыптауымен бұл сан үлкенірек болуы мүмкін ) .

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

- стек жады қажет емес;

... жалғасы

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