4.2.1. ���������� �������� ����������, ����� �������� ��������
���� �� �������
, �� ���� �� ������������ ��
��� ���������� C � ��� ���� n .
����� k -- ������������� ����� �����. �������� ������
�� ������� ����� k. (������ --
, �����
�
��� �����.) ��������� ������� ����� ��������, ���� n �� �������
�� k. ������� ������ k-�������������, ���� ������ ��
���� �������� � �����������
����������. ����� ������ 1-����������. ����
������ k-���������� �
, �� �� ����������.
�� ������, ��� ������������� k-������������� ������ � 2k-������������� (�� ��� �� ���������). � ������� ����� �������������� �������� ������������ ���:
k:=1; {������ x �������� k-�������������} while k < n do begin | ..������������� k-������������� ������ � 2k-�������������; | k := 2 * k; end;
��������� �������������� ������� � ���,��� �� �����������
<< �������>> ��� ������������� ������� ����� �� ������ k �
���� ������������� �������. ����� ���������
���
������� �������
�
�
������������� �������
(�� ����������
������ ������ ������� x).
����� �������������� 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. ����� p0 � q0 ��������� ������ ��������� ��������� ��������, ������������ �������, 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) ������ ������� �� �������� (
(2) ������ ������� �������� () ��� ��
��������, �� ������� � ��� �� ������ ���������� �������� �������
������� [
) �
(
)].
���������� ��� ������� ��������. ����, ��������
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.
��������� ����� ��������� ������: ��������� � �������������� ��������� ������� ��� ���������� ��������� ���������.
�������� << ������ �������� ������>> -- ��������, � ������� ����� ���� ������, �� ���� ������� ������� � ��� ������, �� ������� -- � ��� ������ � ��� �����:
����� ��������, ��� ������� ����� << �� ����� �
��������>>: � ������� ������ ��� ���� � ���� ���� (���� ������
�� � ����� ����� ��� ����).
����������� ��� ��������, ��� ���������� ����������
���������� ����� ���� ������� ������, � ��� ����� ��������� ����
�� ����� �������. ������� �� ����. ����� �������� ����� ������
��� ���� �� �������:
��� ����� � ����� ������ (������ ������) ����� ��������
����������� ����� �� ���� �������.
������ �� ������������ ������� ����������� �������. ���
����� ��� ���� ������� �����. ��� ����� �������, ��� �� �����:
�� ���� ��������� � ���� ����, ��� �������� �� �� �����. �����
����������� �������, ������� ��� �������� �
������������� ����� ������ ����� (��� ����� ���� ����� ������
���� � �����). ��� ���� �������, ���
.����� � ����� �������� ������ �� ��������
�������, �� ������� ���, ������� �������������� � �����������
������. ��� ���������� �� ������ ��� �������� � �������
�����������, ���� � ����� �� ��������� �������������.
��� ������ ����� ��������� ������� ���������� ������
������� -- ��� ����
��������� ������ ����� n
�������� ������ 2n �
. ��������� ���������
����� ��������� �� �������, ��������� �� ������� �����
����������� �������, �� ��������� �������������� ������, �����
��������� ����� ���������� (� ���������� � ������������ �������).
�� ����� ���������� ����������� ����� �� ���� ��������
������, � �� ������ �� ������� ������. �����
-- ������, ���������� ����������.
��������� ������ ����� ����� �� 1 �� n; � ����� x[i] �� �����
�������� ��� � �����, ������� � ������� i. � �������� ����������
���������� ������ ������ ����� �����������. ����� ������
�������� ������ ����� ������� � ���������� k. ����� �������, �
�������� ������ ��������� ������
������� �� ��� �����: �
�������� �����
�� ������, � �
�������� ���
��������������� � ������� ����������� ����� ������� -- ��������,
��� �������� ���� �������� �����.
�� ������ ���� �������� ����� ������� ������������ ������� ������ � �������� ��� � ��������������� �����, �� �������������� � ���������� ���������� ������ �����.
����������� � ������������. ��������� ������ ���������
����� �� 1 �� �������� �������� ���������� k. � ������
������� s ����� ���� ������� 2s � 2s+1. ���� ���
���� ����� ������ k, �� ������� ���; ����� �������
���������� ������. ���� , �� ������� s �����
����� ������ ���� (2s).
��� ������� s �� ����������
<< ���������>> � ������ � s: ��� �������� ������� s �
���� �� �������� (�������, ������ � ��� ����� -- ��
��� ���, ���� �� �� ������ �� �������
).
������� 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.) ������ ��������
������������� ������ � ������ �����: ��� �������� ��� ��
��������. ����� ������ ����� ��������� -- ��������� ��������;
����� ��������, ��� � ������� �� �������� �� ������ .�� �������� -- �� ���� �� ����� �������. (�� ��� �������� � ����,
������� ��� ����������� � ������������� ����������.)
�������, �������, ��� ���������� �� ����� ������� ����� ���� ��������� � ������� ������� ���������������� ��������
(��. ����� 12), ������ ��������� ��� ������� �
��������� C �������� ������.