Массивтерді сұрыптаудың негізгі алгоритмдері

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

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

СЕМЕЙ ҚАЛАСЫНДАҒЫ ШӘКӘРІМ АТЫНДАҒЫ УНИВЕРСИТЕТІ

Информатика және ақпаратттық технологиялар кафедрасы

СРО

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

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

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

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

Семей 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) элементтерден тағы да ең үлкені таңдап алынады да, N-1 орында тұрған элементпен алмастырылады. Өз жұмысын алгоритм 1-ші және 2-ші орындарда тұрған элементтер сұрыпталғаннан кейін ғана өз жұмысын тоқтатады. Ол үшін N-1 өтім керек болады. Осылайша ең кіші элементтерді

сұрыптауға да қолдануға болады.

for i := 1 to n-1 do begin
k := i; x := a[i] ;
for j := i+1 to n do
if a[j] < x then begin
k := j;
x := a[j] ;
end;
a[k] := a[i] ;
a[i] := x;

end;

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

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

Сонымен қатар, массивте келесі сұрыптаулар түрлері де бар:

... жалғасы

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