��������� ����������������, ��� 3. ���������� � �����

2-� �������
������� �. ����

The Art of Computer Programming, vol.3. Sorting and Searching, 2-ed
Donald E. Knuth
����� ��������� ����������������, ��� 3. ���������� � �����, 2-� �������

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

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


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

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

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

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


824 ���., � ��.; ISBN 978-5-8459-0082-1, 0-201-89685-0; ������ 70x100/16; ������� ����������������2013, 4 ��.; �������.



����������� �����? �������������� � ������� � ��������:







�����, ������������� ������ � ���� ������:

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



���������� ����� "��������� ����������������, ��� 3. ���������� � �����"

����������� ����������� � ����� ��������� ����������������, ��� 3. ���������� � �����

����� 5. ����������
5.1. ������������� �������� ������������ 5.1. ������������� �������� ������������
5.1.1. ��������
5.1.2. ������������ ���������������
5.1.3. �����
5.1.4. ��������� � ���������

5.2. ���������� ����������
5.2.1. ���������� ����� �������
5.2.2. �������� ����������
5.2.3. ���������� ����������� ������
5.2.4. ���������� ������� �������
5.2.5. ���������� ������� �������������

5.3. ����������� ����������
5.3.1. ���������� � ����������� ������ ���������
5.3.2. ������� � ����������� ������ ���������
5.3.3. ����� � ����������� ������ ���������
5.3.4. ���� ����������

5.4. ������� ����������
5.4.1. ������������ ������� � ����� � ����������
5.4.2. ����������� �������
5.4.3. ��������� �������
5.4.4. ������ ����� � �������� �����������
5.4.5. ������������� ����������
5.4.6. ������������ ���������� ������� �� ������
5.4.7. ������� ����������� ����������
5.4.8. ���������� � ����� �������
5.4.9. ����� � ��������

5.5. ������. ������� � ������������

����� 6. �����
6.1. ���������������� �����

6.2. ����� ����� ��������� ������
6.2.1. ����� � ������������� �������
6.2.2. ����� �� ��������� ������
6.2.3. ���������������� �������
6.2.4. ���������������� �������

6.3. �������� �����

6.4. �����������

6.5. ������� �� ��������� ������

������ � �����������
���������� �. ������� �������� ��������� ��������
�.1. �������� ��������� (����������)
�.2. �������� ��������� (������������)
�.�. �������� ������������� �����, ����� ����� ��� � ����� ���������
���������� �. �������� �����������


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

�� ������� ����� ������������ ���������� ���������� ��������� ����, ��������������� ��� �������� �������� ���������� � ������������ ��� ����������������. �� �������� �����, � ��� � ������������ ������� ����������� ����� �����. ������ ����� ��� ���� ������ �����. ��� ���������� "��������� ����������������" �. �. �����, ������� ����� ��� ������ �����������, ������ � ������� ���� ������� ���������� �� ����������� � �������� ���������� ������ ����������� ��� ����, ��� ������ � �����������������.

�� ��� �������� ����� �������� ����� � ���, ��� ��� ������������� �� ������� ��� �������� ������� ����������������, ������� ��� ��������, ���� ��� ��������, "���������" ����������������, ���������� ����� �������� ������������������ �������� �, ��� ����� �������, ���� �������������� �������� ��� �������.

�� ��� ���� �� ������, ��� ���� ������������ �������� ������ �� �������� ����������������������� ������������ � ����. ��� �������� ������������ �� ������� ������������� ����� ���������������� � �����������, ������� ������ ������������ ����� � ������������ ��������������� ����� ������������ ����. ��� ���������� ������ ������ � ����������� ������ ���������� ������������� ������� �� ������� ����� ����, ���������� �������� ������� ���������� � ���� �������. ���������� "��������� ����������������" �. �. ����� � ���� �� ����� ����.

�� �������� ���, ��� ���������� �������������, ��������������, ���������, ���������������� � ������ ������ ���������� ���� ������������ ������ � ��� ��� ����� �� ������ ���� ����� � ������������ ����� ��������� ��������� ����� ������������ ����. �� ������� ��������, ��� ����� "��������� ����������������" �. �. ����� �������� ���������� �������� � ������������. ��������, ���� ������� �� ������� ����� ���� ������������� ����� ��� ��� ����������, ��� �������� �������� � ������ �� ����������.

� ������ ������, �������� ����������, ������� �������, ��������

� ����� "��������� ����������������"

� ������ ����� ���� ������. ���� ���������� ��������� � ��� �� ��������� �������� � ������ �������, ���������� ����� �� ������ ���������. ������ � ������������ ������ ���������� ������� � ������ ����� ������������, ���� �� �� ����� �� �������� ����� �����������. ������, ���������� ��� ��������, ��������� ������ ������� �� ��������������� �������� ��������. ����, ����������� � ��������� ���������, �� ��� �� � �����. �� ����� � ���� � ������ ��������. �������� ����, ���������� ����������, �� ����� ��������� � ���������� ��������� ������������ �� ��������. ������ � ����� ������ ��������� ������������ �������� ����������� ���� ���������� ������������� ������� �������� ������ ����� "��������� ����������������"

������ ����� 30 ��� �� ������� ������� ������� � 1972 ���� � ��� ���� �����. ��� ���� ���������� �� ����������� ������ ����, � ��� ����� � �� �������. � ���������� ������� �� ���������� ����� ��� ���������� �. �. ����� ���� ����������������� ���������. � 1998 ���� � ��� ����� ������ ������� "��������� ����������������" � ��� ��������� ������������������ ��������� ��������� ������� ������, �� ����������� �������� ������ ������, � ������� �������� ������ � �������� ������ ����������, ��������� ����� ���������� � �����������, ��������� ����������. �������� ������������ �� ���� ���� "��������� ����������������", ����� ��������� ������� ��������� ������ ����������� ������� �� ������� �����, ������� �� � ������� � �����.

� ��� �� ����� "��������� ����������������" �. �. �����?

��-������, ��� ����� � ������������ ������� ������� �� ����������� � ������� ������������ ����������. �� ������� ����� ���� �������� �� ������ ��������������� ����� �� ����������� ����������������, ������ ����������, ���������� ����������. ����� ����� ������� � ��������� ������� �������, �������� � �������� ����������������. � �������� ��������� ����� ������ ���������� ����� ������ ���� �������� ������ ��������������� �������������� ���������� MIX. ��� ��������� ������� ����������� ��������� � ������ ������������ �������������� �����. ��������� MIX-��������� �� �������� ��� ��� ���������� �� �� ������ �������� ������ �� ���������� ������� �����. ������ ������ �������� ����� ������ ���������� �������� ����-�������.

��-������, ��������� ����������� ��������, �������� � �����, �������� � ���� �������� ��������������� ������ ����������, ������� � ��� ��� ���� ���� �������� ����� ����������� � �������� ����������������.

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

�-���������, ������� �������� ���������� ���������. ����� ���������� �� ������� ���� ��������� � �� ���������� ��������� �� �������������-��������������. ������� ����� ��������� ������� ������������ ��������� �� ����� ������. �������� ��������������. ��� ��������� ���� ������� �� ��������� ������ ������ �������� ���������� ��� ����������� ���������� ����������������. �������������� ������������ "�����������" ���������� ��������� ���������� (���� � �. �. ����� ���� ��������� �����, �� ������� �� ������).

������ ������������ ������ "��������� ����������������" ����� ����� ����������.

����� ���� ����� ��������� ���� "��������� ����������������" � ��������� ���������� ����� � 1976-1977 ����� �� ����� ���������� � ������������ ������������. ����� ������������� ��������������� ������ ���������� ����������������, � ������� ������� ����� �. �. ����. ���� ����� ����������, ���������, ���������� ��������.

������������ ����� ������ ������� � ������� ������. ������� ����� ���� ����� ������ ��� "���������� ����������������" � 1962 ����. ���������� �� � ������. � ���� ����� ������. ������� ����� ���� "��������� ����������������" ������� � ����������� ���� ��������.

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

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

�� ������� ������� ������� ����� "��������� ����������������" �. �. ����� ������ ����� 25 ���. ��� �� ����� ����� �� ������ �� ��������, �� ��-�������� �������� �������� ������������ �� ��������� ����������������, ������, �� ������� ������ �������� ���� � ����������� ����� ���������.

�� ��� ���� �� ���������� ����� ����� ��� ������ ������� 1-�� � 2-�� �����, � ����� ������ ������� 3-�� ����. ����� ���� � ��� ������������ ��������� � ������������ ����������. ���������� �������, ��� ����� ���������� ����������� ���������, � ������ ����������, ���������� � ���������� ������� (�������� ������ � ���), ��������������. ����������� ��������� � ���������� ������ ����� � �������, ���������� ���������� � ��������, ��������� �������������� ����� ������ �� ����������, ������������ ������������� ���������� ��������� ���.

����������� ������������� ����� 3, �������� ������� 3.5 � 3.6, � ����� ������� 4.5.2, 4.7, 5.1.4, 5.3, 5.4.9, 6.2.2, 6.4, 6.5 � ��.

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

������� �������� �� �������� ������� 1-�� � 2-�� ����� � ������� ������� 3-�� ����. ����� ����, ������ ���������� � �����������, ������� ��������������� �������.

��� �������� �� ��������� ��������� ����� ������, ����������� � ������ ��������� ���������. � ����������� ������� �������������� �������, �������� � ������� ���������� �� ������� �����. ��� ������������� ����������� ���������� �����������. �� ������ ��������, � ��������� ��-�� ��������� ��������� ��������, ������ ����� "��������� ����������������" ������ ��������. ����� �� ������, ������� ���������� ��������� �����, �������� ������ ��������� ������; ��������� � ���, ����� ����������� ��������� ������.

��-�� ������ ��������� (����� ���� ���������� ����� �����) ���������� ��������� ����� ���, ����� ��������� ������� � ����������� ��������� ����� �� ��� ������ ���������� � ���. ������� � ����� 1 ����� ����������� ��� ������ �������, ������� ����������� ������� ���������� � 3-� ����. ������ ������� ��� ������ ���� ����������� ���������, ��� �������� ��������� ����� ���� �� ����������� ����������. ��������, ��� �������� �� ����� �������, ����� ������ �� ����� 7, 8 � ����������� �� �������� � ������������ ��� ���� �����. �� ������ � ������� ��������, ��� ����� ����� ��� ����� ������������ �, ����������, ����� �� �������� � ������� �������� � �������� ����������� ����� �������.

������� ����� �������� �������� �� ������ �� ������ ����������� �����������, �������� ���������� �����. ��� ��, ��� � �����������, ��� ����������� ����� ��������� � 1-� ����, � �������� �� 2-�. ������� ��� ��������� ����������� ������������ ������ ���� �� ����������� ������. ���� ����� �������� �������� �� ������ [�], ��� � � ��������� ������������. ��� ������ ����������� � ��������, � ������ � � ������, � ���������� ��������, ������ ���������� �.

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

��������� � ��� ���������, ����������� �����;
��� �������� � �����������.
� ��� �����, �d Urbe Condita XXXIX.vi
(ROBERT BURTON, Anatomy of Melancholy 1.2.2.2)

�����������

��������� ��� �������� ���������� ������������ ��������� �� �������������� ����������, ������������� � ����� 2 ���� 1, ��� ��� � ��� � �������� ����������� ����� ����������� ������� ������� ������������� ������.

�������� "���������� � �����" ����� ������ �������� � �����������, � �� �����, ��� ��� ����� ������������� ������ ��� ��� ��������� �������������, ������� ���������� ����������� �������� ���������� ������ ���������� ��� ����������, ����������� ������� ����������. �� �� ����� ���� ���� ���������� � ������ ������������ ����� ��������� ������ ��� ���������� �������� ����� ������ ����� ��������.

  • ��������� ������ ������������� ���������?
  • ��� �������� ��������� ��������� � ���������?
  • ��� � ������� �������������� ������� ���������������� ������������� ����������?
  • ��� ��������� ������� �������� ��� ������� ������������ ������?
  • � ����� ������ �������� ����� ������� ��������� �� ���������?
  • ����� ������� ���� �� ����� ��������� ������ � �������� ����������?
  • ��� ���������� ������������ ��� ������� ��� ������ ������� �������� ����������, ����� ��� ��������� �����, �������� � �����?

�� ����� ���� � ������, ��� ����������� ������ ������ ������ ���������������� ��������� � ����� � ����������� � �������!

� ������ ��� ������ ����� 5 � 6. ����� 5 ��������� ���������� � ������������ �������. ��� ������� ���� ��������� �� ��� �������� �����, � ������� ���� ���� � ���������� � ������� ����������. � ����� 5 �������� ����� �������������� �������. � ��� ���������� ��������������� ������ ����������� (������ 5.1) � ����������� ������� ���������� (������ 5.3). � ����� � ��������� �������� ������ ������������ ��������� � �������� ��� ������. ����� ��������������� ������ ����������������� ������, ������ ��������� ������ ���� �������� ������� � �����������, � ����� ����������� ����� ������� �������� � ������� ���������� �����. ����� 5 � 6 ����� ������������� ����� �����; ������ �� ���� ����������.

� ��� ����������� ��� ��������� �������� �������������� �������� (� ���������� � ���, ������� ��������������� � ����� 2), � ������: ������� � ������������ (������ 5.2.3) � �������� ������, �������������� � �������� ���������������� �������� (������ 6.2.3).

��� � � ���� 1 � 2, � ���� ��� ������� ������� ����� ����� �� ���������������� ���������. ������ ������������ ��� ������ ��� � ����� �����, � � �������, ��� � �� ������� ������� �� �����, ������� �� ������������ �������.

� ���� ��� ������� �� ��������������� �������� ���������������� ����������. ����� ����, � ������� �������� ��������� � ��������� �������� �� ��������� (������ 5.4.5). ���� ���-���� ������� ��� ����� ���������������� �������, �� ������� ��� ������ � ������ �����, �� � ����������� ������ ����� ������ � ��������� ��������. �� ���-���� � �������� ����������� ������������ ��������� ������������ �������������� �������� � ������ ����� ��������� ��������� ��������� ��������� ���������. ���������� ����� ��������� ������� ������������� �� �����, ��� �� ������ ������ ������������ ����� ������� � ������������ �����.

��� ������ �������������� � ����������� ������ ����� � �������� �������� ��� ��������� �� ���������� ������. � ����� ���� ���� � �� �������, � �� ������� ������, ������� ������� ����� ��������������� ���������. � �� �� ����� ����� ������� �������������� �������� � ����������� ��� ������ ��� ����� ������� ����������, ������� ������� �� ������� ������ ������������ (������� �������, ��� ��������� � �������� 5.1, 5.2.2 � 6.4). ���� �� ��������� ���������� (��������������� ��� ���������� ����� ������������) ����� ���� ������� �� �������� 5.3 � 5.4.4, � ����� 4.3.3, 4.6.3 � 4.6.4 ���� 2.

��������� ���, � ��������, ������������ ����� ������ � ��������������� �����; ����������� �������� ���� �������, ���������� ���������� MIX, �������� �������� ��������� � ���� 1. � ���������� � ��������� �������������� � ������ ����� �������������� �����������, ������� ������ ���������� �� �������� � ������������ �������������� ����������.

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

��� ����� ������� ������������� ������� �������� ����� 1 � 2. � ��� � ������� ���������� ���������� ������ �E� � METRFONT ���, ��� �������� �� ��� ������ ����, ��� ������� ��� ���� �������������.

������� � ����������� ������ �����, � ������� ����������� ��������� ������ ����� � ������ ���� ���������� � ������. � �������� ��������� ��������� ����� ������������ ����������� � � �� �� ����� ������ ������� �������� ��������. ���� ��������� ������� ����� ����������, � �� ������� ������ ���� ����� ��� ���������� ������. ��������� ��������� ����� ������, �� �������� ��� ��������� � �������� 5.1.4 (������������ � ���������), 5.3 (����������� ����������), 5.4.9 (���������� �� �����), 6.2.2 (��������), 6.4 (������������� �����������) � 6.5 (����������� �������).

����� �������, ������ ��� ������ ��������� ���������������� ������������. ������������ ������������� ���������� ������������ � ������������� ���������. ������ ������� ��������� ������� ������ ����� ���������� ������������ "� �������� ����������" (��� ������������ ��������� �� ��, ��� ��������� �� ����� ����� ������). ��������, ���� �� � ��������� ����� � ����� �� ��������� ����� ������������ ���� �� ���������� ������, �� � ����������� ������� �� ���������� ��������� ��������, ����� ��� ����������������� �������� ������� ������ � ������. �� ���� � ���� ������ ��������� �� �������� ������ �� ����� ��������, � ����� �������� � ��������� � ������� ������� 6.2.5. ��� ����� ����������� ������� �����������, ������� � �������� �������� � ������������� ������� ���� 3; ��� ������, ��������, ����� 17 ���. �� ������� � ������ ��������� ���� 4 � 5. � ����, ����� ��� ���� ������������ ����� ��, ��� ������ ����� ������ � ������.

� ����������� ���������� ������ �����, ������� �������� ��� �������� �������� � ������� ��������� 35 ���. ������� ����� ������� ������ �� ���������� ����� ������ ������� ���� ��������� ������ ������� (Phillis Winkler), ������� ��������� ����� ������� ������� � ������ ���, ������� ���� (Silvio Levy), ������� ��������������� �������������� ����� � ����� ����������� ��������� �������� �����������, � ����� ������� �������� (Jeffrey Oldham), ������� ������������� ����� 250 ������������ ����������� � ������ METRP05T. ������� ������, ��� ������, ��������� � ���������� ����������������� ������ ������������ Addison-Wesley.

� �������� ��� ������, ������� ���������� �������� ���������� � ������ ������� (� ����� ������, �������, ���, �� ������� �����), � ���������� �������� ��������� ����� ������ � ����� ���������. ��� �� ����� � ��������, ��� ��������� ������ ��� �� ��������, � ����� �� ��������� �� ��� ����� ������. ������� �� ������ ��������* � ����� ������, ����������� � ���� ����������� ��������� ��� � ����������� ������������ ���������, � ������ ������� $2,56 ����, ��� ������ �� ������. �� Web-��������, ����� ������� �������� �� ������� �����, ���������� ������� ������ ���� ��������� ������ � �� �����������, � ������� ��� ��������.


* ������� � ���� �������� ���������� �������. � ����. ���.

D. �. �.
��������, ����������
���� 1997

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

����������


����� 5. ���������� ...................................................... 19
*5.1. ������������� �������� ������������ ............................ 29
*5.1.1. �������� ................................................. 29
*5.1.2. ������������ ��������������� ............................. 40
*5.1.3. ����� .................................................... 53
*5.1.4. ��������� � ��������� .................................... 66
5.2. ���������� ���������� ........................................... 92
5.2.1. ���������� ����� ������� .................................. 99
5.2.2. �������� ���������� ....................................... 126
5.2.3. ���������� ����������� ������ ............................. 160
5.2.4. ���������� ������� ������� ................................ 181
5.2.5. ���������� ������� ������������� .......................... 192
5.3. ����������� ���������� .......................................... 204
5.3.1. ���������� � ����������� ������ ��������� ................. 204
*5.3.2. ������� � ����������� ������ ��������� ................... 221
*5.3.3. ����� � ����������� ������ ��������� ..................... 232
*5.3.4. ���� ���������� .......................................... 245
5.4. ������� ���������� .............................................. 274
5.4.1. ������������ ������� � ����� � ���������� ................. 278
*5.4.2. ����������� ������� ...................................... 294
*5.4.3. ��������� ������� ........................................ 315
*5.4.4. ������ ����� � �������� ����������� ...................... 327
*5.4.5. ������������� ���������� ................................. 340
*5.4.6. ������������ ���������� ������� �� ������ ................ 346
*5.4.7. ������� ����������� ���������� ........................... 372
*5.4.8. ���������� � ����� ������� ............................... 378
*5.4.9. ����� � �������� ......................................... 387
5.5. ������. ������� � ������������ .................................. 412

����� 6. ����� ........................................................... 425
6.1. ���������������� ����� .......................................... 429
6.2. ����� ����� ��������� ������ .................................... 442
6.2.1. ����� � ������������� ������� ............................. 442
6.2.2. ����� �� ��������� ������ ................................. 459
6.2.3. ���������������� ������� .................................. 492
6.2.4. ���������������� ������� .................................. 516
6.3. �������� ����� .................................................. 527
6.4. ����������� ..................................................... 549
6.5. ������� �� ��������� ������ ..................................... 597

������ � ����������� ..................................................... 623

���������� �. ������� �������� ��������� �������� ........................ 794
A.I. �������� ��������� (����������) ................................. 794
�.2. �������� ��������� (������������) ............................... 795
�.�. �������� ������������� �����, ����� �������� � ����� ��������� .. 796

���������� �. �������� ����������� ....................................... 798

���������-������� ��������� .............................................. 804


Copyright © 1992-2019 ������������ ������ "����������-�������"

Rambler  Top100