��������� ������� $n\,{\hbox{\rm log}}\,n$


$\scriptstyle{\blacktriangleright}$ 4.2.1. ���������� �������� ����������, ����� �������� �������� ���� �� ������� $n\,\log n$, �� ���� �� ������������ �� $Cn\log
n$ ��� ���������� C � ��� ���� n .

  �� ��������� ��� �������.

������� 1 (���������� ��������):

 

����� k -- ������������� ����� �����. �������� ������ ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$ �� ������� ����� k. (������ -- ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[k]}}$, ����� ${\hbox{\tt x[k+1]}}\ldots{\hbox{\tt x[2k]}}$ � ��� �����.) ��������� ������� ����� ��������, ���� n �� ������� �� k. ������� ������ k-�������������, ���� ������ �� ���� �������� � ����������� ����������. ����� ������ 1-����������. ���� ������ k-���������� � ${\hbox{\tt n}}\leqslant{\hbox{\tt k}}$, �� �� ����������.

�� ������, ��� ������������� k-������������� ������ � 2k-������������� (�� ��� �� ���������). � ������� ����� �������������� �������� ������������ ���:

 k:=1;
 {������ x �������� k-�������������}
 while k < n do begin
 | ..������������� k-������������� ������ � 2k-�������������;
 | k := 2 * k;
 end;

��������� �������������� ������� � ���,��� �� ����������� << �������>> ��� ������������� ������� ����� �� ������ k � ���� ������������� �������. ����� ��������� \begin{displaymath}
{\hbox{\tt ������� (p,q,r: integer)}}\end{displaymath}��� ${\hbox{\tt p}}\leqslant{\hbox{\tt q}}\leqslant{\hbox{\tt r}}$ ������� ������� ${\hbox{\tt x[p+1]}}\ldots{\hbox{\tt x[q]}}$${\hbox{\tt x[q+1]}}\ldots{\hbox{\tt x[r]}}$ � ������������� ������� ${\hbox{\tt x[p+1]}}\ldots{\hbox{\tt x[r]}}$ (�� ���������� ������ ������ ������� x).

\begin{displaymath}
\begin{picture}
(20,6)

\thinlines 
 
\put(1,1){\line(1,0){1...
 ...tt q}}}}
\put(17,5){\makebox(1,1){{\hbox{\tt r}}}}\end{picture}\end{displaymath}����� �������������� k-�������������� ������� � 2k-������������� �������������� ���:

  t:=0;
  {t ������ 2k ��� t = n, x[1]..x[t] ��������
   2k-�������������; ������� ������� x �� ���������}
  while t + k < n do begin
  | p := t;
  | q := t+k;
  | ...r := min (t+2*k, n); {min(a,b) - ������� �� a � b}
  | ������� (p,q,r);
  | t := r;
  end;
������� ������� ���������������� ������� ��� ������ ����������� ������� -- ��������� ��� b. ����� p0q0 ��������� ������ ��������� ��������� ��������, ������������ �������, s0 -- ��������� ���������� � ������ b �������. �� ������ ���� ������� ������������ ���� �� ���� ��������:

        b[s0+1]:=x[p0+1];
        p0:=p0+1;
        s0:=s0+1;
���
        b[s0+1]:=x[q0+1];
        q0:=q0+1;
        s0:=s0+1;
������ �������� (������ �������� �� ������� �������) ����� ������������� ��� ������������� ���������� ���� �������: (1) ������ ������� �� �������� (${\hbox{\tt p0}}<{\hbox{\tt q}}$);

(2) ������ ������� �������� (${\hbox{\tt q0}}={\hbox{\tt r}}$) ��� �� ��������, �� ������� � ��� �� ������ ���������� �������� ������� �������  [$({\hbox{\tt q0}} < {\hbox{\tt r}}$) � (${\hbox{\tt x[p0+1]}}\leqslant{\hbox{\tt x[q0+1]}}$)].

���������� ��� ������� ��������. ����, ��������

  p0 := p; q0 := q; s0 := p;
  while (p0 <> q) or (q0 <> r) do begin
  | if (p0 < q) and ((q0 = r) or ((q0 < r) and
  | |                (x[p0+1] <= x[q0+1]))) then begin
  | | b [s0+1] := x [p0+1];
  | | p0 := p0+1;
  | | s0 := s0+1;
  | end else begin
  | | {(q0 < r) and ((p0 = q) or ((p0<q) and
  | |   (x[p0+1] >= x[q0+1])))}
  | | b [s0+1] := x [q0+1];
  | | q0 := q0 + 1;
  | | s0 := s0 + 1;
  | end;
  end;
(���� ��� ������� �� ������� � ������ ����������� �������� � ��� �����, �� ��������� ��� ��������; � ��������� ������� ������.)

�������� ���� ���������� ��������� ������� ������� � ������ x.

��������� ����� ��������� ������: ��������� � �������������� ��������� ������� ��� ���������� ��������� ���������. 


������� 2 (���������� �������):

�������� << ������ �������� ������>> -- ��������, �    ������� ����� ���� ������, �� ���� ������� ������� � ��� ������, �� ������� -- � ��� ������ � ��� �����:

\begin{displaymath}
\begin{picture}
(6,5)
\put(3,1){\circle*{.15}}
\put(2,2){\ci...
 ...){.33333333}}
\put(4.5,3){\vector(1,3){.33333333}}\end{picture}\end{displaymath}

����� ��������, ��� ������� ����� << �� ����� � ��������>>: � ������� ������ ��� ���� � ���� ���� (���� ������ �� � ����� ����� ��� ����). ����������� ��� ��������, ��� ���������� ���������� ���������� ����� ���� ������� ������, � ��� ����� ��������� ���� �� ����� �������. ������� �� ����. ����� �������� ����� ������ ��� ���� �� �������: \begin{displaymath}
{\hbox{\rm ����� � ������ = ������� �� ����� � �������-��������}}\end{displaymath}��� ����� � ����� ������ (������ ������) ����� �������� ����������� ����� �� ���� �������.

������ �� ������������ ������� ����������� �������. ��� ����� ��� ���� ������� �����. ��� ����� �������, ��� �� �����: �� ���� ��������� � ���� ����, ��� �������� �� �� �����. ����� ����������� �������, ������� ��� �������� $+\infty$ � ������������� ����� ������ ����� (��� ����� ���� ����� ������ ���� � �����). ��� ���� �������, ��� $\min(t,+\infty)=t$.����� � ����� �������� ������ �� �������� �������, �� ������� ���, ������� �������������� � ����������� ������. ��� ���������� �� ������ ��� �������� � ������� �����������, ���� � ����� �� ��������� �������������.

��� ������ ����� ��������� ������� ���������� ������ ������� ${\hbox{\tt 1}},{\hbox{\tt 2}},\ldots$ -- ��� ���� ��������� ������ ����� n �������� ������ 2n${\hbox{\tt 2n}}+{\hbox{\tt 1}}$. ��������� ��������� ����� ��������� �� �������, ��������� �� ������� ����� ����������� �������, �� ��������� �������������� ������, ����� ��������� ����� ���������� (� ���������� � ������������ �������).

�� ����� ���������� ����������� ����� �� ���� �������� ������, � �� ������ �� ������� ������. ����� ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$ -- ������, ���������� ����������. ��������� ������ ����� ����� �� 1 �� n; � ����� x[i] �� ����� �������� ��� � �����, ������� � ������� i. � �������� ���������� ���������� ������ ������ ����� �����������. ����� ������ �������� ������ ����� ������� � ���������� k. ����� �������, � �������� ������ ��������� ������ ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[n]}}$������� �� ��� �����: � ${\hbox{\tt x[1]}}\ldots{\hbox{\tt x[k]}}$ �������� ����� �� ������, � � ${\hbox{\tt x[k+1]}}\ldots{\hbox{\tt x[n]}}$ �������� ��� ��������������� � ������� ����������� ����� ������� -- ��������, ��� �������� ���� �������� �����.

�� ������ ���� �������� ����� ������� ������������ ������� ������ � �������� ��� � ��������������� �����, �� �������������� � ���������� ���������� ������ �����.

����������� � ������������. ��������� ������ ��������� ����� �� 1 �� �������� �������� ���������� k. � ������ ������� s ����� ���� ������� 2s2s+1. ���� ��� ���� ����� ������ k, �� ������� ���; ����� ������� ���������� ������. ���� ${\hbox{\tt 2s}}={\hbox{\tt k}}$, �� ������� s ����� ����� ������ ���� (2s).

��� ������� s �� ${\hbox{\tt 1}}\ldots{\hbox{\tt k}}$ ���������� << ���������>> � ������ � s: ��� �������� ������� s � ���� �� �������� (�������, ������ � ��� ����� -- �� ��� ���, ���� �� �� ������ �� ������� ${\hbox{\tt 1}}\ldots{\hbox{\tt k}}$). ������� s ����� �������� ����������, ���� ������� � ��� ����� -- ������������ ������� s-���������; s-��������� ������� ����������, ���� ��� ��� ������� ���������. (� ���������, ����� ���� �������� ���������� �������������� ���������.)

����� ��������� ������:

 k:= n
 ... ������� 1-��������� ����������;
 {x[1],..,x[k] <= x[k+1] <=..<= x[n]; 1-��������� ���������,
  � ���������, x[1] - ������������ ������� ����� x[1]..x[k]}
 while k <> 1 do begin
 | ... �������� ������� x[1] � x[k];
 | k := k - 1;
 | {x[1]..x[k-1] <= x[k] <=...<= x[n]; 1-��������� ����-
 |   ����� �����, �����, ��������, ������ ����� }
 | ... ������������ ������������ 1-��������� �����
 end;
� �������� ��������������� ��������� ��� ����������� ��������� �������������� ������������ s-��������� � �����. ��� ���:
  {s-��������� ��������� �����, �����, ��������, �����}
  t := s;
  {s-��������� ��������� �����, �����, ��������, ������� t}
  while ((2*t+1 <= k) and (x[2*t+1] > x[t])) or
  |     ((2*t <= k) and (x[2*t] > x[t])) do begin
  | if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin
  | | ... �������� x[t] � x[2*t+1];
  | | t := 2*t + 1;
  | end else begin
  | | ... �������� x[t] � x[2*t];
  | | t := 2*t;
  | end;
  end;

����� ��������� � ������������ ���� ���������, ��������� �� ��� ��������������. ����� � s-��������� ��� �������, ����� ����� ��� ������� t, ���������. ���������� ������� ������� t. ��� ���������, � ������ �������� ���������� ����� � ����� �����������. ����� �������, �� ���� ����������� ����� � t-��������� ����� ������������ ����� � ����� ������� t � ����� � �� ��������. (� ������ ������ ������� t ���������, � ��� � �������.) � ���� �������� ���� ����� �������� ���:

while ���������� ����� �� � t, � � ����� �� ������� do begin
| if ��� � ������ ���� then begin
| | �������� t � �� ������ �����; t:= ������ ���
| end else begin {���������� ����� - � ����� ����}
| | �������� t � �� ����� �����; t:= ����� ���
| end
end
����� ������ ������� t ���������� ���������� (� ��� �������� ������������ ����� t-���������). �� ��������� ������� � ������ ��� �������� ����������, � ��������� ������� ����� � �� ���� ����������. � ��������� �������� s-��������� �� ���������� �� �����, �� ���������� �� �������� (����� ��� ��� �������� ��������� �������������), ��� ��� ������������ �� ����������. ��� �� ��������� ����� �������������� ��� ����, ����� ������� 1-��������� ���������� �� ��������� ������ ����������:
  k := n;
  u := n;
  {��� s-���������� � s>u ��������� }
  while u<>0 do begin
  | {u-��������� ��������� �����, ����� ����� ��� �����}
  | ... ������������ ������������ u-��������� � �����;
  | u:=u-1;
  end;

������ ������� ��������� ���������� �� ������� (�����������, ��� n -- ���������, x ����� ��� arr = array [1..n] of integer).

  procedure sort (var x: arr);
  | var u, k: integer;
  | procedure exchange(i, j: integer);
  | | var tmp: integer;
  | | begin
  | | tmp  := x[i];
  | | x[i] := x[j];
  | | x[j] := tmp;
  | end;
  | procedure restore (s: integer);
  | | var t: integer;
  | | begin
  | | t:=s;
  | | while ((2*t+1 <= k) and (x[2*t+1] > x[t])) or
  | | |     ((2*t <= k) and (x[2*t] > x[t])) do begin
  | | | if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin
  | | | | exchange (t, 2*t+1);
  | | | | t := 2*t+1;
  | | | end else begin
  | | | | exchange (t, 2*t);
  | | | | t := 2*t;
  | | | end;
  | | end;
  | end;
  begin
  | k:=n;
  | u:=n;
  | while u <> 0 do begin
  | | restore (u);
  | | u := u - 1;
  | end;
  | while k <> 1 do begin
  | | exchange (1, k);
  | | k := k - 1;
  | | restore (1);
  | end;
  end;`


��������� ���������

�����, �������������� ��� ���������� �������, ������ �������� � ������ ������. (��. � ����� 6 (� ����� ������) �� ������� � ������������.)

���������� �������� ������ ���, ��� ��� �� �������, �����  ���� ����������� ������ ��������� � ����������� ������. ����� ������� ������������� ����� �����, ������� ���������� � ������ (��������, � ������� ������), � ����� ������� ���������� �����.

��� ���� ����������� ������ �������� ���������� (������� ���������� �����) �����:   ����� ������������� ������, ������� ��������� ��� ������� b , � �������� ������ �� ��� �����: ������� b , ������ b � ������� b . (��� ������ ��������� � ����� 1.) ������ �������� ������������� ������ � ������ �����: ��� �������� ��� �� ��������. ����� ������ ����� ��������� -- ��������� ��������; ����� ��������, ��� � ������� �� �������� �� ������ $Cn\log
n$.�� �������� -- �� ���� �� ����� �������. (�� ��� �������� � ����, ������� ��� ����������� � ������������� ����������.)

�������, �������, ��� ���������� �� ����� ������� $Cn\log
n$����� ���� ��������� � ������� ������� ���������������� �������� (��. ����� 12), ������ ��������� ��� ������� � ��������� C �������� ������.



pvv
1/8/1999