Мәліметтердің барлық жиынын бір реттен өңдейтін операция фаза деп
аталады. Қайталана отырып сұрыптау процесін құратын кішкентай ішкі
процесс кезең
немесе этап деп аталады. Біздің мысалда сұрыптау үш кезеңде
жасалады. Әрбір кезең бөлу фазасы мен біріктіру фазасынан тұрады.
Сұрыптау үшін үш файл (лента) қажет, сондықтан бұл әдіс үшленталы
біріктіру деп аталады.
Жалпы айтқанда, бөлу фазасы сұрыптауға жатпайды, себебі олар
элементтердің орнын ауыстыра алмайды. Бұл мағынада олар непродуктивны.
Оларды біріктіру және бөлу фазаларын қосып жоюға болады; элементтерді
бір тізбекке біріктірудің орнына біріктірудің нәтижесін бірден келесі кезеңде
енуші тізбек болатын екі тізбекке (ленталарға) бөледі. Сонымен қатар,
көшіру операцияларын үнемдейміз (екі есе кіші), бірақ бұл қосымша
(сыртқа) жадыны (төртінші лентаны қолдану) қолдануға әкеледі.
Бұндай әдістің екіфазалықтан айырмашылығы бірфазалық немесе
балансталған біріктіру деп аталады.
Біріктіру бағдарламасын тереңірек талдайық. Бастапқыда мәліметтер
массив түрінде (қарапайымдылық үшін) орналасқан деп алайық, бірақ тек
қана тізбекті қарастыруға болады. Бағдарламаның басқа нұсқасын файлдарда
қарастырамыз да, сосын екеуін салыстырамыз.
Екі файлдың орнына бір массивті қолдануға болады, оны екі соңы бар
тізбек ретінде қарастырамыз. Екі файлдың элементтерін біріктірудің орнына
оларды массивтің екі соңынан алуға болады. Осылайша біріктіру-бөлу
фазаларын біріктірудің жалпы түрін 3-суретте көрсетілгендей бейнелеуге
болады.
Сур.3 Қарапайым біріктіру әдісімен екі массивті сұрыптау
Біріктірілетін элементтердің қайта сілтеу бағыты әрбір реттелген
жұптардан кейін (бірінші кезеңде), төрттіктер (екінші кезеңде) және т.с.с.
өзгереді. Осылайша, екі шығыстық тізбектер бірқалыпты толтырылады –
шығыстық массивтің екі шегі. Әрбір кезеңнен кейін орындарымен ауысады:
шығыстық енетінге ауысады және керісінше.
Процедураны екі массивті бреуіне – еклік ұзындыққа біріктіру арқылы
жеңілдетуге болады:
А : аrrау [ 1 ..2*N] of item;
i, j индекстері екі берілген элементті көрсетсін, k, l – қайта сілтеудің екі
орнын. Бастапқы берілгендер - А[1], ..., A[N] элементтері. Берілгендердің
қайта сілтеу бағ
up = true - ағымдағы кезеңде А[I],..., A[N] компоненттері "жоғарыға"
A[N+1],..., A[2*N] айнымалыларына қайта сілтеледі
(А[1],..., A[N] -> A[N+1],.., A[2-N]) up = false - "төменге" қайта
сілтеледі - A[N+1],..., A[2*N] айнымалылары A[1], …, A[N]-ге сілтеледі.
(A[N+1],..., A[2*N] -> A[1],..., A[N])
Up мәні әрбір кезеңнен кейін өзгереді.
Сонымен қатар, біріктірілетін ішкі тізбектердің ұзындығы үшін Р
айнымалысын енгіземіз. Оның бастапқы мәні Р = 1 және әрбір кезекті
кезеңнен кейін екі есе көбейеді. Қарапйымдылық үшін N әрқашанда екінің
дәрежесі деп есептейміз.
Онда қарапайым біріктіру бағдарламасының бірінші нұсқасы;
PROCEDURE MERGESORT;
VAR I, J, К, L, P: INTEGER;
UP: BOOLEAN;
BEGIN
UP:=TRUE; P:=1;
REPEAT { индекстерді инициализациялау }
IF UP THEN
BEGIN I :=1; J :=N; К :=N+1; L :=2*N END
ELSE BEGIN К :=1; L :-N; I :=N+1; J:=2*N END;
{ П.1 - I, J тізбектерінің Р-жинағын К, L
тізбектеріне біріктіру }
UP - NOT UP; Р:= 2 * P
UNTIL P = N;
END;
П.1-ні нақтылайық. Бұл N элементтерді өңдейтін кезең Р-
жинақтарының тізбекті біріктірілуінен тұрады. Әрбір біріктірілуден кейін
қайта сілтеудің бағыты шығыстық массивтің төменгі шегінен жоғарысына
ауысады немесе керісінше (екі бағыттағы бірдей таратылуды қамтамасыз ету
үшін).
Егер біріктірілетін элементтер массивтің төменгі шегіне сілтелсе, онда
қайта сілтеудің индексі k болады, және k әрбір қайта сілтеуден кейін 1-ге
көбейеді, ал егер массивтің жоғарғы шегіне сілтелсе, онда l әрбір қайта
сілтеуден кейін 1-ге азаяды.
Біріктіру опреациясын жеңілдетуге болады, егер қайта сілтеу орнын
әрқашан k арқылы белгілеп, сосын әрбір Р-жинағының біріктірілуінен кейін k
мен l-дің орнын ауыстырып отырсақ. Индекстің кеңейтілуін h арқылы
белгілейміз, мұндағыh= 1 немесе h= -1.
Енді П. 1-ды аламыз:
H:=1; M:=N;
REPEAT
Q := Р; R:= Р; М := М - 2 * Р;
{П. 1.1 I-дағы Q элементтержің біріктірілуі және J-дағы R
элементтердің біріктірлуі, сілтеу индексі Н кеңейтілуі бар К}
Н:= -Н;
{П. 1.2 К мен L мәндерін айырбастау; }
UNTIL М = 0;
П. 1.1-ді бөлшектейміз. Біріктіруден кейін бос болып қалмайтын тізбек
қалдығы қарапайым кодтау көмегімен шығыстық тізбекке қосылатынын
ескеру керек.
WHILE (Q <> 0) AND (R <> 0 )
DO BEGIN { I-дан немесе J-дан элемент таңдау}
IF A[I].KEY < A[J].KEY THEN BEGIN
{п. I.I.I – I-дан К-ға элементті сілтеу, I мен К-нің үлкеюі;}
Q:=Q-1
END ELSE BEGIN
{п. 1.1.2 - J дан К-ға элементті сілтеу, J мен К-нің үлкеюі;}
R:=R-1;
END
END;
{п. 1.1.3. I тізбегінің қалдығын көшіру;}
{п. 1.1.4. J тізбегінің қалдығын көшіру;}
пп.1.1.1 мен 1.1.2-ні бөлшектеу қажет емес; пп.1.1.3 мен 1.1.4-ді
барлық бағдарлама жазбасының процесінде бөлшектейміз.; п. 1.2 –ні де.
Жазбаның алдында N-ге (екінің дәрежесі) шектеуді алып тастауға
тырысамыз. Жалпы жағдайда енетін тізбектердің қалдығының ұзындығы Р-
дан кем болып қалғанша Р-жинағының біріктірілуін жалғастыра береміз. Бұл
алгоритмнің біріктірілетін тізбектердің ұзындықтары – Q мен R мәндері
анықталатын бөлігіне әсер етеді. Онда үш оператордың орнына
Q := Р; R := Р; М:=М-2*Р;төрт оператор қолданамыз
IF М >= P THEN Q := Р ELSE Q := М; М :- М - Q;
IF М >= Р THEN R := Р ELSE R := М; М :- М - R;
М – біріктірілетін екі енетін тізбектің элементтерінің жалпы санын
білдіреді.
Сонымен, бағдарлама жұмысының аяқталуын қамтамасыз ету үшін
сыртқы циклді басқаратын Р = N шартын Р >= N шартына ауыстыру керек,
Енді барлық алгоритмді жазып шығайық.
PROCEDURE MERGESORT;
VAR I, J, К, L, Т, Н, М, Р, Q, R: INTEGER;
UP: BOOLEAN;
BEGIN UP-TRUE; P:=1;
REPEAT H:=1;M:=N;
IF UP THEN
BEGIN I := 1;J:=N;K:=N+ 1;L:=2*N END
ELSE К := 1; L := N; I := N + 1; J := 2 * N END;
REPEAT {}
{}
IF M >= P THEN Q := P ELSE Q := М; М := M - Q;
IF M >= P THEN R := P ELSE R := М; М := М - R;
WHILE ( Q <> 0 ) AND ( R <> 0 ) DO
BEGIN
IF A[I].KEY < A[J].KEY THEN BEGIN
A[K]:= A[I]; К := К + H; I := I + 1; Q := Q -1;
END ELSE BEGIN
A[K] := A[J]; К := К + H; J :- J + 1; R := R - 1
END END;
{ j-дағы серияның қалдығын көшіру}
WHILE R <> О DO BEGIN
A[K]:=A[J];K:=K+H;J:-J-1;R:=R- 1 END;
{ I- дағы серияның қалдығын көшіру }
WHILE Q <> О DO BEGIN
A[k] := A[I]; K := K+H: I:=I-l; Q:=Q- 1
END;
H := -Н; Т := К; К:= L; L := Т UNTIL М = 0;
Достарыңызбен бөлісу: |
