\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=2

\subsubchap{񎐒������ ����������� ������}
噅 ���� ������ ��������� ������� ���������� �������� �� ���� 
������������� ������. ⅐�����, ���������� ���������� ����������� ������ 
�������� � ����������:

\medskip
\item{i)} 퀉�� ���������� ����; ��������� ��������������� ������ � 
������� ������ � �������� ���� ��������� "$\infty$" (������� �� 
������������� ������ ������ ��������� �����).

\item{ii)} ������ ��� (i). � ���� ��� ����� ������ ����,
���������� �� ����������, ��� ��� ����� ���������� ���� ��� ������� 
�� $\infty$.

\item{iii)} ������ ��� (i) �� ��� ���, ���� �� ����� ������� $N$ �������.
\medskip

\noindent
瀌����, ��� ���� ����� ������� ������� ���� �������� ��������� �� 
������ ����������, � �������� ������ �� ��������� ���������������, ���� �� 
������. ꀐ����, �� ��������, �������������� ������ �������, � ������� 
�������� �������� ������ ��������� ���������������, �� ������ �� 
���������� ���������� ������ �� �������� �� ������������� ������.

� �������������� ����� (��������, ������ � ����������� ���������� 
�������) ����� ���������� ������� "����� ���������� �������", ������� 
����������� � ������� ���������. � ����� ������� ���������� ��������� 
������� �������� ��������������, ���� ������ $N$ �� ������� ������.

������ ����� ������� $N-1$ ��������� ������ ���, ����� ���������� 
��������� ������; �� ����� ������� ��������� ������� ������ � ������. 
茅���� ��������� ������ ��������� ��������� ��������, ������� ��� ���� 
������������� $\infty$: ��������� �������� ����� ���������� � 
��������������� �������, � ������, ������� �� ��������, ���������� 
�� ����� ���������. 򎃄� ��� ������� �� ����� ������������� ����� ��� 
����������� �������. � ���� ���� ������� ��� ������ �������� ���������� 
����������� ������.

\alg S.(񎐒������ ����������� �������� ������.) 瀏��� $R_1$,~\dots, 
$R_N$ ��������������� �� ��� �� �����. �� ���������� ���������� �� 
����� ����� �����������: $K_1\le \ldots\le K_N$. 񎐒������ �������� �� 
��������� ���� ������, ���� �� ������� ����, ��� �����, ������, 
�����������, �������� ������� \emph{����������} �������, ����� ������ �� 
�������� � �. �.

\st[���� �� $j$.] ⛏������ ���� \stp{2} � \stp{3} ��� $j=N$, $N-1$, \dots, 2.
%% 170 

\st[퀉��~$\max(K_1,~\ldots, K_j)$.] 퀉�� ���������� �� ������~$K_j$, 
$K_{j-1}$,~\dots, $K_1$; ����� ��� �����~$K_i$.

\st[����� ������� �~$R_j$.] ⇀����������� ������~$R_i\xchg R_j$. 
(򅏅�� ������~$R_j$,~\dots, $R_N$ �������� ���� ������������� �������.)
\algend
\picture{���. ~21. 񎐒������ ������� �������.}

� ����.~1 �������� �������� ����� ��������� �� ����������� ������, 
��������� ���� ��� ��������; ��������, ������������ �� ��, ����� 
��������� ������������� �� ����� ������ � ����~S2, �������� ������ �������.

{\catcode`\!=\active\def!#1.{{\bf #1}}
\htable{򀁋��� 1}%
{񎐒������ ����������� �������� ������}%
{\strut\hfil$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr
503 & 087 & 512 & 061 &!908.& 170 &!897.& 275 & 653 & 426 & 154 & 509 & 612 & 677 &!765.&!703.\cr
503 & 087 & 512 & 061 & 703 & 170 &!897.& 275 & 653 & 426 & 154 & 509 & 612 & 677 &!765.& 908 \cr
503 & 087 & 512 & 061 & 703 & 170 &!765.& 275 & 653 & 426 & 154 & 509 & 612 &!677.& 897 & 908 \cr
503 & 087 & 512 & 061 &!703.& 170 &!677.& 275 &!653.& 426 & 154 & 509 &!612.& 765 & 897 & 908 \cr
503 & 087 & 512 & 061 & 612 & 170 &!677.& 275 &!653.& 426 & 154 &!509.& 703 & 765 & 897 & 908 \cr
503 & 087 & 512 & 061 & 612 & 170 & 509 & 275 &!653.&!426.&!154.& 677 & 703 & 765 & 897 & 908 \cr
\ldots\cr
061 &!087.& 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
}}

񎎒����������� \MIX-��������� �������� ������.

\prog S.(񎐒������ ����������� �������� ������.)
ꀊ � � ���������� ���������� ���� �����, ������, ����������� � ������� 
��~$|INPUT|+1$ ��~$|INPUT|+N$, ����������� �� ��� �� ����� �� �����, 
����������� ������ �����. 獀����� ���������: $|rA|\equiv \hbox{������� 
��������}$, $|rI1|\equiv j-1$, $|rI2|\equiv k$ (������ ��� ������), 
$|rI3|\equiv i$. �����������, ���~$N\ge 2$.
\code
START & ENT1 & N-1      & 1   & S1. ���� ��~$j$. $j\asg N$.
2H    & ENT2 & 0,1      & N-1 & S2. 퀉��~$\max(K_1, \ldots, K_j)$. $k\asg j-1$.
      & ENT3 & 1,1      & N-1 & $i\asg j$.
      & LDA  & INPUT,3  & N-1 & $|rA|\asg K_i$.
8H    & CMPA & INPUT,2  & A
      & JGE  & *+3      & A   & ����, ����~$K_i\ge K_k$.
      & ENT3 & 0,2      & B   & � ��������� ������ ����������~$i\asg k$,
%% 171
      & LDA  & INPUT, 3 & B   & $|rA|\asg K_i$.
      & DEC2 & 1        & A   & $k\asg k-1$.
      & J2P  & 8B       & A   & ������, ����~$k>0$.
      & LDX  & INPUT+1,1& N-1 & S3. ����� ������� �~$R_j$.
      & STX  & INPUT,3  & N-1 & $R_i\asg R_j$.
      & STA  & INPUT+1,1& N-1 & $R_j\asg |rA|$.
      & DEC1 & 1        & N-1 
      & J1P  & 2B       & N-1 & $N\ge j \ge 2$.
\endcode
\progend
␅�� ������ ���� ��������� ������� �� ����� ���������~$N$, ����� 
���������~$A$ � ����� "�������������� ����������"~$B$. 텒����� ������, 
��� ���������� �� �������� �������� ������
$$
A=\perm{N}{2}={1\over 2}N(N-1).
\eqno(1)
$$
񋅄���������, ���������� �������� ������ ��������~$B$. 텑����� �� ��� 
������������� �������� ������, �� ��� ����� ���������� ������ ������ 
��������~$B$. � ���. �~3 ��~6 ��������, ���
$$
B=(\min 0, \ave (N+1)H_n-2N, \max \floor{N^2/4});
\eqno(2)
$$
� ���� ������ �������� ���������� ����������� ������������ �������� 
(����������� ���������� ��������~$B$ �� ��� ��� �� ����������).

򀊈� �������, ������� ����� ������ ���������~S 
����� $2.5N^2+3(N+1)H_N+3.5N-11$~������, �.~�.\ ��� ���� �������� 
��������� ������� ������� (���������~5.2.1S). 荒������ �������� 
��������~S � ����������� ������� �������� (��������~5.2.2�), ��� ��� ����� 
�������� ����� ������������� ��� �������� ������, � ������� ������ 
���������� ����� ������ �������� �� ���. � ���� ������� ��� ���������� 
������� �������� ������������ ������ ���������, ��� ��� ������� ������, � 
���, ��� ����� ����������, ����������������. � � ���������������� 
���������~5.2.2� ����� ��� ����� ��������� ���������~S! 񎐒������ ������� 
�������� ����������� ��-�� ����, ��� � ��� ����������� ������� ����� 
�������, � �� ����� ��� ��� ���������� ������� ������� ������������ ����� ����
��������� ������.

\section 󑎂�������������� �������� ������. 񓙅������ �� �����-������ 
������ �������� ����� ������, ������������ � ���������~S? ⎇���� � 
������� ����� ��������� � ����~S2: �������� �� ����������� ����� ������� 
������ ���������� ���������? �� �� ���� ������---\emph{���!}

\proclaim 녌��~M. � ����� ��������� ���������� ��������� �� 
$n$~���������, ���������� �� ��������� ��� ���������, 
���������� ��������� �� ������� ���� $n-1$~���������.

%%172 

\proof 呋� ����������� ����� $n-1$ ���������, �� �������� �� ������� ���� 
��� ��������, ��� ������� �� ���� ���������� �� ������ ��������, 
�������������� �� �� ��������. 񋅄���������, �� ��� � �� ������, 
������� �� ���� ���� ��������� ������, �, ������, �� ������ ���������� ��������.
\proofend

򀊈� �������, ������� ������, � ������� ������������ ���������� �������, 
������ �������� �� ����� ��� �� $n-1$ �����. ����� �� ���, ��� ��� ���� 
������� ����������, ���������� �� $n$ ��������� �������, ����� ����� 
��������� ����� ������� $n^2$? � �������, ����� M ��������� ������ � 
\emph{�������} ���� ������; ��� ����������� ������� ����� 
������������ ����������� ����� ����������. 퀏�����, � ���.~8 ��������,
 ��� ������������ ������� ��������� ���������~S ���������� ��������� ����� ���������.

���������� 16 �����, �������������� � 1-� ������ � ����.~1. � �� 
�������� ���������� ����� ��� ����������� 
�������---������� ��� ����� �� ������ ������ �� ������ �����. 퀗��� ����� � 
����������� �����������, �������� ������ ������, � ������ �������������� � ������
$$
512, 908, 653, 765;
$$
����� ���������� �� ���� ������� ��������� 908 � ����� ���������� �� 
���� �����. ����� �������� ������ �� �������� �������, ���������� 
����������� ������� ��������� ��� �������� ������, ���������� 908; 
���������� �� $\{170, 897, 275\}$ ����� 897, � ����� ���������� �����
$$
512, 897, 653, 765
$$
��� 897. ����������, ��� ���� ����� �������� ������ �� �������� �������, 
���������� ���������� �� $\{170, 275\}$, � ����� ���������� ��
$$
512, 275, 653, 765
$$
� �. �. ꀆ��� �����, ����� �������, ������� �� ����� 6 �������������� 
���������. ⎎���, ���� $N$---������ �������, �� ����� ��������� ���� �� 
$\sqrt N$ ����� �� $\sqrt N$ ��������� � ������;
����� �����, ����� �������, ������� �� ����� ��� $\sqrt{N}-1$ ��������� 
������ ������ ����� ���������� �������� ���� $\sqrt{N}-1$ ��������� ����� 
"������� �����". ���� ����� ������� �������� "������������ �����"; ����� 
����� ������ ��� ���� ���� $O(N\sqrt{N})$, ��� ����������� �����, ��� $O(N^2)$.

셒�� ������������� ������ ������� ����������� 
�.~X.~������� [{\sl JACM\/}, {\bf 3} (1956), 152--154]; �� ������, ��� ��� 
���� ����� ��������, ������� � ���������� ����� ����������� ������,
������ ��������� ������� � �. �. 퀏�����, ����� �����������
%%173
������ ������� � ���, ����� ��������� ���� �� $\root 3\of N$ ������� �����,
 ������ �� ������� �������� �� $\root 3\of N$ ����� ����� �� $\root 3\of 
N$ �������; ����� ������ ��������������� $N\root 3\of N$. 呋� ������� 
��� ���� �� �� ������� ����������, �� �� ������ � ����, ��� ����� ������ 
"����� $n$-� �������", ���������� �� ��������� ��������� ������. ␅�� 
������ ����� ������ ��������������� $N \log N$; �� ����� �������� ��� 
\dfn{������� �� ������}.
\section ⛁�� �� ������. ����� ���������� ����������� ������ �� ������ 
����� ����� ����������, ���� ��������������� ��������� � �������� 
"�������� � ����������". ����������, ��������, ���������� ������������ 
�� ����������� �������, ���������� �� ���.~22. 䆈� ��������� 䎍�, � 
䆎 ��������� 䆅��; ����� � ��������� ���� 䆎 ���������� � 䆈�� � �. �.

� ���.~22 ��������, ��� 䆎---������� ����� ������ �����������, � ��� 
����, ����� ���������� ���, ������������� $8-1=7$ ������ (�. �. ���������).
 䈊 ����� �� ����������� ����� ������ �� ���� �������: ����� �� 
�����������, � ������� ������� 䆎, ������� ���� ������������ � ������ 
���� 䆅��, ��� �� ��������� ������ �� ���� �������. ⒎���� ������ ����� 
����������, �������� 䆅�� ������� � 䆈���, � ���������� ����� �����---� 
䈊��; ����� ��� �������������� ����� ��������� ��� ����������� ������� �� 
���� ������, ������ �� ���� ����������� ���, ������� �� ��������� �� 
���������� ���.

⎎��� ����� "�������" ������, ������������ � ����� ������, � �������� ��� 
����������� ������ �������. �������� ����� ������� ������ ��������, 
��� ������������� ������ �� ���� ��������� ������ ������ ���������, � 
������ �� �������� � �����, ���� ����� ��������� ����������� � 
������� ������� ������. 䋟 ����� ����� �������� ���� ���� ����, � ������, 
��� ��� ��� ������ ���������� �� ���� ������ ���������� ����� $\lceil 
\log_2 N\rceil$) �������������� ���������. 񓌌�����
%%174
\picture{���. 23. ��� ���������� ����������� ������ �� ������...}
%% 175
����� ���������� ����� ���������� ����������� ������ �������� 
��������������� $N\log N$.

� ���.~23 ���������� ����������� ������ �� ������ ������������ ���� 16 
�����. 瀌����, ��� ��� ����, ����� �����, ���� ��������� ��������� 
������� "$-\infty$", ���������� �������, ������ ������ ����, ����������� � 
�����. ���� ���� ������������ � ���������������� �������� ��������� 
��� �������, ����������� ������� �����, � �� ��� ����. ��� �������, ��� 
���������� ������ ��� $N$ �������� �������, $N-1$ ����-���������� � $N$ 
��������� �������. (����������, ���� �����
\picture{���. 24.  ������� ������������� ������� ���������� � 
����������. ꀆ��� ����������� �� ���� ������� ���������������� � ��������.}
���� �� ����� ��� �� ����, �� �� ����� ��������� ��������� ������ � 
����������� ������.)

����� ������� �� ������������� ������������������, ������� �� ���������� 
��������, � ���� ����� ������� �������� ������ �� ��� ���, ���� �� �� 
��������� � ������� �� ������ ���� �� ���������, ��� ������� ���.~10 �� 
�������� ��� ��� �������� �����.

� �� ����������� ������ �� ������, ���������, �� ��������, 
�.~�.~���������� [A Programming Language (Wiley, 1962), 223--227], 
��������� ������������� ����������, ��������� ������� ����������� 
"������������ ������": ����� ���������� ����� �� ������ ������ ����������� 
�����, �� �� ������ ������ ��� ����� �� ����� �������� �� "$-\infty$"; 
����� �� ���������� ������������ ����� � ������ ������������ �� ������,
 �� ��� ����� �������� �������, ������� � ����� ������ ��� ����� ������ 
���������, �� ��� ������� ����� (� ������ ���������� �� ���� ������, 
������������� ��� ���). ⛏����� ��� �������� ������� ���, ������� 
��������, ������ �� ���.~23(�) � ���.~24.

ꎋ� ����� ������ ��������� ����� �������, ����� ���������� ���������� 
�� "����������" �������, ���������� �� ���.~23, � "����������": ��������� 
�������, �����������
%% 176
� �����, ������������ ����� ���������� �� ��� ��������, ������������ ����� 
���������� �� �������� ���������� � �. �. ���� �������� �������� �� 
������� �� ������ �� ����������� �������, ������� �� ������������� ������� ����������.

�������� ������ �������, ��� � ����������� ������ ���� ������ 
�����������---�� ��������� �������� ������ ��������� $-\infty$ �~$-\infty$. 
(������ ���������� �������, �� �� ����� ������� ������� ���������� 
����� ���������� �� $-\infty$, � ��� ���������� ������ ����� �� ������ 
������ ����������� �������������� ������ ����� �� ����� ��������� $-\infty$.)
\picture{���. 25. ������������� ������������� ������ ��� 
������� ��������� ������.}

� ���.~23 �~24 ���������� \emph{������ �������� �������} � 16 ��������� 
������ (��. � �.~2.3.4.5); ����� ������� ������ ������� � 
���������������� ������� ������, ��� �������� �� ���.~25. 瀌����, ��� 
����� ���� ����� $k$ �������� ���� $\lfloor k/2\rfloor$ , � ��� ��������� 
�������� ���� $2k$ � $2k+1$. ��� �������� ��� ���� ������������ 
����������� ������, ��������� �������� ����������� ����� ������������ ���� 
�� ���� $k$ � ����� $2k$ �~$2k+1$, ��� ����� �� ���� $k$ � ����� $k\oplus 
1$ 
�~$\lfloor k/2\rfloor$. (焅�� ����� $k\oplus 1$ ���������� ����� $k+1$ 
��� $k-1$ � ����������� ��  ����, �������� �� $k$ ������ ��� ��������.)

� ��� ��� � ����� �������� ������ �� ������ � ��� ��� ���� ���� 
��������������, ��� $N$ ���� ������� 2; � ���������������� ����� 
�������� � ������������ ��������� $N$, ��� ��� ������ �������� ������ � 
$N$ ��������� ������ �������� ��������� ��� ������ N. 

 � ������� ������ � ��������� �������: ������ �� � ���������� ������ 
�������� ������ ��� "$-\infty$"? � ������ ��, ���� �� �������, ���� �� 
��� ������������ ����������, ��������� �� ���.~24, ������� ����������� � 
������� 1--16
%%177
������� ��������� ������ ��� ������ ����������� "���", ���������� 
$-\infty$? ��������, ����� ������ � ������, ��� ��� ���� � 
���������������� ���������, ������ �� ������ ����������� $-\infty$, �� � 
���������� ����������� ����������� $N$ ������� �� ��� �� ����� ��� 
��������������� ������� ������. ��� �������� � ��� ������ ������� 
��������� ����������. 僎 ����� �.~�.~�.~󈋜��� [{\sl CACM\/}, {\bf 7} 
(1964), 347--348] �������� ���� �������� "������������� �����������" ("heapsort").

\section ���������� ����������.  ᓄ�� �������� ���� ������ $K_1$, 
$K_2$, \dots, $K_N$ "���������", ����
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ ��� $1\le \lfloor j/2\rfloor<j\le N$.}
\eqno(3)
$$
� ���� ������ $K_1\ge K_2$, $K_1\ge K_3$, $K_2\ge K_4$ � �.�.; ������ ��� 
������� ����������� �� ���.~24. � ���� �������, � ���������, ��� 
���������� ���� ����������� "�� ������� ��������":
$$
K_1=\max(K_1, K_2, \ldots, K_N).
\eqno(4)
$$
呋� �� �� ������ ���-������ ������������� ������������ �������� ���� � 
��������, �� ��� ��������� ������������ ��������� ���������� ����� ���� �� 
��������������� "����������" ���������� ������, �������� ���, ������� 
������� ����.

����������� ������ � ������ ���������� �������� ��������� �.~�.~􋎉� 
[{\sl CACM\/}, {\bf 7} (1964), 701]. �� ��� ������� ����������� ���� 
����� �������, ���
$$
K_{\lfloor j/2\rfloor}\ge K_j \rem{ ��� $l < \lfloor j/2\rfloor<j\le N$,}
\eqno(5)
$$
��� $l$---��������� ����� $\ge1$. (� �������� ����� ��� ������� ����������� 
"�������������" ��� $l=\floor{N/2}$, ��������� �� ���� ������ $j$ �� 
������������� ������� $\floor{N/2}<\floor{j/2}<j\le N$.) 
텒����� ������, ���, ������� ���� ��������� � ������ � ���� $l$, 
������������� ����, ����� �������������� ����������� (5) � �� ������, 
����� $\floor{j/2}=l$. 񋅄���������, ����� ��������� $l$ �� �������, ���� � 
����� ������ �� ����� ���������� ������� (3). ��� ���� 󈋜���� � 􋎉�� 
�������� � �������� ���������, ������� ����������� ������������ ��������.

\alg H.(���������� ����������.) 瀏��� $R_1$, \dots, 
$R_N$ ��������������� �� ��� �� �����; ����� ���������� ���������� �� 
����� ����� �����������: $K_1\le \ldots \le K_N$. 񍀗��� 
���� ��������������� � ��������, ����� ���� ������� �������� ����������� 
����������� � ������������ �� ���� ������������� �����. �����������, 
��� $N\ge2$.
\st[퀗������ ���������.] 󑒀������ $l\asg\floor{N/2}+1$, $r\asg N$.
\st[󌅍����� $l$ ���~$r$.] 呋�. $l>1$, �� ���������� $l\asg l-1$, $R\asg 
R_l$, $K\asg K_l$. (呋�  $l>1$, ��� ��������, ��� ����������
%% 178
������� �������������� ��������� ����� � ��������; ���� �� $l= 1$, �� ��� 
������, ��� ����� $K_1$, $K_2$, \dots, $K_r$ ��� �������� ��������.) � 
��������� ������ ���������� $R\asg R_r$, $K\asg K_r$, $R_r\asg R_1$  � 
$r\asg r-1$; ���� � ���������� ���������, ��� $r=1$, �� ���������� 
$R_1\asg R$ � ��������� ������ ���������.

\st[���������� � "�������������".] 󑒀������ $j\asg l$. 
(� ����� �������
$$
K_\floor{j/2}\ge K_j \rem{��� $l<\floor{j/2}<j\le r$,}
\eqno(6)
$$
� ������ $R_k$, $r<k\le N$, �������� ���� ������������� �����. ���� 
\stp{3}--\stp{8} ���������� ���������� "�������������"; ��
\picture{���. 26. ���������� ����������; ��������� ������� �������� "�������������".}
�������� ������������ ��������� $R_l\asg R$ � ����������� ������������ 
������� $R_l$, \dots, $R_r$ ����� �������, ����� ������� (6) ����������� � 
��� $\floor{j/2}=l$.)

\st[��������� ����.] 󑒀������ $i\asg j$ � $j\asg 2j$. (� ����������� 
����� $i = \floor{j/2}$.) 呋� $j< r$, �� ������� � ���� \stp{5};
���� $j=r$, �� ������� � ���� \stp{6}; ���� �� $j>r$, �� ������� � ���� \stp{8}.

\st[퀉�� "��������" ����.] 呋� $K_j<K_{j+1}$, �� ����������
$j\asg j+1$.

\st[ᎋ��� $K$?] 呋� $K\ge K_j$, �� ������� � ���� \stp{8}. 
\st[���� ��� �����.] 󑒀������ $R_i\asg R_j$ � ������������
� ���� \stp{4}.

\st[瀍���� $R$.] 󑒀������ $R_i\asg R$. (� ���� �������� 
"�������������", ������� � ���� \stp{�}, �������������.) ⎇��������� 
� ���� \stp{2}.
\algend
%%179
\bye



