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


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

Сұрыптаудың түрлеріне тоқатала кетейік:

1. Ауыстырмалы сұрыптау (көпіршік әдісі)
Алгоритм 1-ші мен 2-ші элементтерді салыстырудан басталады. Егер 2-ші элемент 1-шіден кіші болса, онда оларды орындарымен алмастырылады. Бұл процесс қатар тұрған әр жұп элементтері үшін қайталанады, процесс бүкіл N элементтері өңделмейінше қайталанады. Массивтің бір «өтімінен» кейін ең үлкен элемент ең артқы (N-ші) орынға тұрғызылады. Алгоритм жалғаса береді, сонда p-ші өтім кезінде алғаш (N-p) элементтері оң жақтағы көрші элементтерімен салыстырылады. Егер келесі бір өтімде алмастырулар болмаса, алгоритм өз жұмысын тоқтатады. Соңында ең «жеңіл» элементтер алгоритм орындалуы барысында біртіндеп «қалқып шығады».
Бұл әдістің ерекшелігі - әр элементті массивтің басқа элементетрімен салыстырып шығу емес, көрші екі элементпен салыстыру. Көпіршікті сұрыптаудың кемімелі алгоритмінің мәні мынада: М массивін біртіндеп төменнен жоғары қарай (басынан аяғына дейін) қарап шығу. Егер көрші элементтері шарт орындалатындай болса (шарты – оң жақтағы элемент сол жақтағы элементтен үлкен), онда осы элементтердің мәндері ауысады.
1. «Қазақстан»: Ұлттық энцклопедия / Бас редактор Ә. Нысанбаев – Алматы «Қазақ энциклопедиясы» Бас редакциясы, 1998.
2. Бурин Е. А. Программирование на языке Турбо Паскаль. А., 2000.
3. Досмайлов Т.К. “Программалау тілі Паскаль” А.,1996.

Пән: Информатика
Жұмыс түрі: Материал
Көлемі: 3 бет
Бұл жұмыстың бағасы: 300 теңге




ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ
СЕМЕЙ ҚАЛАСЫНДАҒЫ ШӘКӘРІМ АТЫНДАҒЫ УНИВЕРСИТЕТІ
Информатика және ақпаратттық технологиялар кафедрасы

СРО

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

Пәні: Мәліметтер қоры алгоритмі және құрылымы.

Орындаған: Нуркенов. Е.Б.

Тексерген: Болсынбекова Ш.Ж.

Семей 2015жыл.

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

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

Сұрыптаудың түрлеріне тоқатала кетейік:

1. Ауыстырмалы сұрыптау (көпіршік әдісі)
Алгоритм 1-ші мен 2-ші элементтерді салыстырудан басталады. Егер 2-
ші элемент 1-шіден кіші болса, онда оларды орындарымен алмастырылады. Бұл
процесс қатар тұрған әр жұп элементтері үшін қайталанады, процесс бүкіл N
элементтері өңделмейінше қайталанады. Массивтің бір өтімінен кейін ең
үлкен элемент ең артқы (N-ші) орынға тұрғызылады. Алгоритм жалғаса береді,
сонда p-ші өтім кезінде алғаш (N-p) элементтері оң жақтағы көрші
элементтерімен салыстырылады. Егер келесі бір өтімде алмастырулар болмаса,
алгоритм өз жұмысын тоқтатады. Соңында ең жеңіл элементтер алгоритм
орындалуы барысында біртіндеп қалқып шығады.
Бұл әдістің ерекшелігі - әр элементті массивтің басқа
элементетрімен салыстырып шығу емес, көрші екі элементпен салыстыру.
Көпіршікті сұрыптаудың кемімелі алгоритмінің мәні мынада: М массивін
біртіндеп төменнен жоғары қарай (басынан аяғына дейін) қарап шығу. Егер
көрші элементтері шарт орындалатындай болса (шарты – оң жақтағы элемент сол
жақтағы элементтен үлкен), онда осы элементтердің мәндері ауысады.
Ауыстырмалы сұрыптау:
for i := 1 to n-1 do 
for j := n-1 downto i do 
if a[j] a[j+1] then begin 
x := a[j]; 
a[j] := a[j+1]; 
a[j+1] := x; 
end;

2. Қою (орналастыру) арқылы сұрыптау.
Бұл жағдайда басында алғаш тұрған екі элемент сұрыпталады. Олар
сұрыпталған S жиынын құрайды. Келесі элемент алынып, сұрыпталған S жиынына
сол жағындағы элементтері одан кіші етіліп, ал оң жағынан артық болып
қойылады. Берілген элементті жиынға тұрғызу орны – аралықты жартыға бөлу
арқылы табылады. Алгоритм қашан өз жұмысын аяқтайды, сол жағдайда N-ші
орында тұрған элемент өңделіп болады.
Айталық сізге массив берілді. Бұл массив элементтерін
Орналастыру арқылы сұрыптау тәсілімен төменнен жоғары қарай былай
сұрыптаймыз:
Массивтің екінші элементін аламыз, оны бірінші элементпен салыстырамыз.
Егер екінші элемент бірінші элементтен кіші болса, екінші элементті
біріншінің, бірінші элементті екіншінің орнына орналастырамыз. Егер екінші
элемент бірінші элементтен үлкен немесе тең болса, ешнәрсе істемей
процессті жалғастыра береміз. Сосын үшінші элементті алып екінші элементпен
салыстырамыз, егер үшінші элемент екінші элементтен кішкентай болса,
олардың орындарын ауыстырамыз, содан кейін (екіншінің орнына келген үшінші
элементті) бірінші элементпен салыстырамыз. Осы процесс массив аяқталғанша
жалғаса береді. Соңында элементтері сұрыпталған массивке қол жеткіземіз. 

Бұл алгоритмді кішкентай (он шақты элементі бар) массивтерді
сұрыптау үшін қолдануға болады және "Таңдау арқылы сұрыптау" алгоритміне
қарағанда сәл ақылдырақ, яғни берілген массив неғұрлым сұрыпталған болса,
бұл алгоритмнің жылдамдығы соғұрлым артады. 

3. Таңдап алу (сызықтық) арқылы сұрыптау.
N элементтерден құралған массивттің ең үлкен элементі табылады
(ол p нөмерінде тұр делік), оның N-ші орында тұрған элементпен орындары
ауыстырылады, мұнда бір шарт сақталуы тиіс: N p, яғни олар тең болмауы
керек. Қалған (N-1) элементтерден ... жалғасы
Ұқсас жұмыстар
Сұрыптау әдістері
Бір өлшемді массивтерді сұрыптау алгоритмдері
Сұрыптау әдістері жайында
Сұрыптау есептері. Сұрыптау алгоритмдері
Сұрыптау есептері, сұрыптау алгоритмдері
Сұрыптау. Мәліметтерді сұрыптау
Сұрыптау есептері, қою арқылы сұрыптау
Сұрыптау есептері. Сұрыптау алгоритмі
Сұрыптау есептері. Таңдау арқылы сұрыптау
Сұрыптау есептері
Пәндер

Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор №1 болып табылады.

Байланыс

Qazaqstan
Phone: 777 614 50 20
WhatsApp: 777 614 50 20
Email: info@stud.kz
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь