\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