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

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

Қ.Жұбанов атындағы Ақтөбе өңірлік университеті.
Техникалық факультеті.
"Мұнай-газ ісі" кафедрасы.

РЕФЕРАТ

Пән:Бағдарламалау және алгоритмдеу негіздері.
Тақырыбы: Массивтерді сұрыптау әдістері.

Орындаған: Утебаев Марлен
Тобы: АжБк-202
Тексерген:

Ақтөбе 2023

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

Бағдарламаларды параллелизациялау - бұл параллель архитектуралық есептеу жүйесінде (соңғы уақытта, әдетте, көп процессорлы есептеу жүйесінде) тиімді орындалуы үшін бағдарламалар түрінде жазылған алгоритмдерді бейімдеу процесі. Ол бағдарламаларды параллелизмді сипаттайтын және мақсатты компьютерлік жүйенің аудармашыларына түсінікті арнайы тілге қайта жазудан немесе арнайы белгілеулерді енгізуден (мысалы, MPI немесе OpenMP нұсқауларынан) тұрады [1].
Параллельдеу қолмен, автоматтандырылған немесе жартылай автоматтандырылған болуы мүмкін. Оның сапасының тиімділігін бағалау үшін келесі критерийлер қолданылады:
- жеделдету - идеалды жағдайда (параллелизмді ұйымдастыру үшін үстеме шығынсыз) процессорлар санына тең;
- load - пайдаланылатын процессорлардың үлесін көрсетеді. Ең дұрысы 1 немесе 100% тең.
Параллельдеу кезінде алгоритм құрылымының формальды параллелизмін ғана емес, сонымен қатар параллельді компьютерлерде алмасу операцияларының, әдетте, арифметикалық операцияларға қарағанда әлдеқайда баяу жүретінін ескеру қажет. Бұл параллелизмді ұйымдастыруға арналған үстеме шығындардың басым бөлігінің болуына байланысты.
Параллелизацияның тиімділігі ең алдымен есептеу алгоритмін ұйымдастыруға және жүйелі және параллельді программа блоктарының арақатынасына байланысты [2].
Компьютер архитектурасының екі түрлі түрі параллельді есептеулерді ұйымдастырудың кем дегенде екі түрлі әдісін ұсынады:
- векторизация;
- параллелизация.
Векторизация - деректерді параллелизациялаудың бір түрі, яғни. бір параллель нұсқау әртүрлі деректер ағындарына әсер етеді. Жалпы жағдайда параллелдеу кеңірек мүмкіндіктер береді: деректер бойынша параллелизациямен қатар процестер бойынша параллельдеу мүмкін - әртүрлі командалық ағындардың басқаруымен әртүрлі деректер ағындары есептеу процесіне қатысады.
Векторизацияға жататын циклдерге қойылатын қажетті талаптар:
- цикл ең ішкі болуы керек;
- цикл денесінің ішінде тармақталуға жол берілмейді;
- цикл денесінен сыртқы функциялар мен процедураларды шақыруға рұқсат етілмейді;
- цикл денесінде векторлар немесе массивтер элементтерінің рекурсиясы болмауы керек.
Параллелдеу деректер бойынша да, процестер арасында да мүмкін. Сонымен қатар, екі жағдайда да параллельдеу үшін бірдей бағдарламалық құралдарды пайдалануға болады.
Параллельдеу әдістерін келесідей бөлуге болады:
- оптимизациялаушы компилятордың директивалары;
- тілдің параллелизация мүмкіндіктерін кеңейтетін арнайы директивалар;
- параллельді программалау тілдері;
- байланыс құралдары, процессор интерфейсі құралдары.
1.1 Программалауда массивтерді сұрыптау

Сұрыптау қазіргі деректерді өңдеудегі ең кең таралған процестердің бірі болып табылады. Деректерді сұрыптау тапсырмалары компьютерлерде өте кең таралған. Бұл, негізінен, сұрыпталмаған деректерге қарағанда сұрыпталған деректерді түсіну оңайырақ болатындығына байланысты.
Сұрыптау алгоритмі - тізімдегі элементтерді ретке келтіру процедурасы. Әдетте біз жазбаларды (кез келген мәліметтерді қамтитын) кілттер бойынша сұрыптау туралы айтамыз - реттілік қатынасына мүмкіндік беретін осы жазбалардың фрагменттері [3].
Сұрыптау әдісін ақылға қонымды таңдау үшін біз алгоритмдер бағаланатын параметрлерді қарастырамыз.
Сұрыптау уақыты алгоритмнің өнімділігін сипаттайтын негізгі параметр болып табылады. Есептеу күрделілігі деп те аталады.
Жад - бірқатар алгоритмдер мәліметтерді уақытша сақтау үшін қосымша жадты бөлуді талап етеді. Пайдаланылатын жадты бағалау кезінде бастапқы массив алатын кеңістік және енгізу ретіне тәуелсіз шығындар, мысалы, бағдарлама кодын сақтауға арналған шығындар ескерілмейді.
Тұрақтылық - тұрақты сұрыптау тең элементтердің салыстырмалы орнын өзгертпейді. Бұл сипат өте пайдалы болуы мүмкін, егер олар бірнеше өрістерден тұрса және олардың біреуі бойынша сұрыптау орын алса.
Мінез-құлықтың табиғилығы - сұрыпталған немесе жартылай сұрыпталған деректерді өңдеу кезіндегі әдістің тиімділігі. Алгоритм енгізу тізбегінің осы сипаттамасын ескерсе және жақсырақ жұмыс істесе, өзін табиғи түрде әрекет етеді.
Алгоритмнің тағы бір маңызды қасиеті - оның қолданылу аясы. Сұрыптаудың екі негізгі түрі бар:
1) Ішкі сұрыптау кез келген ұяшыққа кездейсоқ қол жеткізумен жедел жадқа толығымен сәйкес келетін массивтермен жұмыс істейді. Деректер әдетте бір жерде, қосымша шығындарсыз сұрыпталады.
2) Сыртқы сұрыптау үлкен сақтау құрылғыларымен жұмыс істейді, бірақ қол жеткізу кездейсоқ емес, дәйекті (файлдарды сұрыптау), яғни қазіргі уақытта біз тек бір элементті көреміз және жадымен салыстырғанда кері орау шығындары негізсіз жоғары. Бұл алгоритмге кейбір қосымша шектеулер қояды және әдетте қосымша дискілік кеңістікті пайдаланатын арнайы сұрыптау әдістеріне әкеледі. Сонымен қатар, медиадағы деректерге қол жеткізу ЖЖҚ-мен операцияларға қарағанда әлдеқайда баяу.
Сұрыптаудың көптеген әдістері бар, олардың әрқайсысының өзіндік артықшылықтары мен кемшіліктері бар. 1.1.1 Жылдам сұрыптау

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

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