Сұрыптау есептері. қою арқылы сұраптау

Кіріспе
Қолданылған әдебиеттер

Сұрыптау – массив элементтерін белгілі бір заңдылықпен орындарын ауыстырып реттеу процесін айтамыз. Мысалы, сандар массивін өсуі, кемуі бойынша сұрыптау, жолдар массивін алфавит бойынша сұрыптау және тағыбасқа.
Сұрыптау барлық программалау саласында қолданылады. Сұрыптау бұл ақпараттық объектілердің мәндерін өсу немемсе кему бойынша реттелуін іске асыратын процесс. Мысалы, егер i<= i<=... <= i болса, онда n – элементтеріндегі i тізімдері өсу бойынша сұрыпталады. Сұрыптау алгоритмнің екі түрі бар: операциялық жадыда немесе дискідегі файл түрінде орналастырылған массивтердің сұрыпталуы және магниттік ленталардағы немесе дисктерде орналасқан кезекті файлдардың сұрыпталуы.
Массивтерді және кезекті файлдарды сұрыптаудың негізгі ерекшелігі – массивтің әрбір элементі әр уақытта жеңіл беріледі. Ол әр уақытта массивтің кез келген элементі басқа бір массивтің элементімен салыстырылады да, массивтің кез келге екі элементтері орындарымен ауыстырылуы мүмкін. Ал кезекті файлда әрбір уақытта тек қана бір элемент беріледі. Осындай айырмашылықтардан сұрыптаудың тәсілдерінде бір-бірінен үлкен өзгерістері бар.
Кестелермен жұмыс істегенде оның негізгі операциялары – ол жазбаларды реттеу және берілген шарт бойынша жазба кестелерінде барлау жасау.
Сұрыптау – бұл кейбір критерийлері бойынша жазбаны кестелерде нақты бір тәртіппен реттеуоперациясы. Сұрыптау барлық жазбалар кілттерінің мәндерімен сәйкес іске асады (мыс., алфавит бойынша аттарын реттеу немесе сандарды өсу бойынша реттеу). Сұрыптаудың көптеген бір-бірінен айрықша тәсілдері бар. Егер де кесте бүтіндей ЭЕМ-нің жедел жадында орналасса, онда оның реттелуі ішкі деп аталады. Ал егер де реттелген мәліметтерді сақтау үшін сыртқы есте сақтау құрылғысы пайдаланса, онда бұндай реттелу сыртқы деп аталады. Операцияларды салыстырудың орташа саны, сұрыптаудың тәсілінен байланысты, және де рационалды тәсілді таңдаған кезде кейбіреулері минимумға жетеді. Ішкі сұрыптау тәсілдерін екі топқа бөлуге болады:
• Резервтік жадыны қажет ететін тәсілдер
• Резервтік жадыны қажет етпейтін тәсілдер
Бірінші топқа таңдау, енгізу, көпіршік (пузырька), Шелл тәсілдері жатса, екінші топқа квадраттық таңдау, қосылу тәсілі және т.б жатады. Қарапайым сұрыптау тәсілдері (таңдау, енгізу, ауыстыру) шамамен n**2 салыстыруынталап етеді. Әдетте одан да қиынырақ алгоритмдер орташа n*log2(n) салыстыруларында нәтиженің берілуін қамтамасыз етеді. Бірақ та кез келген жағдайларда қолайлы сұрыптау жоқ, себебі олардың тиімділігі кестедегі кілттердің түріне және олардың алдын ала реттелуіне байланысты.

1. Бүркіт Ә.Х. Информатиканы оқытудың теориясы мен әдістемесі. Шымкент, 2012. – Б. 1005-1007.
2. Қойбағарова Т.Қ., Ельтинова Р.А. Информатиканы оқыту әдістемесі: Оқу құралы. І-ІІ-бөлім.
3. Вирт Н. Алгоритмы + структуры данных = программа./Н.Вирт. – М.: Мир, 1985.
4. Вирт Н. Алгоритмы и структуры данных./ Н.Вирт. – М.: Мир, 1989. – 360 с.

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

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

СӨЖ
Тақырыбы: Сұрыптау есептері. Қою арқылы сұраптау

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

Семей қаласы,
2015 жыл
Сұрыптау - массив элементтерін белгілі бір заңдылықпен орындарын ауыстырып реттеу процесін айтамыз. Мысалы, сандар массивін өсуі, кемуі бойынша сұрыптау, жолдар массивін алфавит бойынша сұрыптау және тағыбасқа.
Сұрыптау барлық программалау саласында қолданылады. Сұрыптау бұл ақпараттық объектілердің мәндерін өсу немемсе кему бойынша реттелуін іске асыратын процесс. Мысалы, егер i= i=... = i болса, онда n - элементтеріндегі i тізімдері өсу бойынша сұрыпталады. Сұрыптау алгоритмнің екі түрі бар: операциялық жадыда немесе дискідегі файл түрінде орналастырылған массивтердің сұрыпталуы және магниттік ленталардағы немесе дисктерде орналасқан кезекті файлдардың сұрыпталуы.
Массивтерді және кезекті файлдарды сұрыптаудың негізгі ерекшелігі - массивтің әрбір элементі әр уақытта жеңіл беріледі. Ол әр уақытта массивтің кез келген элементі басқа бір массивтің элементімен салыстырылады да, массивтің кез келге екі элементтері орындарымен ауыстырылуы мүмкін. Ал кезекті файлда әрбір уақытта тек қана бір элемент беріледі. Осындай айырмашылықтардан сұрыптаудың тәсілдерінде бір-бірінен үлкен өзгерістері бар.
Кестелермен жұмыс істегенде оның негізгі операциялары - ол жазбаларды реттеу және берілген шарт бойынша жазба кестелерінде барлау жасау.
Сұрыптау - бұл кейбір критерийлері бойынша жазбаны кестелерде нақты бір тәртіппен реттеуоперациясы. Сұрыптау барлық жазбалар кілттерінің мәндерімен сәйкес іске асады (мыс., алфавит бойынша аттарын реттеу немесе сандарды өсу бойынша реттеу). Сұрыптаудың көптеген бір-бірінен айрықша тәсілдері бар. Егер де кесте бүтіндей ЭЕМ-нің жедел жадында орналасса, онда оның реттелуі ішкі деп аталады. Ал егер де реттелген мәліметтерді сақтау үшін сыртқы есте сақтау құрылғысы пайдаланса, онда бұндай реттелу сыртқы деп аталады. Операцияларды салыстырудың орташа саны, сұрыптаудың тәсілінен байланысты, және де рационалды тәсілді таңдаған кезде кейбіреулері минимумға жетеді. Ішкі сұрыптау тәсілдерін екі топқа бөлуге болады:
* Резервтік жадыны қажет ететін тәсілдер
* Резервтік жадыны қажет етпейтін тәсілдер
Бірінші топқа таңдау, енгізу, көпіршік (пузырька), Шелл тәсілдері жатса, екінші топқа квадраттық таңдау, қосылу тәсілі және т.б жатады. Қарапайым сұрыптау тәсілдері (таңдау, енгізу, ауыстыру) шамамен n**2 салыстыруынталап етеді. Әдетте одан да қиынырақ алгоритмдер орташа n*log2(n) салыстыруларында нәтиженің берілуін қамтамасыз етеді. Бірақ та кез келген жағдайларда қолайлы сұрыптау жоқ, себебі олардың тиімділігі кестедегі кілттердің түріне және олардың алдын ала реттелуіне байланысты.
Сұрыптаудың мақсаты - сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету.
Ішкі сұрыптаулар алгоритмдері - бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым - массив. Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап - жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау (көбікше әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау). Кірулермен сұрыптау - элементтер шартты түрде дайын тізбекке a1, ai-1 және кіретін тізбекке ai,..., an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді. Таңдаумен сұрыптау - ең кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Алмасумен сұрыптау - барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады.
Қарапайым таңдаумен сұрыптау әдісі қарапайым әдістердің ішіндегі ең жақсысы, алмасумен сұрыптау - ең жаманы, ал жылдам сұрыптау ең тезі және ең жақсысы болып табылады.
Бүгінгі таңда сұрыптаудың көптеген тәсілдері белгілі. Олар:
Массивтерді сұрыптау алгоритмдері 4-ке бөлінеді:
1. Таңдау арқылы сұрыптау.
2. Ауыстыру арқылы сұрыптау (көпіршік әдісі).
3. Қою арқы арқылы сұрыптау.
4. Тез сұрыптау.
Сұрыптау немесе объектілер тізімін реттеу деп осы объектілердің қандай да бір сызықтық реттілікке қатысты өсуі мен кемуі бойынша орындауды айтамыз. Сұрыптаудың мәні сонда жазулар тізімінің реттілігін кілттік өріс мәндері кемімейтін тізбек құратындай етуіміз керек. Басқа сөзбен айтқанда R1, R2, .. , Rn жазулары кілттік мәндері K1, K2,...,Kn орналасуы керек. Ki1Ki2 ... Kin.Мұнда реттелген тізбектегі кілттердің бірдей мәндері бар жазулар бір-бірімен қатар орындалады. Сұрыптау әдістері 2 категорияға бөлінеді:
- массивтерді сұрыптау (ішкі сұрыптау)
- тізбектелген файлдарды сұрыптау (сыртқы сұрыптау).
Массивтер ішкі оперативті жадыда орналасады. Оған кез келген уақытта тез кіруге болады. Ал сыртқы сұрыптау реттеуге тиісті мәліметтер көлемі өте үлкен болғанда мәліметтердің оперативті жадыға симай қалғанда қолданылады.
Таңдау көмегімен сұрыптау.
А массивінде мәліметтердің n элементі сақталған және бұл массив бойынша n-1 жүріс етеді. 0-ші жүрісте ең кіші элемент таңдалады. Ол кейіннен А0 элементпен айырбасталады. Келесі жүрісте тізімнің А1 элементінен бастап реттелмеген бөлігі қарастырылады. Мұнда ең кіші элемент тауып алынады да А1-де сақталады. Ары қарай А2 ... Аn-1 тізіміндегі ең кіші элемент ізделеді. Табылған мән А2-мен ауысады. Осылайша, n-1 жүріс өтеді. Соңында тізімнің реттелмеген аяғы 1 элементке дейін қысқарады. Сол элемент ең үлкен болып табылады.
Мысалға, 50,20,40,75,35 массив берілген.
0-жүріс. 20-ны таңдаймыз. Оны А0-мен ауыстырамыз (А0=50).
20,50,40,75,35.
1-жүріс. 35 таңдаймыз. Оны А1-мен орын ауыстырамыз.
20,35,40,75,50.
2-жүріс. 40 таңдаймыз. Оны А2-мен орын ауыстырамыз.
20,35,40,75,50.
3-жүріс. 50 таңдаймыз. Оны А3-пен орын ауыстырамыз.
20,35,40,50,75.
Соңғы қалған 75 саны ең үлкен элемент сұрыпталып шыққанда:
20,35,40,50,75.
Ауыстыру арқылы сұрыптау.
N элементтен тұратын а массивін айырбастау арқылы сұрыптау үшін немесе көпіршік әдісімен сұрыптау үшін n-ші жүріс қажет. Әрбір жүрісте көршілес екі элемент салыстырылады және егер 1-сі үлкен болса немесе 2-не тең болса, онда бұл элементтер орындарымен ауысады. әрбір жүрістің аяғында ең кіші элемент ішкі тізімнің жоғарғы жағына көтеріліп отырады. Бұл қайнап жатқан судың ішіндегі ауаның көбікшесіне ұқсас. Сондықтан көпіршік әдісі деп аталады.
Мысал. Массив:
50,20,40,75,35
0-жүріс. 50 мен 20салыстырылады.
20,50,40,75,35
1-жүріс. 50 мен 40 салыстырылады
20,40,50,75,35
2-жүріс. 50 мен 70 реттелген, сондықтан қалады.
20,40,50,70,35
3-жүріс.75 пен 35 салыстырылады.
20,40,50,35,75
4-жүріс. 50 мен 35 салыстырылады
20,40,35,50,75
5-жүріс. 40 пен 35 салыстырылады
20,35,40,50,75
20 мен 30 реттелген
20,35,40,50,75 болып реттеледі.
Массивтегі жүрістер саны минимальды немесе максимальды элемент қай жерде орналасқанына байланысты. Мұнда бірінен кейін бірі келетін жүрістердің бағытын ауыстыру арқылы жылдамдатуға болады. Мұндай алгоритм Шейкер сұрыптауы деп аталады.
Қою арқылы сұрыптау. Тез сұрыптау
Қою арқылы сұрыптау - келесі процеске ұқсас. Карточкаларға аттарды жазып, карточкаларды алфавит бойынша өзіне керекті орынға қыстырып қою арқылы реттеу. Мысалға:
50,20,40,75,35 массивін қыстыру арқылы сұрыптау керек. 50 элементінен бастаймыз. 20-ны 0 позициясына қыстыру, 50-ді 1 позициясына жылжыту.
40-ты 1 позициясына қыстыру, 50-ді 2 позицияға жылжыту.
75-ті 3 позициясына қыстыру.
35-ті 1 позициясына қыстыру, қалғандарын оңға қарай жылжыту.
Есептеу күрделілігі: жалпы салыстырулар саны -ге тең. Ең жақсы жағдайда, яғни тізім реттелген жағдайда күрделілігі О(n)-ге , ал жаман жағдайда О(n2)-ге тең.
Бинарлық қоюлар арқылы сұрыптау.
Бұл жай енгізулермен сұрыптаудың жақсартылған варианты. Жаңа элементті қосуға қажетті дайын тізбек реттелген болып, енгізу орнын неғұрлым жылдам табуға негізделген. Ол үшін дайын тізбектің ортаңғы элементі ізделіп, ары қарай ортасынан бөлу ... жалғасы

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