\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