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


Сұрыптау алгоритмдері.
Сұрыптау дегеніміз – жиын объектілерін белгілі бір тәртіппен ауыстырып қою процесі. Сұрыптаудың мақсаты – сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету. Массивтерді сұрыптау әдістеріне қойылатын негізгі талап – жадыны тиімді пайдалану.
Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді, сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау алгоритмдері(файлдарды сұрыптау). Сандық емес алгоритмдер үшін жазбалар массивтерін сұрыптау тән.
Кілттік өріс – сызықтық тәртіптегі қатынаспен анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі орнықты деп аталады.
Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив. Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау).
Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,…, ai-1 және кіретін тізбекке ai,…, an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді.
Таңдаумен сұрыптау – ең кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады.
Алмасумен сұрыптау – барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.
Қарапайым таңдаумен сұрыптау әдісі қарапайым әдістердің ішіндегі ең жақсысы, алмасумен сұрыптау – ең жаманы, ал жылдам сұрыптау ең тезі және ең жақсысы болып табылады.
Сыртқы сұрыптау алгоритмдері – бұл сыртқы жадтағы мәліметтерді сұрыптау алгоритмдері, мұнда қолайлы құрылым - файл . Негізгі ерекшелігі - өңдеудіңәрбір уақыт мезетінде тек бір ғана элементі(компонента) жетімді. Файлдардысұрыптауәдістерініңкөпшілігі (доступных в данный момент) тоғыстырупроцедурасынанегізделеді. Тоғыстыру – екі (немесеодан да көп)
Пайдаланылған әдебиеттер:
1. Досмайлов Т. К. «Паскаль программалау тілі», А.,1996.
2. Бурин Е. А. «Программирование на языке Турбо Паскаль», А., 2000.
3. Семашко Г. Л., Салтыков Г. Л. «Программирование на языке Паскаль». М.,1988.

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

бот арқылы тегін алу, ауыстыру

Қандай қате таптыңыз?

Рақмет!






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

СӨЖ

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

Орындаған: Сапенова Ш.
Тобы: Т-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 ... жалғасы
Ұқсас жұмыстар
Информатика пәнінен лекциялық сабақтардың тезистері
Сұрыптау есептері. Сұрыптау алгоритмдері
Сұрыптау есептері. Сұрыптау алгоритмі
Сұрыптау есептері. Таңдау арқылы сұрыптау
Сұрыптау есептері, сұрыптау алгоритмдері туралы ақпарат
Сұрыптау есептері, қою арқылы сұрыптау
Сұрыптау есептері. қою арқылы сұраптау
Мәселе есептерді шешудің моделін жасау
Массивтер жайлы
Ақпараттық жүйенің жіктелуі
Пәндер