\input style
\chapnotrue
\chapno=5
\subchno=2
\subsubchno=1
%% 130

\excercises
\ex[м25]\exhead(бЕСПОРЯДОК В БИБЛИОТЕКЕ.) нЕБРЕЖНЫЕ ЧИТАТЕЛИ ЧАСТО 
СТАВЯТ КНИГИ НА ПОЛКИ В БИБЛИОТЕКЕ НЕ НА СВОЕ МЕСТО. оДИН ИЗ СПОСОБОВ 
ИЗМЕРИТЬ СТЕПЕНЬ БЕСПОРЯДКА В БИБЛИОТЕКЕ---ПОСМОТРЕТЬ, КАКОЕ МИНИМАЛЬНОЕ, 
КОЛИЧЕСТВО РАЗ ПРИШЛОСЬ БЫ БРАТЬ КНИГУ С ОДНОГО МЕСТА И ВСТАВЛЯТЬ ЕЕ В 
ДРУГОЕ МЕСТО ДО ТЕХ ПОР, ПОКА КНИГИ НЕ ОКАЖУТСЯ РАСПОЛОЖЕННЫМИ В ПРАВИЛЬНОМ 
ПОРЯДКЕ.

пУСТЬ $\pi=a_1\ a_2\ \ldots\ a_n$---ПЕРЕСТАНОВКА МНОЖЕСТВА 
$\{1, 2, \ldots, n\}$. "оПЕРАЦИЯ УДАЛЕНИЯ-ВСТАВКИ" ЗАМЕНЯЕТ $\pi$ НА
$$
a_1\ a_2\ \ldots\ a_{i-1}\ \ldots\ a_j\ a_i\ a_{j+1}\ \ldots\ a_n
$$
ИЛИ НА
$$
a_1\ \ldots\ a_j\ a_i\ a_{j+1}\ \ldots\ a_{i-1}\ a_{i+1}\ \ldots\ a_n
$$
ПРИ НЕКОТОРЫХ $i$ И $j$. пУСТЬ $\mathop{\rm dis}\nolimits 
(\pi)$---МИНИМАЛЬНОЕ ЧИСЛО ОПЕРАЦИЙ УДАЛЕНИЯ-ВСТАВКИ, НЕОБХОДИМОЕ ДЛЯ 
УПОРЯДОЧЕНИЯ ПЕРЕСТАНОВКИ $\pi$. мОЖНО ЛИ ВЫРАЗИТЬ $\mathop{\rm 
dis}\nolimits (\pi)$ ЧЕРЕЗ БОЛЕЕ ПРОСТЫЕ ХАРАКТЕРИСТИКИ $\pi$?

\ex[40] пРОВЕДИТЕ ЭКСПЕРИМЕНТЫ СО СЛЕДУЮЩЕЙ МОДИФИКАЦИЕЙ СОРТИРОВКИ С 
УБЫВАЮЩИМ ШАГОМ, ИМЕЮЩЕЙ ЦЕЛЬЮ УСКОРЕНИЕ "ВНУТРЕННЕГО ЦИКЛА": ДЛЯ $s=t$, 
$t-1$, \dots, $2$ И ДЛЯ $j=h_s+1$, $h_s+2$, \dots, $N$ ПОМЕНЯТЬ 
МЕСТАМИ $R_{j-h_s}\xchg R_j$, ЕСЛИ $K_{j-h_s}>K_j$. (тАКИМ ОБРАЗОМ, 
РЕЗУЛЬТАТ ОБМЕНОВ НЕ РАСПРОСТРАНЯЕТСЯ; НЕ ПРОИЗВОДИТСЯ СРАВНЕНИЙ 
$K_{j-h_s}:K_{j-2h_s}$. зАПИСИ НЕ ОБЯЗАТЕЛЬНО БУДУТ $h_s$-ОТСОРТИРОВАНЫ, 
НО ЭТИ ПРЕДВАРИТЕЛЬНЫЕ ПРОСМОТРЫ СПОСОБСТВУЮТ СОКРАЩЕНИЮ ЧИСЛА 
ИНВЕРСИЙ.) сОРТИРОВКА ЗАВЕРШАЕТСЯ ПРИМЕНЕНИЕМ ПРОСТЫХ ВСТАВОК.
\subsubchap{оБМЕННАЯ СОРТИРОВКА}
мЫ ПОДОШЛИ ТЕПЕРЬ КО ВТОРОМУ ИЗ СЕМЕЙСТВ АЛГОРИТМОВ СОРТИРОВКИ, 
УПОМЯНУТЫХ В САМОМ НАЧАЛЕ \S~5.2,---К МЕТОДАМ "ОБМЕНОВ" ИЛИ "ТРАНСПОЗИЦИЙ", 
ПРЕДУСМАТРИВАЮЩИХ СИСТЕМАТИЧЕСКИЙ ОБМЕН МЕСТАМИ МЕЖДУ ЭЛЕМЕНТАМИ ПАР, В 
КОТОРЫХ НАРУШАЕТСЯ УПОРЯДОЧЕННОСТЬ, ДО ТЕХ ПОР, ПОКА ТАКИХ ПАР НЕ ОСТАНЕТСЯ.

пРОЦЕСС ПРОСТЫХ ВСТАВОК (АЛГОРИТМ 5.2.1S) МОЖНО РАССМАТРИВАТЬ КАК 
ОБМЕННУЮ СОРТИРОВКУ: МЫ БЕРЕМ НОВУЮ ЗАПИСЬ $R_j$ И, ПО СУЩЕСТВУ, МЕНЯЕМ 
МЕСТАМИ С СОСЕДЯМИ СЛЕВА ДО ТЕХ ПОР, ПОКА ОНА НЕ ЗАЙМЕТ НУЖНОГО МЕСТА. 
тАКИМ ОБРАЗОМ, КЛАССИФИКАЦИЯ МЕТОДОВ СОРТИРОВКИ ПО ТАКИМ СЕМЕЙСТВАМ, 
КАК "ВСТАВКИ", "ОБМЕНЫ", "ВЫБОР" И Т. Д., НЕ ВСЕГДА ЧЕТКО ОПРЕДЕЛЕНА. в 
ЭТОМ ПУНКТЕ МЫ РАССМОТРИМ ЧЕТЫРЕ ТИПА МЕТОДОВ СОРТИРОВКИ, ДЛЯ КОТОРЫХ 
ОБМЕНЫ ЯВЛЯЮТСЯ ОСНОВНОЙ ХАРАКТЕРИСТИКОЙ: 
\emph{ОБМЕННУЮ СОРТИРОВКУ С ВЫБОРОМ} ("МЕТОД ПУЗЫРЬКА"), 
\emph{ОБМЕННУЮ СОРТИРОВКУ СО СЛИЯНИЕМ} (ПАРАЛЛЕЛЬНУЮ СОРТИРОВКУ бЭТЧЕРА), 
\emph{ОБМЕННУЮ СОРТИРОВКУ С РАЗДЕЛЕНИЕМ} ("БЫСТРУЮ СОРТИРОВКУ" хОАРА), 
\emph{ПОРАЗРЯДНУЮ ОБМЕННУЮ СОРТИРОВКУ}.

\section мЕТОД ПУЗЫРЬКА. пОЖАЛУЙ, НАИБОЛЕЕ ОЧЕВИДНЕЙ СПОСОБ ОБМЕННОЙ 
СОРТИРОВКИ ЭТО СРАВНИВАТЬ $K_1$ С $K_2$, МЕНЯЯ МЕСТАМИ $R_1$ И $R_2$, ЕСЛИ 
ИХ КЛЮЧИ НЕ УПОРЯДОЧЕНЫ, ЗАТЕМ ПРОДЕЛАТЬ ТО ЖЕ САМОЕ С $R_2$ И $R_3$, 
$R_3$ И $R_4$ И Т. Д. пРИ ВЫПОЛНЕНИИ ЭТОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ОПЕРАЦИЙ 
ЗАПИСИ С БОЛЬШИМИ КЛЮЧАМИ БУДУТ ПРОДВИГАТЬСЯ ВПРАВО, И НА САМОМ ДЕЛЕ 
ЗАПИСЬ С НАИБОЛЬШИМ КЛЮЧОМ 
%% 131
ЗАЙМЕТ ПОЛОЖЕНИЕ $R_N$. пРИ МНОГОКРАТНОМ ВЫПОЛНЕНИИ ЭТОГО ПРОЦЕССА 
СООТВЕТСТВУЮЩИЕ ЗАПИСИ ПОПАДУТ В ПОЗИЦИИ $R_{N-1}$, $R_{N-2}$ И Т. Д., ТАК 
ЧТО В КОНЦЕ КОНЦОВ ВСЕ ЗАПИСИ БУДУТ УПОРЯДОЧЕНЫ.

нА РИС.~14 ПОКАЗАНО ДЕЙСТВИЕ ЭТОГО МЕТОДА СОРТИРОВКИ НА ШЕСТНАДЦАТИ КЛЮЧАХ 
503 087 512 \dots 703. фАЙЛ ЧИСЕЛ УДОБНО
\picture{рИС. 14.  сОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА В ДЕЙСТВИИ.}
ПРЕДСТАВЛЯТЬ НЕ ГОРИЗОНТАЛЬНО, А ВЕРТИКАЛЬНО, ЧТОБЫ ЗАПИСЬ $R_N$ БЫЛА 
СВЕРХУ, a $R_1$---СНИЗУ. мЕТОД НАЗВАН "МЕТОДОМ ПУЗЫРЬКА", ПОТОМУ ЧТО 
БОЛЬШИЕ ЭЛЕМЕНТЫ, ПОДОБНО ПУЗЫРЬКАМ, "ВСПЛЫВАЮТ" НА СООТВЕТСТВУЮЩУЮ 
ПОЗИЦИЮ В ПРОТИВОПОЛОЖНОСТЬ "МЕТОДУ ПОГРУЖЕНИЯ" (Т. Е. МЕТОДУ ПРОСТЫХ 
ВСТАВОК), В КОТОРОМ ЭЛЕМЕНТЫ ПОГРУЖАЮТСЯ НА СООТВЕТСТВУЮЩИЙ УРОВЕНЬ. мЕТОД 
ПУЗЫРЬКА ИЗВЕСТЕН ТАКЖЕ ПОД БОЛЕЕ ПРОЗАИЧЕСКИМИ ИМЕНАМИ, ТАКИМИ, 
КАК "ОБМЕННАЯ СОРТИРОВКА С ВЫБОРОМ" ИЛИ МЕТОД "РАСПРОСТРАНЕНИЯ". нЕТРУДНО 
ВИДЕТЬ, ЧТО ПОСЛЕ КАЖДОГО ПРОСМОТРА ФАЙЛА ВСЕ ЗАПИСИ, НАЧИНАЯ С САМОЙ 
ПОСЛЕДНЕЙ, КОТОРАЯ УЧАСТВОВАЛА В ОБМЕНЕ,
%%132
И ВЫШЕ, ДОЛЖНЫ ЗАНЯТЬ СВОЙ ОКОНЧАТЕЛЬНЫЕ ПОЗИЦИИ,ТАК ЧТО ИХ НЕ НУЖНО 
ПРОВЕРЯТЬ ПРИ ПОСЛЕДУЮЩИХ ПРОСМОТРАХ. нА РИС.~14 ТАКОГО РОДА ПРОДВИЖЕНИЯ 
АЛГОРИТМА ОТМЕЧЕНЫ ЧЕРТОЧКАМИ. зАМЕТИМ, НАПРИМЕР, ЧТО ПОСЛЕ ЧЕТВЕРТОГО 
ПРОСМОТРА СТАЛО ИЗВЕСТНО, ЧТО ЕЩЕ ПЯТЬ ЗАПИСЕЙ ЗАНЯЛИ СВОИ ОКОНЧАТЕЛЬНЫЕ 
ПОЗИЦИИ. пРИ ПОСЛЕДНЕМ, ПРОСМОТРЕ ВООБЩЕ НЕ БЫЛО ПРОИЗВЕДЕНО 
ОБМЕНОВ. тЕПЕРЬ, СДЕЛАВ ЭТИ НАБЛЮДЕНИЯ, МЫ ГОТОВЫ СФОРМУЛИРОВАТЬ АЛГОРИТМ.

\alg в.(мЕТОД ПУЗЫРЬКА.) зАПИСИ $R_1$, \dots, $R_N$ ПЕРЕРАЗМЕЩАЮТСЯ НА 
ТОМ ЖЕ МЕСТЕ; ПОСЛЕ ЗАВЕРШЕНИЯ СОРТИРОВКИ ИХ КЛЮЧИ БУДУТ УПОРЯДОЧЕНЫ: 
$K_1\le \ldots \le K_N$.

\st[нАЧАЛЬНАЯ УСТАНОВКА BOUND.] уСТАНОВИТЬ 
$|BOUND|\asg N$. (|BOUND|---ИНДЕКС САМОГО ВЕРХНЕГО ЭЛЕМЕНТА, О КОТОРОМ ЕЩЕ 
НЕ ИЗВЕСТНО, ЗАНЯЛ ЛИ ОН УЖЕ СВОЮ ОКОНЧАТЕЛЬНУЮ ПОЗИЦИЮ; ТАКИМ ОБРАЗОМ, МЫ 
ОТМЕЧАЕМ, ЧТО К ЭТОМУ МОМЕНТУ ЕЩЕ НИЧЕГО НЕ ИЗВЕСТНО.)

\st[цИКЛ ПО $j$.] уСТАНОВИТЬ $t\asg0$. вЫПОЛНИТЬ ШАГ \stp{з} ПРИ $j=1$, 2, 
\dots, $|BOUND|-1$. зАТЕМ ПЕРЕЙТИ К ШАГУ \stp{4}. (еСЛИ $|BOUND|=1$, ТО 
СРАЗУ ПЕРЕЙТИ К \stp{4}.)

\st[сРАВНЕНИЕ/ОБМЕН $R_j : R_{j+1}$]%
\note{зДЕСЬ, КАК И РАНЕЕ, ДВОЕТОЧИЕ ИСПОЛЬЗУЕТСЯ ДЛЯ ОБОЗНАЧЕНИЯ 
ОПЕРАТОРА СРАВНЕНИЯ.---{\sl пРИМ. РЕД.}}).
еСЛИ $K_j>K_{j+1}$, ТО ПОМЕНЯТЬ МЕСТАМИ  $R_j\xchg R_{j+1}$ И УСТАНОВИТЬ 
$t\asg j$.

\st[бЫЛИ ЛИ ОБМЕНЫ?] еСЛИ $t=0$, ТО ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА. в 
ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ $|BOUND|\asg t$ И ВОЗВРАТИТЬСЯ К ШАГУ \stp{2}.
\algend
\picture{рИС. 15. бЛОК-СХЕМА СОРТИРОВКИ МЕТОДОМ ПУЗЫРЬКА.}

\prog в.(мЕТОД ПУЗЫРЬКА.) кАК И В ПРЕДЫДУЩИХ \MIX-ПРОГРАММАХ ЭТОЙ ГЛАВЫ, 
МЫ ПРЕДПОЛАГАЕМ, ЧТО СОРТИРУЕМЫЕ ЭЛЕМЕНТЫ НАХОДЯТСЯ В ЯЧЕЙКАХ 
$|INPUT|+1$, \dots,  $|INPUT|+N$;
РЕГИСТРЫ: $|rI1|\equiv t$; $|rI2|\equiv j$.
%% 133
\code
START &ENT1 & N          & 1   & B1. нАЧАЛЬНАЯ УСТАНОВКА |BOUND|.  $t\asg N$.
1H    &ST1  & BOUND (1:2)& A   & $|BOUND|\asg t$.
      &ENT2 & 1          & A   & в2. цИКЛ. ПО $j$.
      &ENT1 & 0          & A   & $t \asg 0$.
      &JMP  & BOUND      & A   & вЫХОД, ЕСЛИ  $j\ge |BOUND|$.
3H    &LDA  & INPUT, 2   & C   & B3. сРАВНЕНИЕ/ОБМЕН $R_j:R_{j+1}$.
      &смра & INPUT+1,2  & C 
      &JLE  & 2F         & C   & еСЛИ $K_j\le K_j+1$, ТО БЕЗ ОБМЕНА.
      &LDX  & INPUT+1,2  & B   & $R_{j+1}$
      &STX  & INPUT,2    & B   & $\to R_j$.
      &STA  & INPUT+1,2  & B   & $\hbox{(ПРЕЖНЕЕ $R_j$)}\to R_{j+1}$
      &ENT1 & 0,2        & B   & $t\asg j$.
9H    &INC2 & 1          & C   & $j\asg j+1$.
BOUND &ENTX & -*,2       & A+C & $|rX|\asg j-|BOUND|$. (иЗМЕНЯЕМАЯ ИНСТРУКЦИЯ)
      &JXN  & 3в         & A+C & $1\le j <|BOUND|$.
4H    &J1P  & 1B         & A   & в4. бЫЛИ ЛИ ОБМЕНЫ?  к в2, ЕСЛИ $t>0$.
\endcode
\progend

\section аНАЛИЗ МЕТОДА ПУЗЫРЬКА. оЧЕНЬ ПОЛЕЗНО ИССЛЕДОВАТЬ ВРЕМЯ РАБОТЫ 
АЛГОРИТМА в. оНО ОПРЕДЕЛЯЕТСЯ ТРЕМЯ ВЕЛИЧИНАМИ: ЧИСЛОМ ПРОСМОТРОВ $A$, 
ЧИСЛОМ ОБМЕНОВ $B$ И ЧИСЛОМ СРАВНЕНИЙ $C$. еСЛИ ИСХОДНЫЕ КЛЮЧИ РАЗЛИЧНЫ И 
РАСПОЛОЖЕНЫ В СЛУЧАЙНОМ ПОРЯДКЕ, ТО МОЖНО ПРЕДПОЛОЖИТЬ, ЧТО ОНИ ОБРАЗУЮТ 
СЛУЧАЙНУЮ ПЕРЕСТАНОВКУ МНОЖЕСТВА $\{1,2, \ldots, n\}$. пОНЯТИЕ ТАБЛИЦЫ 
ИНВЕРСИЙ (П.~5.1.1) ПРИВОДИТ К ПРОСТОМУ СПОСОБУ ОПИСАНИЯ ДЕЙСТВИЯ 
КАЖДОГО ПРОСМОТРА ПРИ СОРТИРОВКЕ МЕТОДОМ ПУЗЫРЬКА.

\proclaim тЕОРЕМА I. пУСТЬ $a_1$ $a_2$ \dots\ $a_n$---ПЕРЕСТАНОВКА   
МНОЖЕСТВА $\{1, 2, \ldots, n\}$,  А $b_1$ $b_2$ \dots 
$b_n$---СООТВЕТСТВУЮЩАЯ ТАБЛИЦА ИНВЕРСИЙ. еСЛИ В РЕЗУЛЬТАТЕ ОЧЕРЕДНОГО 
ПРОСМОТРА ПРИ СОРТИРОВКЕ МЕТОДОМ ПУЗЫРЬКА (АЛГОРИТМ в) ПЕРЕСТАНОВКА $a_1$ 
$a_2$ \dots $a_n$ ПРЕОБРАЗУЕТСЯ В $a'_1$ $a'_2$ \dots $a'_n$, ТО 
СООТВЕТСТВУЮЩАЯ ТАБЛИЦА ИНВЕРСИЙ $b'_1$ $b'_2$ \dots $b'_n$ ПОЛУЧАЕТСЯ ИЗ 
$b_1$ $b_2$ \dots $b_n$ УМЕНЬШЕНИЕМ НА ЕДИНИЦУ КАЖДОГО НУЛЕВОГО ЭЛЕМЕНТА.

\proof еСЛИ ПЕРЕД $a_i$ ИМЕЕТСЯ БОЛЬШИЙ ЭЛЕМЕНТ, ТО $a_i$ ПОМЕНЯЕТСЯ 
МЕСТАМИ С НАИБОЛЬШИМ ИЗ ПРЕДШЕСТВУЮЩИХ ЭЛЕМЕНТОВ, ТАК ЧТО $b_i$ 
УМЕНЬШИТСЯ НА ЕДИНИЦУ. с ДРУГОЙ СТОРОНЫ, ЕСЛИ ПЕРЕД $a_i$ НЕТ ЭЛЕМЕНТА, 
БОЛЬШЕГО $a_i$, ТО $a_i$ НИКОГДА НЕ ПОМЕНЯЕТСЯ МЕСТАМИ С БОЛЬШИМ ЭЛЕМЕНТОМ,
ТАК ЧТО $b_{a_i}$ ОСТАНЕТСЯ 0. 
\proofend

иТАК, МОЖНО РАЗОБРАТЬСЯ В ТОМ, ЧТО ПРОИСХОДИТ В ПРОЦЕССЕ СОРТИРОВКИ 
МЕТОДОМ ПУЗЫРЬКА, ИЗУЧАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ТАБЛИЦ ИНВЕРСИЙ МЕЖДУ 
ПРОСМОТРАМИ. вОТ КАК ВЫГЛЯДЯТ, НАПРИМЕР,
%% 134
\bye