Массивтерді сұрыптау әдістері Насруллаева Айкерим

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

Насруллаева Айкерим

Сұрыптау

Сұрыптау - қазіргі заманда мәліметтері өңдеу процессінің кең тараған түрлерінің бірі.

Массив элементтерін белгіленген ережелер бойынша орналастыру болып табылады. Мысалы, массивті өсуі немесе кемуі бойынша сұрыптау.

5 10 15 20 25 - осу

Сұрыптау түрлері: Ауыстырмалы сұрыптау

Алгоритм 1-ші мен 2-ші элементтерді салыстырудан басталады. Егер 2-ші элемент 1-шіден кіші болса, онда оларды орындарымен алмастырылады. Бұл процесс қатар тұрған әр жұп элементтері үшін пайдаланылады, процесс бүкіл N элементтері өңделмейінше қайталанады.

Ауыстырмалы сұрыптау:

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;

1 5 6 9 11 2 1

Сұрыптау түрлері: Орналастыру арқылы сұрыптау

Бұл жағдайда басында алғаш тұрған екі элемент сұрыпталады. Олар сұрыпталған S жиынын құрайды. Келесі элемент алынып, сұрыпталған S жиынына сол жағындағы элементтері одан кіші етіліп, ал оң жағынан артық болып қойылады. Берілген элементті жиынға тұрғызу орны – аралықты жартыға бөлу арқылы табылады. Алгоритм қашан өз жұмысын аяқтайды, сол жағдайда N-ші орында тұрған элемент өңделіп болады.

Айталық сізге массив берілді. Бұл массив элементтерін «Орналастыру арқылы сұрыптау» тәсілімен төменнен жоғары қарай былай сұрыптаймыз:

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

Сұрыптау түрлері: Таңдап алу арқылы сұрыптау

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;

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

Таңдау арқылы сұрыптау - бұл сұрыптаудың ең қолайлы түрі. Әдетте бұл әдіс кестені реттеуді қажет еткен адам ойына ең бірінші келеді. Бұның мәні мынада, мысалы n элементтен тұратын А сандар массиві берілген. Оны таңдау әдісін қолданып элементтерінің өсуі бойынша сұрыптау қажет.

Енгізу арқылы сұрыптау - бұл массивтің сұрыпталмаған бөлігінен сұрыпталған бөлігіне элементтерді енгізу болып табылады. Енгізілген элемент массив бөлігінің сұрыпталуын бұзбау қажет. Ол үшін енгізілген элемент өз орнын тапқанша, сұрыпталған бөлігінің элементтерімен орын ауыстырып отыруы тиіс.

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

Біріктіру арқылы сұрыптау - массив элементтерін бөліктерге бөліп, бөлек-бөлек сұрыптау.

Бұл әдіс бойынша:

· Берілген массив бірнеше бөліктерге (кіші масивтерге) бөлініп, бөлек-бөлек сұрыпталады;

· Бірінші және екінші бөліктен сұрыпталған бір бөлік жасақталады; пайда болған бөлік пен үшінші бөлік және тағы да сол тәрізді сұрыпталады;

· Осы процесс соңғы екі бөлік біріккенге дейін жалғасып отырады.

Сұрыптаудың шейкерлі әдісі - ретсіздіктен құтылу арқылы сұрыптау.

Бұл әдіс 1959 жылы Donald Lewis Shell авторының атынан ұсынылды. Бұл алгоритмнің негізгі мәні мынада:

· Массивтегі ретсіздіктен құтыламыз;

· Бір-бірінен алшақ орналасқан элементтерді салыстырамыз;

· Салыстырып отырған интервалдар бірте-бірте кемиді;

· Соңғы қадамдарды элементтер жай ғана орые алмастырумен шектеледі.