Сұрыптау есептері

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

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ СЕМЕЙ ҚАЛАСЫНЫҢ ШӘКӘРІМ АТЫНДАҒЫ МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ

СӨЖ

Тақырыбы: Сұрыптау есептері.

Орындаған: Сапенова Ш.
Тобы: Т-341
Тексерген:Болсынбекова Ш.Ж.

Семей қаласы,
2015 жыл.
Сұрыптау алгоритмдері.
Сұрыптау дегеніміз - жиын объектілерін белгілі бір тәртіппен ауыстырып қою процесі. Сұрыптаудың мақсаты - сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету. Массивтерді сұрыптау әдістеріне қойылатын негізгі талап - жадыны тиімді пайдалану.
Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді, сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау алгоритмдері(файлдарды сұрыптау). Сандық емес алгоритмдер үшін жазбалар массивтерін сұрыптау тән.
Кілттік өріс - сызықтық тәртіптегі қатынаспен анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі орнықты деп аталады.
Ішкі сұрыптаулар алгоритмдері - бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым - массив. Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап - жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау (көбікше әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау).
Кірулермен сұрыптау - элементтер шартты түрде дайын тізбекке a1,..., ai-1 және кіретін тізбекке ai,..., an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді.
Таңдаумен сұрыптау - ең кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады.
Алмасумен сұрыптау - барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.
Қарапайым таңдаумен сұрыптау әдісі қарапайым әдістердің ішіндегі ең жақсысы, алмасумен сұрыптау - ең жаманы, ал жылдам сұрыптау ең тезі және ең жақсысы болып табылады.
Сыртқы сұрыптау алгоритмдері - бұл сыртқы жадтағы мәліметтерді сұрыптау алгоритмдері, мұнда қолайлы құрылым - файл . Негізгі ерекшелігі - өңдеудің әрбір уақыт мезетінде тек бір ғана элементі(компонента) жетімді. Файлдарды сұрыптау әдістерінің көпшілігі (доступных в данный момент) тоғыстыру процедурасына негізделеді. Тоғыстыру - екі (немесе одан да көп) тізбектерді бір тізбекке біріктіру, ол тізбек элементтері қайталанатын таңдау арқылы реттелген . Қарапайым тоғыстыру келесі қадамдардан тұрады:
1.
a тізбегі b және c екі жартыға бөлінеді;
2.
b және c тізбектері жеке элементтерді реттелген жұптарға біріктіру арқылы тоғыстырылады;
3.
Алынған тізбек a деп аталады, содан кейін 1 және 2 қадамдар қайталанады; бұл жолы реттелген жұптар реттелген төрттіктерге тоғыстырылады;
4.
Алдыңғы қадамдар қайталады; төрттіктер сегіздіктерге тоғыстырылады, барлық үрдіс бүкіл тізбек реттелгенше жалғасады; тоғыстырылатын жарты тізбектер ұзындықтары екі еселеніп отырады.
Табиғи тоғыстыру - бұл әр тоғыстыруда мүмкін ең ұзын ішкі тізбектер біріктірілетін тоғыстыру.
Бүгінгі таңда сұрыптаудың көптеген тәсілдері белгілі. Олар:
Таңдау арқылы сұрыптау - бұл сұрыптаудың ең қолайлы түрі. Әдетте бұл әдіс кестені реттеуді қажет еткен адам ойына ең бірінші келеді. Бұның мәні мынада, мысалы n элементтен тұратын А сандар массиві берілген. Оны таңдау әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет. Алгоритмі:
1. Өлшемі n болатын А массивін толтыру және экранға шығару;
2. i:=1;
3. Индекс i-ден басталатын массив элементтерінің ішінен ең кішісін (индексі j) таңдап алу;
4. A[i] және A[j] элементтерінің орындарын ауыстыру;
5. i:=i+1 ... жалғасы

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