\input style
\chapnotrue
\chapno=5
\subchno=1
%% 93
\subchap{тНУТРЕННЯЯ СОРТИРОВКА}
эАЧНЕМ ОБСУЖДЕНИЕ ХОРОШЕГО "СОРТИРОВАНИЯ" С МАЛЕНЬКОГО ЭКСПЕРИМЕНТА: КАК 
БЫ ВЫ РЕШИЛИ СЛЕДУЮЩУЮ ЗАДАЧУ ПРОГРАММИРОВАНИЯ?                    $$
\vtop{
\narrower
"▀ЧЕЙКИ ПАМЯТИ $|R|+1$,  $|R|+2$, $|R|+3$, $|R|+4$ И~$|R|+5$
СОДЕРЖАТ ПЯТЬ ЧИСЕЛ. эАПИШИТЕ ПРОГРАММУ, КОТОРАЯ ПЕРЕРАЗМЕЩАЕТ, ЕСЛИ НУЖНО,
 ЭТИ ЧИСЛА ТАК, ЧТОБЫ ОНИ РАСПОЛОЖИЛИСЬ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ."
\par
}
$$
(хСЛИ ВЫ УЖЕ ЗНАКОМЫ С КАКИМИ-ЛИБО МЕТОДАМИ СОРТИРОВКИ, ПОСТАРАЙТЕСЬ, 
ПОЖАЛУЙСТА, НА МИНУТУ ЗАБЫТЬ О НИХ; ВООБРАЗИТЕ, ЧТО ВЫ РЕШАЕТЕ ТАКУЮ 
ЗАДАЧУ ВПЕРВЫЕ, НЕ ИМЕЯ НИКАКИХ ПРЕДВАРИТЕЛЬНЫХ ЗНАНИЙ О ТОМ, КАК К НЕЙ ПОДСТУПИТЬСЯ.)

\bigskip
\emph{
яРЕЖДЕ ЧЕМ ЧИТАТЬ ДАЛЬШЕ, НАСТОЯТЕЛЬНО ПРОСИМ ВАС НАЙТИ ХОТЬ КАКОЕ-НИБУДЬ 
РЕШЕНИЕ ЭТОЙ ЗАДАЧИ.
}
\bigskip
\line{\null\leaders\hbox to 1em{\hss.\hss}\hfill\null}
\bigskip

тРЕМЯ, ЗАТРАЧЕННОЕ НА РЕШЕНИЕ ПРИВЕДЕННОЙ ВЫШЕ ЗАДАЧИ, ОКУПИТСЯ С ЛИХВОЙ, 
КОГДА ВЫ ПРОДОЛЖИТЕ ЧТЕНИЕ ЭТОЙ ГЛАВЫ. тОЗМОЖНО, ВАШЕ РЕШЕНИЕ ОКАЖЕТСЯ 
ОДНИМ ИЗ СЛЕДУЮЩИХ:

\medskip
A.{\sl  ёОРТИРОВКА ВСТАВКАМИ.\/} ¤ЛЕМЕНТЫ ПРОСМАТРИВАЮТСЯ ПО ОДНОМУ, И 
КАЖДЫЙ НОВЫЙ ЭЛЕМЕНТ ВСТАВЛЯЕТСЯ В ПОДХОДЯЩЕЕ МЕСТО СРЕДИ РАНЕЕ 
УПОРЯДОЧЕННЫХ ЭЛЕМЕНТОВ. (шМЕННО ТАКИМ СПОСОБОМ ИГРОКИ В БРИДЖ 
УПОРЯДОЧИВАЮТ СВОИ КАРТЫ, БЕРЯ ПО ОДНОЙ.)

B.{\sl  юБМЕННАЯ СОРТИРОВКА.\/} хСЛИ ДВА ЭЛЕМЕНТА РАСПОЛОЖЕНЫ НЕ ПО 
ПОРЯДКУ, ТО ОНИ МЕНЯЮТСЯ МЕСТАМИ. ¤ТОТ ПРОЦЕСС ПОВТОРЯЕТСЯ ДО ТЕХ ПОР, 
ПОКА ЭЛЕМЕНТЫ НЕ БУДУТ УПОРЯДОЧЕНЫ.
 C. {\sl ёОРТИРОВКА ПОСРЕДСТВОМ ВЫБОРА.\/} ёНАЧАЛА ВЫДЕЛЯЕТСЯ 
НАИМЕНЬШИЙ (ИЛИ. БЫТЬ МОЖЕТ, НАИБОЛЬШИЙ) ЭЛЕМЕНТ И КАКИМ-ЛИБО ОБРАЗОМ 
ОТДЕЛЯЕТСЯ ОТ ОСТАЛЬНЫХ, ЗАТЕМ ВЫБИРАЕТСЯ НАИМЕНЬШИЙ (НАИБОЛЬШИЙ) ИЗ 
ОСТАВШИХСЯ И Т. Д.

D. {\sl ёОРТИРОВКА ПОДСЧЕТОМ.\/} ъАЖДЫЙ ЭЛЕМЕНТ СРАВНИВАЕТСЯ СО ВСЕМИ 
ОСТАЛЬНЫМИ; ОКОНЧАТЕЛЬНОЕ-ПОЛОЖЕНИЕ ЭЛЕМЕНТА ОПРЕДЕЛЯЕТСЯ ПОДСЧЕТОМ 
ЧИСЛА МЕНЬШИХ КЛЮЧЕЙ.

E. {\sl ёПЕЦИАЛЬНАЯ СОРТИРОВКА\/}, КОТОРАЯ ХОРОША ДЛЯ ПЯТИ ЭЛЕМЕНТОВ, 
УКАЗАННЫХ В ЗАДАЧЕ, НО НЕ ПОДДАЕТСЯ ПРОСТОМУ ОБОБЩЕНИЮ НА. СЛУЧАЙ 
БОЛЬШЕГО ЧИСЛА ЭЛЕМЕНТОВ.
%% 94
F. {\sl ыЕНИВОЕ РЕШЕНИЕ.\/} тЫ НЕ ОТКЛИКНУЛИСЬ НА НАШЕ ПРЕДЛОЖЕНИЕ И 
ОТКАЗАЛИСЬ РЕШАТЬ ЗАДАЧУ. цАЛЬ, НО ТЕПЕРЬ, КОГДА ВЫ ПРОЧЛИ ТАК МНОГО, ВАШ 
ШАНС УПУЩЕН.

G. {\sl эОВАЯ СУПЕРСОРТИРОВКА\/}, КОТОРАЯ ПРЕДСТАВЛЯЕТ СОБОЙ 
ОПРЕДЕЛЕННОЕ УСОВЕРШЕНСТВОВАНИЕ ИЗВЕСТНЫХ МЕТОДОВ. (яОЖАЛУЙСТА,
 НЕМЕДЛЕННО СООБЩИТЕ ОБ ЭТОМ АВТОРУ.)
\medskip

хСЛИ БЫ ЭТА ЗАДАЧА БЫЛА СФОРМУЛИРОВАНА, СКАЖЕМ, ДЛЯ 1000 ЭЛЕМЕНТОВ, А НЕ 
ДЛЯ 5, ТО ВЫ МОГЛИ БЫ ОТКРЫТЬ И НЕКОТОРЫЕ БОЛЕЕ ТОНКИЕ МЕТОДЫ, О КОТОРЫХ 
БУДЕТ УПОМЯНУТО НИЖЕ. т ЛЮБОМ СЛУЧАЕ, ПРИСТУПАЯ К НОВОЙ ЗАДАЧЕ, РАЗУМНО 
НАЙТИ КАКУЮ-НИБУДЬ ОЧЕВИДНУЮ ПРОЦЕДУРУ, А ЗАТЕМ ПОПЫТАТЬСЯ УЛУЧШИТЬ 
ЕЕ. ёЛУЧАИ р, т И ё ПРИВОДЯТ К ВАЖНЫМ КЛАССАМ МЕТОДОВ СОРТИРОВКИ, 
КОТОРЫЕ ПРЕДСТАВЛЯЮТ СОБОЙ УСОВЕРШЕНСТВОВАНИЯ СФОРМУЛИРОВАННЫХ ВЫШЕ 
ПРОСТЫХ ИДЕЙ.

сЫЛО ИЗОБРЕТЕНО МНОЖЕСТВО РАЗЛИЧНЫХ АЛГОРИТМОВ СОРТИРОВКИ, И В ЭТОЙ 
КНИГЕ РАССМАТРИВАЕТСЯ ОКОЛО 25 ИЗ НИХ. ¤ТО ПУГАЮЩЕЕ КОЛИЧЕСТВЕ МЕТОДОВ НА 
САМОМ ДЕЛЕ ЛИШЬ МАЛАЯ ТОЛИКА ВСЕХ АЛГОРИТМОВ, ПРИДУМАННЫХ ДО СИХ ПОР; 
МНОГИЕ, УЖЕ УСТАРЕВШИЕ МЕТОДЫ МЫ ВОВСЕ НЕ БУДЕМ РАССМАТРИВАТЬ ИЛИ 
УПОМЯНЕМ ЛИШЬ ВСКОЛЬЗЬ. яОЧЕМУ ЖЕ ТАК МНОГО МЕТОДОВ СОРТИРОВКИ? 
фЛЯ ПРОГРАММИРОВАНИЯ ЭТО ЧАСТНЫЙ СЛУЧАЙ ВОПРОСА: "яОЧЕМУ СУЩЕСТВУЕТ ТАК 
МНОГО МЕТОДОВ $x$?", ГДЕ $x$ ПРОБЕГАЕТ МНОЖЕСТВО ВСЕХ ЗАДАЧ. юТВЕТ СОСТОИТ 
В ТОМ, ЧТО КАЖДЫЙ МЕТОД ИМЕЕТ СВОИ ПРЕИМУЩЕСТВА И НЕДОСТАТКИ, ПОЭТОМУ ОН 
ОКАЗЫВАЕТСЯ ЭФФЕКТИВНЕЕ ДРУГИХ ПРИ НЕКОТОРЫХ КОНФИГУРАЦИЯХ ДАННЫХ И 
АППАРАТУРЫ. ъ СОЖАЛЕНИЮ, НЕИЗВЕСТЕН "НАИЛУЧШИЙ" СПОСОБ СОРТИРОВКИ;
СУЩЕСТВУЕТ \emph{МНОГО} НАИЛУЧШИХ МЕТОДОВ В ЗАВИСИМОСТИ ОТ ТОГО, ЧТО 
СОРТИРУЕТСЯ, НА КАКОЙ МАШИНЕ, ДЛЯ КАКОЙ ЦЕЛИ. уОВОРЯ СЛОВАМИ ЁЕДЬЯРДА 
ъИПЛИНГА, "СУЩЕСТВУЕТ 9 И ЕЩЕ 60 СПОСОБОВ СЛОЖИТЬ ПЕСНЮ ПЛЕМЕНИ, И КАЖДЫЙ 
ИЗ НИХ В ОТДЕЛЬНОСТИ ХОРОШ".

яОЛЕЗНО ИЗУЧИТЬ ХАРАКТЕРИСТИКИ КАЖДОГО МЕТОДА СОРТИРОВКИ, ЧТОБЫ МОЖНО БЫЛО 
ПРОИЗВОДИТЬ РАЗУМНЫЙ ВЫБОР ДЛЯ КОНКРЕТНЫХ ПРИЛОЖЕНИЙ. ъ СЧАСТЬЮ, ЗАДАЧА 
ИЗУЧЕНИЯ ЭТИХ АЛГОРИТМОВ НЕ СТОЛЬ УЖ ГРОМОЗДКА, ПОСКОЛЬКУ МЕЖДУ НИМИ 
СУЩЕСТВУЮТ ИНТЕРЕСНЫЕ ВЗАИМОСВЯЗИ.

т НАЧАЛЕ ЭТОЙ ГЛАВЫ МЫ ВВЕЛИ ОСНОВНУЮ ТЕРМИНОЛОГИЮ И ОБОЗНАЧЕНИЯ, КОТОРЫЕ 
И БУДЕМ ИСПОЛЬЗОВАТЬ ПРИ ИЗУЧЕНИИ СОРТИРОВКИ. чАПИСИ
$$
R_1, R_2, \ldots, R_N
\eqno(1)
$$
ДОЛЖНЫ БЫТЬ ОТСОРТИРОВАНЫ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ ПО СВОИМ КЛЮЧАМ $K_1$, 
$K_2$, \dots, $K_N$, ПО СУЩЕСТВУ, ПУТЕМ НАХОЖДЕНИЯ ПЕРЕСТАНОВКИ $p(1)$ 
$p(2)$ \dots $p(N)$,  ТАКОЙ, ЧТО
$$
K_{p(1)}\le K_{p(2)}\le \ldots \le K_{p(N)}.
\eqno(2)
$$
%% 95
т ЭТОМ ПАРАГРАФЕ РАССМАТРИВАЕТСЯ \dfn{ВНУТРЕННЯЯ СОРТИРОВКА}, КОГДА ЧИСЛО 
ЗАПИСЕЙ, ПОДЛЕЖАЩИХ СОРТИРОВКЕ, ДОСТАТОЧНО МАЛО, ТАК ЧТО ВЕСЬ ПРОЦЕСС 
МОЖНО ПРОВЕСТИ В ОПЕРАТИВНОЙ ПАМЯТИ ¤ть.

т ОДНИХ СЛУЧАЯХ МОЖЕТ ПОНАДОБИТЬСЯ ФИЗИЧЕСКИ ПЕРЕРАЗМЕСТИТЬ ЗАПИСИ В 
ПАМЯТИ ТАК, ЧТОБЫ ИХ КЛЮЧИ БЫЛИ УПОРЯДОЧЕНЫ;
В ДРУГИХ МОЖНО ОБОЙТИСЬ ВСПОМОГАТЕЛЬНОЙ ТАБЛИЦЕЙ НЕКОТОРОГО
\picture{ЁИС. 6. ёОРТИРОВКА ТАБЛИЦЫ АДРЕСОВ.}
ВИДА, КОТОРАЯ ОПРЕДЕЛЯЕТ ПЕРЕСТАНОВКУ. хСЛИ ЗАПИСИ И/ИЛИ КЛЮЧИ ЗАНИМАЮТ 
НЕСКОЛЬКО СЛОВ ПАМЯТИ, ТО ЧАСТО ЛУЧШЕ СОСТАВИТЬ НОВУЮ ТАБЛИЦУ АДРЕСОВ 
(ССЫЛОК), КОТОРЫЕ УКАЗЫВАЮТ НА ЗАПИСИ, И РАБОТАТЬ С ЭТИМИ АДРЕСАМИ, НЕ 
ПЕРЕМЕЩАЯ ГРОМОЗДКИЕ ЗАПИСИ. ЄАКОЙ МЕТОД НАЗЫВАЕТСЯ \dfn{СОРТИРОВКОЙ 
ТАБЛИЦЫ АДРЕСОВ}
\picture{ЁИС. 7.  ёОРТИРОВКА СПИСКА.}
(РИС~ 6.). хСЛИ КЛЮЧИ КОРОТКИЕ, А СОПУТСТВУЮЩАЯ ИНФОРМАЦИЯ В ЗАПИСЯХ 
ВЕЛИКА, ТО ДЛЯ ПОВЫШЕНИЯ СКОРОСТИ КЛЮЧИ МОЖНО ВЫНЕСТИ В ТАБЛИЦУ АДРЕСОВ; 
ЭТО НАЗЫВАЕТСЯ \dfn{СОРТИРОВКОЙ КЛЮЧЕЙ}. фРУГИЕ СХЕМЫ СОРТИРОВКИ 
ИСПОЛЬЗУЮТ ВСПОМОГАТЕЛЬНОЕ ПОЛЕ СВЯЗИ, КОТОРОЕ ВКЛЮЧАЕТСЯ В КАЖДУЮ ЗАПИСЬ. 
ёВЯЗИ ОБРАБАТЫВАЮТСЯ ТАКИМ ОБРАЗОМ, ЧТО В РЕЗУЛЬТАТЕ ВСЕ ЗАПИСИ 
ОКАЗЫВАЮТСЯ СВЯЗАННЫМИ В ЛИНЕЙНЫЙ СПИСОК, В КОТОРОМ КАЖДАЯ СВЯЗЬ 
УКАЗЫВАЕТ НА СЛЕДУЮЩУЮ ПО ПОРЯДКУ ЗАПИСЬ. ¤ТО НАЗЫВАЕТСЯ 
\dfn{СОРТИРОВКОЙ СПИСКА} (РИС. 7).

%% 96

яОСЛЕ СОРТИРОВКИ ТАБЛИЦЫ АДРЕСОВ ИЛИ СОРТИРОВКИ СПИСКА МОЖНО ПО ЖЕЛАНИЮ 
РАСПОЛОЖИТЬ ЗАПИСИ В НЕУБЫВАЮЩЕМ ПОРЯДКЕ. фЛЯ ЭТОГО ИМЕЕТСЯ НЕСКОЛЬКО 
СПОСОБОВ, ТРЕБУЮЩИХ ДОПОЛНИТЕЛЬНОЙ ПАМЯТИ ДЛЯ ХРАНЕНИЯ ВСЕГО ОДНОЙ ЗАПИСИ 
(СМ. УПР. С 10 ПО 12);
ИЛИ ЖЕ МОЖНО ПРОСТО ПЕРЕМЕСТИТЬ ЗАПИСИ В НОВУЮ ОБЛАСТЬ ПАМЯТИ,  ЕСЛИ ОНА 
МОЖЕТ ВМЕСТИТЬ ВСЕ ЭТИ ЗАПИСИ. яОСЛЕДНИЙ СПОСОБ ОБЫЧНО ВДВОЕ БЫСТРЕЕ 
ПЕРВОГО, НО ТРЕБУЕТ ПОЧТИ В ДВА РАЗА БОЛЬШЕ ПАМЯТИ. тО МНОГИХ ПРИЛОЖЕНИЯХ 
ВОВСЕ НЕ ОБЯЗАТЕЛЬНО ПЕРЕМЕЩАТЬ ЗАПИСИ, ТАК КАК ПОЛЯ СВЯЗИ, КАК ПРАВИЛО, 
ВПОЛНЕ ПРИЕМЛЕМЫ ДЛЯ ОПЕРАЦИЙ С ПОСЛЕДОВАТЕЛЬНОЙ АДРЕСАЦИЕЙ.

тСЕ МЕТОДЫ СОРТИРОВКИ, КОТОРЫЕ МЫ ИССЛЕДУЕМ "ДОСКОНАЛЬНО", БУДУТ 
ПРОИЛЛЮСТРИРОВАНЫ ЧЕТЫРЬМЯ СПОСОБАМИ: ПОСРЕДСТВОМ
\medskip
\item{a)} СЛОВЕСНОГО ОПИСАНИЯ АЛГОРИТМА,
\item{b)} БЛОК-СХЕМЫ,
\item{c)} ПРОГРАММЫ ДЛЯ МАШИНЫ \MIX,
\item{d)} ПРИМЕРА ПРИМЕНЕНИЯ ЭТОГО МЕТОДА СОРТИРОВКИ К ЗАДАННОМУ МНОЖЕСТВУ ЧИСЕЛ.
\medskip
[т ТЕХ ПРИМЕРАХ, ГДЕ ЭТО УМЕСТНО, БУДЕТ ОБРАБАТЫВАТЬСЯ МНОЖЕСТВО ИЗ 16 
ЧИСЕЛ, КОТОРЫЕ АВТОР, ПОЛЬЗУЯСЬ НАБОРОМ ДЕСЯТИЧНЫХ ИГРАЛЬНЫХ КОСТЕЙ, 
ВЫБРАЛ СЛУЧАЙНЫМ ОБРАЗОМ 19 МАРТА 1963 Г.; СР. С УПР. 3.1--1 (С).]

шЗ СООБРАЖЕНИЙ УДОБСТВА ПРОГРАММЫ ДЛЯ МАШИНЫ \MIX\ БУДУТ, КАК ПРАВИЛО, 
НАПИСАНЫ В ПРЕДПОЛОЖЕНИИ, ЧТО КЛЮЧ ЧИСЛОВОЙ И ЧТО ОН ПОМЕЩАЕТСЯ В ОДНОМ 
СЛОВЕ; ИНОГДА МЫ ДАЖЕ БУДЕМ ОГРАНИЧИВАТЬ ЗНАЧЕНИЯ КЛЮЧЕЙ ТАК, ЧТОБЫ ОНИ 
ЗАНИМАЛИ ЛИШЬ ЧАСТЬ СЛОВА. юТНОШЕНИЕМ ПОРЯДКА $<$ БУДЕТ ОБЫЧНОЕ 
АРИФМЕТИЧЕСКОЕ ОТНОШЕНИЕ ПОРЯДКА, А ЗАПИСИ БУДУТ СОСТОЯТЬ ИЗ ОДНОГО 
КЛЮЧА, БЕЗ СОПУТСТВУЮЩЕЙ ИНФОРМАЦИИ. т ЭТИХ ПРЕДПОЛОЖЕНИЯХ 
ПРОГРАММЫ ПОЛУЧАЮТСЯ КОРОЧЕ, ПРОЩЕ ДЛЯ ПОНИМАНИЯ, И НЕ ПРЕДСТАВЛЯЕТ ТРУДА 
РАСПРОСТРАНИТЬ ИХ НА ОБЩИЙ СЛУЧАЙ (НАПРИМЕР, ПРИМЕНЯЯ СОРТИРОВКУ ТАБЛИЦ 
АДРЕСОВ). тМЕСТЕ С \MIX-ПРОГРАММАМИ ПРИВОДИТСЯ АНАЛИЗ ВРЕМЕНИ ВЫПОЛНЕНИЯ 
СООТВЕТСТВУЮЩЕГО АЛГОРИТМА СОРТИРОВКИ.

\section ёОРТИРОВКА ПОДСЧЕТОМ. ўТОБЫ ПРОИЛЛЮСТРИРОВАТЬ СПОСОБ, КОТОРЫМ 
МЫ БУДЕМ ИЗУЧАТЬ МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ, РАССМОТРИМ ИДЕЮ 
"ПОДСЧЕТА", УПОМЯНУТУЮ В НАЧАЛЕ ЭТОГО ПАРАГРАФА. ¤ТОТ ПРОСТОЙ МЕТОД 
ОСНОВАН НА ТОМ, ЧТО $j$-Й КЛЮЧ В ОКОНЧАТЕЛЬНО УПОРЯДОЧЕННОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ ПРЕВЫШАЕТ РОВНО $(j-1)$ ИЗ ОСТАЛЬНЫХ КЛЮЧЕЙ. шНАЧЕ 
ГОВОРЯ, ЕСЛИ ИЗВЕСТНО, ЧТО НЕКОТОРЫЙ КЛЮЧ ПРЕВЫШАЕТ РОВНО 27 ДРУГИХ, ТО 
ПОСЛЕ СОРТИРОВКИ СООТВЕТСТВУЮЩАЯ ЗАПИСЬ ДОЛЖНА ЗАНЯТЬ 28-Е МЕСТО. ЄАКИМ 
ОБРАЗОМ, ИДЕЯ СОСТОИТ В ТОМ, ЧТОБЫ СРАВНИТЬ ПОПАРНО ВСЕ КЛЮЧИ И 
ПОДСЧИТАТЬ, СКОЛЬКО ИЗ НИХ МЕНЬШЕ КАЖДОГО ОТДЕЛЬНОГО КЛЮЧА.

%% 97

юЧЕВИДНЫЙ СПОСОБ ВЫПОЛНИТЬ СРАВНЕНИЯ---
$$
\hfill
\hbox{((СРАВНИТЬ $K_j$ c $K_i$) ПРИ $1\le j \le N$) ПРИ $1\le i\le N$,}
\hfill
$$
НО ЛЕГКО ВИДЕТЬ, ЧТО БОЛЕЕ ПОЛОВИНЫ ЭТИХ ДЕЙСТВИЙ ИЗЛИШНИ, ПОСКОЛЬКУ НЕ 
НУЖНО СРАВНИВАТЬ КЛЮЧ САМ С СОБОЙ И ПОСЛЕ СРАВНЕНИЯ $K_a$ С $K_b$ УЖЕ НЕ 
НАДО СРАВНИВАТЬ $K_b$ С $K_a$. яОЭТОМУ ДОСТАТОЧНО
$$
\hfill
\hbox{((СРАВНИТЬ $K_j$ С $K_i$) ПРИ $1\le j\le i$) ПРИ $1 < i \le N$.}
\hfill
$$
шТАК, ПРИХОДИМ К СЛЕДУЮЩЕМУ АЛГОРИТМУ.

\alg ё.(ёРАВНЕНИЕ И ПОДСЧЕТ.) ¤ТОТ АЛГОРИТМ СОРТИРУЕТ ЗАПИСИ 
$R_1$,~\dots, $R_N$ ПО КЛЮЧАМ $K_1$,~\dots, $K_N$, ИСПОЛЬЗУЯ ДЛЯ 
ПОДСЧЕТА ЧИСЛА КЛЮЧЕЙ, МЕНЬШИХ ДАННОГО, ВСПОМОГАТЕЛЬНУЮ ТАБЛИЦУ 
$|COUNT|[1]$,~\dots, $|COUNT|[N]$. яОСЛЕ ЗАВЕРШЕНИЯ АЛГОРИТМА ВЕЛИЧИНА 
$|COUNT|[j]+1$ ОПРЕДЕЛЯЕТ ОКОНЧАТЕЛЬНОЕ ПОЛОЖЕНИЕ ЗАПИСИ $R_j$.

\st[ёБРОСИТЬ СЧЕТЧИКИ.] єСТАНОВИТЬ $|COUNT|[1]$,~\dots, $|COUNT|[N]$
РАВНЫМИ НУЛЮ.

\st[ЎИКЛ ПО $i$.] тЫПОЛНИТЬ ШАГ \stp{ч} ПРИ $i=N$, $N-1$, \dots, 2;
ЗАТЕМ ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.

\st[ЎИКЛ ПО $j$.] тЫПОЛНИТЬ ШАГ \stp{4} ПРИ $j=i -1$, $i-2$, \dots, 1.

\st[ёРАВНИТЬ $K_i$, $K_j$.] хСЛИ $K_i<K_j$, ТО УВЕЛИЧИТЬ $|COUNT|[j]$ НА 
1; В ПРОТИВНОМ СЛУЧАЕ УВЕЛИЧИТЬ $|COUNT|[i]$ НА~1.
\algend

чАМЕТИМ, ЧТО В ЭТОМ АЛГОРИТМЕ ЗАПИСИ НЕ ПЕРЕМЕЩАЮТСЯ. юН АНАЛОГИЧЕН 
СОРТИРОВКЕ ТАБЛИЦЫ АДРЕСОВ, ПОСКОЛЬКУ ТАБЛИЦА |COUNT| ОПРЕДЕЛЯЕТ КОНЕЧНОЕ 
РАСПОЛОЖЕНИЕ ЗАПИСЕЙ; НО ЭТИ
МЕТОДЫ НЕСКОЛЬКО РАЗЛИЧАЮТСЯ, ПОТОМУ ЧТО $|COUNT|[j]$ УКАЗЫВАЕТ ТО МЕСТО, 
КУДА НУЖНО ПЕРЕСЛАТЬ ЗАПИСЬ $R_j$, А НЕ ТУ ЗАПИСЬ, КОТОРУЮ НАДО ПЕРЕСЛАТЬ 
НА МЕСТО $R_j$. (ЄАКИМ ОБРАЗОМ, ТАБЛИЦА |COUNT| ОПРЕДЕЛЯЕТ ПЕРЕСТАНОВКУ, 
ОБРАТНУЮ $p(1)$~\dots $p(n)$; СМ. П.~5.1.1.)

т РАССУЖДЕНИИ, ПРЕДШЕСТВУЮЩЕМ ЭТОМУ АЛГОРИТМУ, МЫ НЕ УЧИТЫВАЛИ, ЧТО КЛЮЧИ 
МОГУТ БЫТЬ РАВНЫМИ. ¤ТО, ВООБЩЕ ГОВОРЯ, СЕРЬЕЗНОЕ УПУЩЕНИЕ, ПОТОМУ ЧТО 
ЕСЛИ БЫ РАВНЫМ КЛЮЧАМ СООТВЕТСТВОВАЛИ РАВНЫЕ СЧЕТЧИКИ, ТО ЗАКЛЮЧИТЕЛЬНОЕ 
ПЕРЕМЕЩЕНИЕ ЗАПИСЕЙ БЫЛО БЫ ДОВОЛЬНО СЛОЖНЫМ. ъ СЧАСТЬЮ, КАК ПОКАЗАНО В 
УПР. 2, АЛГОРИТМ C ДАЕТ ВЕРНЫЙ РЕЗУЛЬТАТ НЕЗАВИСИМО ОТ ЧИСЛА РАВНЫХ КЛЮЧЕЙ.
\picture{ЁИС. 8. рЛГОРИТМ ё: СРАВНЕНИЕ И ПОДСЧЕТ.}

%% 98

\ctable{|COUNT|($#$):\hfill&&\bskip\hfill$#$\hfill\bskip\cr
\noalign{\rightline{ЄАБЛИЦА 1}}
\noalign{\centerline{\bf ёОРТИРОВКА ПОДСЧЕТОМ (АЛГОРИТМ ё)}}
\noalign{\vskip0.5ex\hrule\vskip0.5ex}
\omit \hfill КЛЮЧИ: \hfill
           & 503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 & 703\cr
\hbox{НАЧ.}&  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  0 \cr
i=N        &  0  &  0  &  0  &  0  &  1  &  0  &  1  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  1  &  12\cr
i=N-1      &  0  &  0  &  0  &  0  &  2  &  0  &  2  &  0  &  0  &  0  &  0  &  0  &  0  &  0  &  13 &  12\cr
i =N-2     &  0  &  0  &  0  &  0  &  3  &  0  &  3  &  0  &  0  &  0  &  0  &  0  &  0  &  11 &  13 &  12\cr
i=N-3      &  0  &  0  &  0  &  0  &  4  &  0  &  4  &  0  &  1  &  0  &  0  &  0  &  9  &  11 &  13 &  12\cr
i=N-4      &  0  &  0  &  1  &  0  &  5  &  0  &  5  &  0  &  2  &  0  &  0  &  7  &  9  &  11 &  13 &  12\cr
i=N-5      &  1  &  0  &  2  &  0  &  6  &  1  &  6  &  1  &  3  &  1  &  2  &  7  &  9  &  11 &  13 &  12\cr
\noalign{
\line{\null\leaders\hbox to 1em{\hss.\hss}\hfill\null}
}
i=2        &  6  &  1  &  8  &  0  &  15 &  3  &  14 &  4  &  10 &  5  &  2  &  7  &  9  &  11 &  13 &  12\cr
\noalign{\vskip0.5ex\hrule\vskip0.5ex}
}

\prog C.(ёРАВНЕНИЕ И ПОДСЧЕТ.) т СЛЕДУЮЩЕЙ РЕАЛИЗАЦИИ АЛГОРИТМА C ДЛЯ 
МАШИНЫ \MIX\ ПРЕДПОЛАГАЕТСЯ, ЧТО ЗАПИСЬ $R_j$ НАХОДИТСЯ В ЯЧЕЙКЕ 
$|INPUT|+j$, a $|COUNT|[j]$---В ЯЧЕЙКЕ $|COUNT| +j$, ГДЕ $1\le j\le N$; 
$|rI1|\equiv i$; $|rI2|\equiv j$; $|rA|\equiv K_i\equiv R_i$; 
$|rX|\equiv|COUNT|[i]$.
\code
START&ENT1 & N       & 1  &ё1 . ёБРОСИТЬ СЧЕТЧИКИ.
     &STZ  & COUNT,1 & N  &$|COUNT|[i]\asg 0$.
     &DEC1 & 1       & N
     &J1P  & *-2     & N  &$N\ge i>0$.
     &ENT1 & N       & 1  &ё2. ЎИКЛ ПО $i$.
     &JMP  & 1F      & 1 
2э   &LDA  & INPUT,1 & N-1
     &LDX  & COUNT,1 & N-1
3H   &CMPA & INPUT,2 & A   &C4. ёРАВНИТЬ $K_i$, $K_j$.
     &JGE  & 4F      & A   &яЕРЕХОД, ЕСЛИ $K_i\ge K_j$.
     &LD3  & COUNT,2 & B   &$|COUNT|[j]$
     &INC3 & 1       & B   &$+1$
     &ST3  & COUNT,2 & B   &$\to |COUNT|[j]$
     &JMP  & 5F      & B   
4H   &INCX & 1       & A-B &$|COUNT|[i]+1\to|COUNT|[i]$.
5H   &DEC2 & 1       & A   &ё3.ЎИКЛ ПО $j$.
     &J2P  & 3B      & A
     &STX  & COUNT,1 & N-1
     &DEC1 & 1       & N-1
1э   &ENT2 & -1,1    & N   &$N\ge i>j>0$.
     &J2P  & 2B      & N
\endcode
\progend

тРЕМЯ РАБОТЫ ЭТОЙ ПРОГРАММЫ РАВНО $13N+6A+5B-4$ ЕДИНИЦ, ГДЕ $N$---ЧИСЛО 
ЗАПИСЕЙ,  $A$---ЧИСЛО СПОСОБОВ ВЫБРАТЬ 2 ПРЕДМЕТА ИЗ $N$, Т. Е. 
$\perm{N}{2}=(N^2-N)/2$, А $B$--- ЧИСЛО ПАР ИНДЕКСОВ,
ТАКИХ, ЧТО $j<i$, И $K_j>K_i$. ЄАКИМ ОБРАЗОМ, $B$---\emph{ЧИСЛО ИНВЕРСИЙ} 
ПЕРЕСТАНОВКИ $K_1$, \dots, $K_N$; ЭТА ВЕЛИЧИНА ПОДРОБНО АНАЛИЗИРОВАЛАСЬ 
В П.~5.1.1, И БЫЛО НАЙДЕНО [ФОРМУЛЫ (5.1.1--12,13)], ЧТО ДЛЯ НЕРАВНЫХ 
КЛЮЧЕЙ, РАСПОЛОЖЕННЫХ В СЛУЧАЙНОМ ПОРЯДКЕ,
$$
B=\left(\min 0, \ave {(N^2-N\over 4}, \max{(N^2-N)\over 2}, 
\dev{\sqrt{N(N-1)(N+2.5)}\over 6}\right).
$$

%% 99

ёЛЕДОВАТЕЛЬНО, ВЫПОЛНЕНИЕ ПРОГРАММЫ C ЗАНИМАЕТ 
ОТ~$3N^2+10N-4$ ДО~$5.5N^2+7.5N-4$ ЕДИНИЦ ВРЕМЕНИ, А СРЕДНЕЕ ВРЕМЯ РАБОТЫ 
НАХОДИТСЯ ПОСЕРЕДИНЕ МЕЖДУ ЭТИМИ ДВУМЯ ГРАНИЦАМИ. эАПРИМЕР, ДЛЯ ДАННЫХ 
ТАБЛ.~1 ИМЕЕМ $N=16$, $A=120$, $B=41$, ЗНАЧИТ, ПРОГРАММА C ОТСОРТИРУЕТ ИХ 
ЗА ВРЕМЯ $1129u$. ьОДИФИКАЦИЮ ПРОГРАММЫ $C$, ОБЛАДАЮЩУЮ НЕСКОЛЬКО ИНЫМИ 
ВРЕМЕННЫМИ ХАРАКТЕРИСТИКАМИ, СМ. В УПР.~5.

ьНОЖИТЕЛЬ $N^2$, КОТОРЫМ ОПРЕДЕЛЯЕТСЯ ВРЕМЯ РАБОТЫ, СВИДЕТЕЛЬСТВУЕТ О 
ТОМ, ЧТО АЛГОРИТМ C НЕ ДАЕТ ЭФФЕКТИВНОГО СПОСОБА СОРТИРОВКИ, КОГДА $N$ 
ВЕЛИКО; ПРИ УДВОЕНИИ ЧИСЛА ЗАПИСЕЙ ВРЕМЯ УВЕЛИЧИВАЕТСЯ В ЧЕТЫРЕ РАЗА. 
яОСКОЛЬКУ ЭТОТ МЕТОД ТРЕБУЕТ СРАВНЕНИЯ ВСЕХ ПАР КЛЮЧЕЙ $(K_i, K_j)$, ТО 
НЕТ ОЧЕВИДНОГО СПОСОБА ИСКЛЮЧИТЬ ЗАВИСИМОСТЬ ОТ $N^2$, ТЕМ НЕ МЕНЕЕ МЫ 
УВИДИМ ДАЛЬШЕ В ЭТОЙ ГЛАВЕ, ЧТО, ПОЛЬЗУЯСЬ "РАЗДЕЛЕНИЕМ И ОБМЕНОМ", 
МОЖНО СНИЗИТЬ ПОРЯДОК СРЕДНЕГО ВРЕМЕНИ РАБОТЫ ДО $N\log N$. рЛГОРИТМ C 
ИНТЕРЕСЕН ДЛЯ НАС НЕ ЭФФЕКТИВНОСТЬЮ, А ГЛАВНЫМ ОБРАЗОМ СВОЕЙ ПРОСТОТОЙ; 
ЕГО ОПИСАНИЕ СЛУЖИТ ПРИМЕРОМ ТОГО СТИЛЯ, В КОТОРОМ БУДУТ ОПИСАНЫ БОЛЕЕ 
СЛОЖНЫЕ (И БОЛЕЕ ЭФФЕКТИВНЫЕ) МЕТОДЫ.

ёУЩЕСТВУЕТ ДРУГАЯ РАЗНОВИДНОСТЬ СОРТИРОВКИ ПОСРЕДСТВОМ ПОДСЧЕТА, КОТОРАЯ 
\emph{ДЕЙСТВИТЕЛЬНО} ВЕСЬМА ВАЖНА С ТОЧКИ ЗРЕНИЯ ЭФФЕКТИВНОСТИ; ОНА 
ПРИМЕНИМА В ОСНОВНОМ В ТОМ СЛУЧАЕ, КОГДА ИМЕЕТСЯ МНОГО РАВНЫХ КЛЮЧЕЙ И ВСЕ 
ОНИ ПОПАДАЮТ В ДИАПАЗОН $u\le K_j\le v$, ГДЕ ЗНАЧЕНИЕ $(v-u)$ НЕВЕЛИКО. 
¤ТИ ПРЕДПОЛОЖЕНИЯ ПРЕДСТАВЛЯЮТСЯ ВЕСЬМА ОГРАНИЧИТЕЛЬНЫМИ, НО НА,САМОМ ДЕЛЕ 
МЫ УВИДИМ НЕМАЛО ПРИЛОЖЕНИЙ ЭТОЙ ИДЕИ; НАПРИМЕР, ЕСЛИ ПРИМЕНИТЬ ЭТОТ 
МЕТОД ЛИШЬ К СТАРШИМ ЦИФРАМ КЛЮЧЕЙ, А НЕ КО ВСЕМ КЛЮЧАМ ЦЕЛИКОМ, ТО ФАЙЛ 
ОКАЖЕТСЯ ЧАСТИЧНО ОТСОРТИРОВАННЫМ, И БУДЕТ УЖЕ СРАВНИТЕЛЬНО ПРОСТО ДОВЕСТИ 
ДЕЛО ДО КОНЦА.

ўТОБЫ ПОНЯТЬ ПРИНЦИП, ПРЕДПОЛОЖИМ, ЧТО ВСЕ КЛЮЧИ ЛЕЖАТ МЕЖДУ~1 И~100. яРИ 
ПЕРВОМ ПРОСМОТРЕ ФАЙЛА МОЖНО ПОДСЧИТАТЬ, СКОЛЬКО ИМЕЕТСЯ КЛЮЧЕЙ, РАВНЫХ 
1, 2, \dots, 100, А ПРИ ВТОРОМ ПРОСМОТРЕ МОЖНО УЖЕ РАСПОЛАГАТЬ ЗАПИСИ В 
СООТВЕТСТВУЮЩИХ МЕСТАХ ОБЛАСТИ ВЫВОДА. т СЛЕДУЮЩЕМ АЛГОРИТМЕ ВСЕ 
ЭТО ОПИСАНО БОЛЕЕ ПОДРОБНО.
\picture{ЁИС. 9. рЛГОРИТМ D: РАСПРЕДЕЛЯЮЩИЙ ПОДСЧЕТ.}
%% 100

\bye