Современные информационные технологии/2. Вычислительная техника и программирование

Мурадилова Г.С., Балгабаева Р.Н., Отарова А.С.

Кокшетауский государственный университет им.Ш.Уалиханова, Казахстан

«АЛГОРИТМДЕУ ЖӘНЕ ПРОГРАММАЛАУ ТІЛДЕРІ» ПӘНІНДЕ МАССИВТЕРДІ РЕТТЕУДІҢ КЕЙБІР ӘДІСТЕРІ

Компьютерлік мамандықтардың студенттеріне «Алгоритмдеу және программалау тілдері» пәнін оқытуда алгоритмдік ойлау қабілетін арттыру, әртүрлі бағыттағы есептерді шешуде алған білімдерін қолдана білу, «функция», «рекурсия» түсініктерін меңгеру мақсаттарында массивтерді реттеу әдістеріне ерекше назар аударылады.

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

Массивтің реттелуі деп кейбір критерийлерге сәйкес реттеу мақсатында элементтерді алмастыру үрдісін айтуға болады.

Массивтерді реттеудің көптеген әдістері (алгоритмдері) бар. Ең жақсы әдістердің бірі - Хоар әдісін қарастырайық. Ол көпіршік әдісіне негізделеді. Тез реттеу негізі - "қаққа бөлу әдісі" болып табылады. Бұл реттеу басқаша Quicksort - тез реттеу деп аталады. Бұл әдісті 1962 жылы Оксфорд университетінің профессоры Хоар ойлап тапты.

Хоар келесі алгоритмді ұсынды. pp ретінде тізбектің қандай да бір ортасынан элемент таңдап алайық (әдетте ортаңғы элементті таңдайды). Егер ол өз орнында тұрса (тізбек реттелген жағдайда), онда сол жағында орналасқан барлық элементтер рр-дан артық емес, ал оң жағында орналасқан барлық элементтер рр-дан кем емес болады.

Сондықтан, тез реттеудің бірінші қадамы: pp-дан кем оң жартысының элементтерін массивтің сол бөлігіне, ал pp-дан артық сол бөлігінің элементтерін массивтің оң бөлігіне алып бару болып табылады. Әдетте, бұл жағдайда іздеуді pp-ның екі жағынан жүргізеді, қалай ретті бұзатын жұп табылса, солай айырбастау жасалады. Одан кейін осы сияқты тәсіл әрбір алынған жартыға қолданылады. Әрқайсысында өзіндік орташа элемент таңдалынады және оған салыстырмалы қажетті алмастырулар жүргізіледі. Хоар алгоритмі рекурсивті процедура түсінігіне жақсы сәйкестенеді. Бір қалыпты түрде қатынау үшін тез реттеу процедурасы екі процедура түрінде ұсынылды – қолданушы қатынайтын – сыртқы fun, және ішкі – fun1. Соңғысы l(left) және r(right) индекстерінің шектеулі мәндерімен берілген ішкі массивтің рекурсивті өңдеуін орындайды. Хоар әдісінің программасы келесі листингте ұсынылды:

#include <iostream.h>

#include <conio.h>

void fun(int *y, int l, int r);

void fun1(int *y, int n)

{

fun(y,0,n-1);

return;

}

void fun(int *y, int l, int r)

{

register int i,j;

int pp,buf;

i=l;

j=r;

pp=y[(l+r)/2];

do

{

while (y[i] < pp && i < r) i++;

while (pp < y[j] && j > l) j--;

if(i<=j)

{

buf=y[i];

y[i]=y[j];

y[j]=buf;

i++; j--;

}

}

while(i<=j);

if(l < j) fun(y,l,j);

if(i < r) fun(y,i,r);

return;

}

int main(int argc, char* argv[])

{

int a[10];

int n=10;

for (int i=0;i<10;i++)

cin>>a[i];

fun1(a,n);

for (int i=0;i<10;i++)

cout<<a[i]<<" ";

getch();

return 0;

}

Литература:

1. Иванова Г.С. Технология программирования: Учебное пособие. М.: МГТУ им. Н.Э.Баумана, 2002.

2. Павловская Т.А. С/С++. Программирование на языке высокого уровня: Учебное пособие. СПб.: Питер, 2002.

3. Кнут Д. Искусство программирования для ЭВМ.Т.З: Сортировка и поиск. М.: Мир, 1978.