UP := NOT UP; P := 2 * P;
UNTIL P >= N;
IF NOT UP THEN
FOR I :
=
1 TO N DO A[I] := A[I+N];
END;
Біріктіру арқылы сұрыптаудың анализі
Әрбір кезеңде ішкі Р тізбектің ұзындығы екі есе көбейіп, және
сұрыптау аяқталғандықтан, Р >= N шарты болғанда, ол [log
2
N] кезеңді талап
етеді. Әрбір кезеңде (анықтама бойынша) N элементтен тұратын барлық
жиын бір рет көшіріледі. Осыдан, қайта сілтеудің жалпы саны мынаған тең:
М = N * [log
2
N]. С кілттерді салыстыру саны бұдан да кіші, себебі тізбек
қалдығын көшіру кезінде салыстыру жүргізілмейді. Сыртқы құрылғылармен
жұмыс кезіндегі негізгі уақыт қайта сілтеулерге кететіндіктен, бұл онша
маңызды емес (ол салыстыруға кететін уақытқа қарағанда бірнеше ретке
жоғары).
Қайта сілтеудің сандары бойынша алгоритм массивтерді сұрыптаудың
жетілдірілген әдісімен салысытырылады. Алайда, индекстерді басқаруға
кететін шығындар жеткілікті жоғары, сонымен қатар элементтердің 2N
өлшемді жадысын қолдану маңызды жетіспеушілік болып табылады.
Табиғи біріктіру
Қарапайым біріктіру алгоритмі мәліметтердің бөлшектеп реттелген
жағдайына әсер етпейді. Неғұрлым ұзынырақ ішкі тізбектердің реттелген
болуына және оларды біріктіруге болатынын есепке алмай, k–ші кезеңде
барлық біріктірілетін ішкі тізбектердің ұзындығы 2
k
-ге тең немесе одан кіші.
Яғни, т және п ұзындықты тізбектерді т + п элементтен тұратын
тізбекке бірден біріктіруге болады.
Әркез ең ұзын екі ішкі тізбек біріктірілетін сұрыптау әдісі табиғи
біріктіру деп аталады. a
k
<=a
k+1
болатындай a
i
, ..., a
j
тізбегін максималды
серия немесе жай серия деп атаймыз, мұндағы k = i, ..., j-1, a
i-1
>а
i
, a
j
>a
j+1
.
Осылайша, табиғи біріктірілуі бар сұрыптау алдын-ала берілген
ұзындығы бар тізбектерді емес, максималды серияларды біріктіреді.
Әрбіреуінде N серия бар екі тізбекті біріктіру кезінде тура N сериясы бар бір
тізбек пайда болады. Осылайша, әр кезеңде сериялардың жалпы саны екі есе
азаяды, және элементтерді қайта сілтеулердің қажетті саны нашар жағдайда
N * [log
2
N] –ге тең, ал әдеттегі жағдайда одан да кіші. Бірақ та,
салыстырулар саны неғұрлым көбірек, себебі элементтерді реттеуге арналған
салыстырулардан басқа да, сериялардың соңын анықтауға арналған әрбір
файлдың көршілес элементтерін салыстыру қажет.
Енді тізбекті файлға қолданылатын табиғи біріктірудің алгоритмін
қарастырайық.
Бастапқы тізбек С файлының түрінде берілген болсын, онда жұмыс
соңында сұрыптаудың нәтижелері болу керек. А және В көмекші файлдар
қолданылады. Әрбір кезең серияларды С-дан А мен В-ға тең бөлетін тарату
фазасынан және серияларды А мен В-дан С-ға біріктіретін біріктіру
фазасынан тұрады (сур.4).
Сур.4 сұрыптаудың фазалары мен сұрыптаудың кезеңдері
Сондықтан алгоритм өз алдына балансталмаған екіфазалы үшленталы
(үшфайлды) біріктіру сұрыптауын көрсетеді.
Мысал. 20 саннан тұратын файл.
Бастапқы
файл
17
37
31' 5
61
59' 13 41 43 67' 11 23 29 47' 3 7 71 ' 2 19 57'
1-шіден
кейін
5 37 17 31'
61
59' 11 13 23 29 41 43 47 67' 2 3 7 19 57 71
2- шіден
кейін
5 61 11 13
71
17 23 29 31 41 43 47 59 67' 2 3 7 19 37 57
3-ші
кезеңдерде
н кейін
проходов
2 67 357 71 11 13 17 19 23 29 31 37 41 43 47 57 59 61
Сериялар саны С бірге тең болған кезде сұрыптау аяқталады. (бастапқы
файлда тым болмаса бір бос емес серия бар деп есептеледі).
L – С-тағы сериялар санын санауға арналған айнымалы болсын.
Глобалды объектілерді анықтайық:
TYPE TAPE = FILE OF ITEM;
VAR С: ТАРЕ;
Онда бағдарламаны келесі түрде безендіруге болады:
PROCEDURE NATURALMERGE;
VAR L : INTEGER;
А, В:ТАРЕ;
BEGIN REPEAT
REWRITE (A); REWRITE (В); RESET (С);
DISTRIBUTE; { тарату}
RESET (A); RESET (В); REWRITE (С);
L:=0;
MERGE; { бөлу }
UNIT L - 1 END;
Naturalmerge-ге кіретін процедураны тізбекті нақтылай отырып,
қадамды бөлшектеу жасайық.
PROCEDURE DISTRIBUTE; { с в а и в-дан }
BEGIN
REPEAT
COPYRUN (С, А); { серияларды көшіру }
IF NOT EOF (С ) THEN COPYRUN (С, В) UNTIL EOF
(С) END;
PROCEDURE MERGE; { а и в в с-дан }
BEGIN
REPEAT
MERGERUN; { екі серияны біріктіру }
L := L + 1 UNTIL EOF (B);
IF NOT EOF (A) THEN BEGIN
COPYRUN (A, C); L := L + 1
END
END;
Бұндай тарату әдісі кезінде А және В файлдарында сериялардың тең
саны, немесе А файлында В файлына қарағанда бір файл артық болады деп
есептеледі. Сериялардың сәйкес жұптарын біріктіреміз де, артықтарды
көшіре саламыз.
mergerun және соруrun бағыныңқы процедуралары EOR (end of the run)
глобалды бульдік айнымалысын енгізуді талап етеді, оның мәні серияның
соңы болған, болмағанын көрсетеді.
PROCEDURE COPYRUN (VAR X, Y : TAPE);
BEGIN { х-тен у-ке бір серияны көшіру }
REPEAT
COPY(X,Y) { бір элементті көшіру }
UNTIL EOR { серияның соңы }
END;
Екінші бағыныңқы процедура PROCEDURE
MERGERUN;
BEGIN { а и в в с-тан екі серияны біріктіру }
REPEAT
IF A^KEY < B^KEY
THEN BEGIN COPY (A, C);
IF EOR THEN COPYRUN (B, C)
END
ELSE BEGIN COPY (B, C);
IF EOR THEN COPYRUN (A, C)
END
UNTIL EOR
END;
Серияларды біріктіру кезінде салыстыру процесі және кілт бойынша
таңдау екі серияның біреуі таусылған кезде аяқталады. Осыдан кейін басқа
серияның қалдығын қарапайым көшіру көмегімен шығыстық серияға көшіру
керек болады. Бұл copyrun процедурасын шақырумен жүзеге асады.
Бағыныңқы процедура copyХ файлынан Ү файлына элементті қайта
сілтейді, және серияның соңына жеткен, жетпегенін анықтайды. Бұл үшін
соңғы оқылған (қайта көшірілген) элементтің кілтін келесімен салыстыру
үшін сақтау керек. Бұл "алдыға қарау" X^ файлының буферлік айнымалысын
қолданумен жүзеге асады..
PROCEDURE COPY (VAR X, Y : ТАРЕ);
VAR BUF : ITEM;
BEGIN
READ (X, BUF); WRITE (Y, BUF);
IF EOF (X) THEN EOF := TRUE
ELSE EOF := BUF.KEY > X^.KEY
END;
Осымен табиғи біріктіру арқылы сұрыптау процедурасын құру
аяқталады.
Өкінішке орай, кейбір жағдайларда бағдарлама сұрыптауды дұрыс
жасамайды. Мысалы, бастапқы тізбек болсын:
3 2 5 11 7 13 19 17 32 31 29 37 43 41 47 59 57 61 71 67
А және В тізбекті серияларды тарата отырып, мынаны аламыз:
А= 3' 7 13 19' 29 37 43' 57 61 71'
В = 2 5 11' 17 23 31' 41 47 59' 67
Достарыңызбен бөлісу: |
