\input style
%% 140
РИТМА бЭТЧЕРА ЗАВЕРШАЕТСЯ; ЭТОТ АЛГОРИТМ МОЖНО БЫЛО БЫ НАЗВАТЬ 
СОРТИРОВКОЙ ПОСРЕДСТВОМ ПЕРЕГИБОВ!

\MIX-ПРОГРАММА ДЛЯ АЛГОРИТМА м ПРИВЕДЕНА В УПР.~12. к СОЖАЛЕНИЮ, 
КОЛИЧЕСТВО ВСПОМОГАТЕЛЬНЫХ ОПЕРАЦИЙ, НЕОБХОДИМЫХ ДЛЯ УПРАВЛЕНИЯ 
ПОСЛЕДОВАТЕЛЬНОСТЬЮ СРАВНЕНИЙ, ВЕСЬМА ВЕЛИКО, ТАК ЧТО ПРОГРАММА МЕНЕЕ 
ЭФФЕКТИВНА, ЧЕМ ДРУГИЕ МЕТОДЫ, КОТОРЫЕ МЫ РАЗБИРАЛИ. оДНАКО АЛГОРИТМ 
ОБЛАДАЕТ ОДНИМ ВАЖНЫМ КОМПЕНСИРУЮЩИМ КАЧЕСТВОМ: ВСЕ СРАВНЕНИЯ/ОБМЕНЫ, 
ОПРЕДЕЛЯЕМЫЕ ДАННОЙ ИТЕРАЦИЕЙ ШАГА мз, МОЖНО ВЫПОЛНЯТЬ \emph{ОДНОВРЕМЕННО} 
НА эвм ИЛИ ЛОГИЧЕСКИХ СХЕМАХ, КОТОРЫЕ ДОПУСКАЮТ ПАРАЛЛЕЛЬНЫЕ
\picture{рИС. 18.  гЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ МЕТОДА бЭТЧЕРА,  $N= 16$.}
ВЫЧИСЛЕНИЯ. с ТАКИМИ ПАРАЛЛЕЛЬНЫМИ ОПЕРАЦИЯМИ СОРТИРОВКА ВЫПОЛНЯЕТСЯ ЗА  
${1\over 2}\lceil \log_2  N \rceil (\lceil log_2 N \rceil + 1)$ ШАГОВ, И 
ЭТО ОДИН
ИЗ САМЫХ БЫСТРЫХ ИЗВЕСТНЫХ ОБЩИХ МЕТОДОВ. нАПРИМЕР, \emph{1024 ЭЛЕМЕНТА 
МОЖНО ОТСОРТИРОВАТЬ МЕТОДОМ бЭТЧЕРА ВСЕГО ЗА 55 ПАРАЛЛЕЛЬНЫХ ШАГОВ}. еГО 
БЛИЖАЙШИМ СОПЕРНИКОМ ЯВЛЯЕТСЯ МЕТОД пРАТТА (СМ. УПР. 5.2.1--30), КОТОРЫЙ 
ЗАТРАЧИВАЕТ 40 ИЛИ 73 ШАГА В ЗАВИСИМОСТИ ОТ ТОГО, КАК СЧИТАТЬ: ЕСЛИ МЫ 
ГОТОВЫ ДОПУСТИТЬ ПЕРЕКРЫТИЕ СРАВНЕНИЙ ДО ТЕХ ПОР, ПОКА НЕ ПОТРЕБУЕТСЯ 
ВЫПОЛНЯТЬ ПЕРЕКРЫВАЮЩИЕСЯ ОБМЕНЫ, ТО ДЛЯ СОРТИРОВКИ 1024 ЭЛЕМЕНТОВ 
МЕТОДОМ пРАТТА ТРЕБУЕТСЯ ВСЕГО 40 ЦИКЛОВ СРАВНЕНИЯ/ОБМЕНА. дАЛЬНЕЙШИЕ 
ПОЯСНЕНИЯ СМ. В П.~5.3.4.

\section "бЫСТРАЯ СОРТИРОВКА". в МЕТОДЕ бЭТЧЕРА 
ПОСЛЕДОВАТЕЛЬНОСТЬ СРАВНЕНИЙ ПРЕДОПРЕДЕЛЕНА: КАЖДЫЙ РАЗ СРАВНИВАЮТСЯ ОДНИ 
И ТЕ ЖЕ ПАРЫ КЛЮЧЕЙ НЕЗАВИСИМО ОТ ТОГО, ЧТО МЫ МОГЛИ УЗНАТЬ О ФАЙЛЕ ИЗ 
ПРЕДЫДУЩИХ СРАВНЕНИЙ. эТО УТВЕРЖДЕНИЕ В БОЛЬШОЙ МЕРЕ СПРАВЕДЛИВО И 
ПРИМЕНИТЕЛЬНО К МЕТОДУ ПУЗЫРЬКА, ХОТЯ АЛГОРИТМ в И ИСПОЛЬЗУЕТ В 
ОГРАНИЧЕННОЙ СТЕПЕНИ ПОЛУЧЕННЫЕ СВЕДЕНИЯ, С ТЕМ ЧТОБЫ СОКРАТИТЬ КОЛИЧЕСТВО 
РАБОТЫ В ПРАВОМ КОНЦЕ ФАЙЛА. оБРАТИМСЯ ТЕПЕРЬ К СОВСЕМ ИНОЙ СТРАТЕГИИ, 
ПРИ КОТОРОЙ ИСПОЛЬЗУЕТСЯ РЕЗУЛЬТАТ КАЖДОГО СРАВНЕНИЯ, ЧТОБЫ ОПРЕДЕЛИТЬ, 
КАКИЕ КЛЮЧИ СРАВНИВАТЬ СЛЕДУЮЩИМИ. тАКАЯ СТРАТЕГИЯ НЕ ГОДИТСЯ ДЛЯ 
ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ, НО ОНА МОЖЕТ ОКАЗАТЬСЯ ПЛОДОТВОРНОЙ ДЛЯ 
ВЫЧИСЛИТЕЛЬНЫХ МАШИН, РАБОТАЮЩИХ ПОСЛЕДОВАТЕЛЬНО.

%%141

иТАК, РАССМОТРИМ. СЛЕДУЮЩУЮ СХЕМУ СРАВНЕНИЙ/ОБМЕНОВ. иМЕЮТСЯ ДВА УКАЗАТЕЛЯ 
$i$ И $j$, ПРИЧЕМ ВНАЧАЛЕ $i=l$, a $j=N$. сРАВНИМ $K_i:K_j$, И ЕСЛИ ОБМЕН 
НЕ ТРЕБУЕТСЯ, ТО УМЕНЬШИМ $j$ НА ЕДИНИЦУ И ПОВТОРИМ ЭТОТ ПРОЦЕСС. пОСЛЕ 
ПЕРВОГО ОБМЕНА УВЕЛИЧИМ $i$ НА ЕДИНИЦУ И БУДЕМ ПРОДОЛЖАТЬ СРАВНЕНИЯ, 
УВЕЛИЧИВАЯ $i$, ПОКА НЕ ПРОИЗОЙДЕТ ЕЩЕ ОДИН ОБМЕН. тОГДА ОПЯТЬ УМЕНЬШИМ 
$j$ И Т. Д.; БУДЕМ "СЖИГАТЬ СВЕЧКУ С ОБОИХ КОНЦОВ", ПОКА НЕ СТАНЕТ $i=j$. 
пОСМОТРИМ, НАПРИМЕР, ЧТО ПРОИЗОЙДЕТ С НАШИМ ФАЙЛОМ ИЗ ШЕСТНАДЦАТИ ЧИСЕЛ:
{\catcode`\!=\active\def!#1 {\bf#1}
\def\inci{\noalign{\rightline{УВЕЛИЧИТЬ $i$}}}
\def\decj{\noalign{\rightline{УМЕНЬШИТЬ $j$}}}
\ctable{#&&\bskip\hfill$#$\hfill\bskip\cr
дАНО:     &!503 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 & 154 & 509 & 612 & 677 & 765 &!703\cr
\decj
1-Й ОБМЕН &!154 & 087 & 512 & 061 & 908 & 170 & 897 & 275 & 653 & 426 &!503 & 509 & 612 & 677 & 765 & 703\cr
\inci
2-Й ОБМЕН & 154 & 087 &!503 & 061 & 908 & 170 & 897 & 275 & 653 & 426 &!512 & 509 & 612 & 677 & 765 & 703\cr
\decj
3-Й ОБМЕН & 154 & 087 &!426 & 061 & 908 & 170 & 897 & 275 & 653 &!503 & 512 & 509 & 612 & 677 & 765 & 703\cr
\inci
4-Й ОБМЕН & 154 & 087 & 426 & 061 &!503 & 170 & 897 & 275 & 653 &!908 & 512 & 509 & 612 & 677 & 765 & 703\cr
\decj
5-Й ОБМЕН & 154 & 087 & 426 & 061 &!275 & 170 & 897 &!503 & 653 & 908 & 512 & 509 & 612 & 677 & 765 & 703\cr
\inci
6-Й ОБМЕН & 154 & 087 & 426 & 061 & 275 & 170 &!503 &!897 & 653 & 808 & 512 & 509 & 612 & 677 & 765 & 703\cr
\decj
}
}
(чТОБЫ ВЫЯВИТЬ СОСТОЯНИЕ $i$ И $j$, КЛЮЧИ $K_i$ И $K_j$ НАПЕЧАТАНЫ ЖИРНЫМ 
ШРИФТОМ.) зАМЕТИМ, ЧТО В КАЖДОМ СРАВНЕНИИ ЭТОГО ПРИМЕРА УЧАСТВУЕТ КЛЮЧ 
503; ВООБЩЕ В КАЖДОМ СРАВНЕНИИ БУДЕТ УЧАСТВОВАТЬ ИСХОДНЫЙ КЛЮЧ $K_1$, 
ПОТОМУ ЧТО ОН БУДЕТ ПРОДОЛЖАТЬ ОБМЕНИВАТЬСЯ МЕСТАМИ С ДРУГИМИ КЛЮЧАМИ 
КАЖДЫЙ РАЗ, КОГДА МЫ ПЕРЕКЛЮЧАЕМ НАПРАВЛЕНИЕ. к МОМЕНТУ, КОГДА $i=j$, 
ИСХОДНАЯ ЗАПИСЬ $R_1$ ЗАЙМЕТ СВОЮ ОКОНЧАТЕЛЬНУЮ ПОЗИЦИЮ, ПОТОМУ ЧТО, КАК 
НЕТРУДНО ВИДЕТЬ, СЛЕВА  ОТ НЕЕ НЕ БУДЕТ БОЛЬШИХ КЛЮЧЕЙ, А СПРАВА---МЕНЬШИХ. 
иСХОДНЫЙ ФАЙЛ ОКАЖЕТСЯ РАЗДЕЛЕН ТАКИМ ОБРАЗОМ, ЧТО ПЕРВОНАЧАЛЬНАЯ ЗАДАЧА 
СВЕДЕТСЯ К ДВУМ БОЛЕЕ ПРОСТЫМ: СОРТИРОВКЕ ФАЙЛА $R_1$ \dots\ $R_{i-1}$ И 
(НЕЗАВИСИМО) СОРТИРОВКЕ ФАЙЛА $R_{i+1}$ \dots\ $R_N$. к КАЖДОМУ ИЗ ЭТИХ 
ПОДФАЙЛОВ МОЖНО ПРИМЕНИТЬ ТОТ ЖЕ САМЫЙ МЕТОД.

в ТАБЛ.~2 ПОКАЗАНО, КАК ВЫБРАННЫЙ НАМИ ДЛЯ ПРИМЕРОВ ФАЙЛ ПОЛНОСТЬЮ 
СОРТИРУЕТСЯ ПРИ ПОМОЩИ ЭТОГО МЕТОДА ЗА 11 СТАДИЙ. в СКОБКИ ЗАКЛЮЧЕНЫ 
ПОДФАЙЛЫ, КОТОРЫЕ ЕЩЕ ПРЕДСТОИТ ОТСОРТИРОВАТЬ; В МАШИНЕ ЭТИ ПОДФАЙЛЫ 
МОЖНО ПРЕДСТАВЛЯТЬ ДВУМЯ ПЕРЕМЕННЫМИ $l$ И~$r$ (ГРАНИЦЫ РАССМАТРИВАЕМОГО В 
ДАННЫЙ МОМЕНТ ФАЙЛА) И СТЕКОМ ДОПОЛНИТЕЛЬНЫХ ПАР $(l_k, r_k)$. кАЖДЫЙ РАЗ, 
КОГДА ФАЙЛ ПОДРАЗДЕЛЯЕТСЯ, МЫ ПОМЕЩАЕМ В СТЕК \emph{БОЛЬШИЙ} ИЗ 
ПОДФАЙЛОВ И НАЧИНАЕМ ОБРАБАТЫВАТЬ ОСТАВШИЙСЯ, И ТАК ДО ТЕХ ПОР, ПОКА 
НЕ ПРИДЕМ К ТРИВИАЛЬНО КОРОТКИМ ФАЙЛАМ; КАК ПОКАЗАНО В УПР.~20, ТАКАЯ 
ПРОЦЕДУРА ГАРАНТИРУЕТ, ЧТО В СТЕКЕ НИКОГДА НЕ БУДЕТ НАХОДИТЬСЯ БОЛЕЕ, ЧЕМ 
ПРИМЕРНО $\log_2 N$ ЭЛЕМЕНТОВ.
%% 142
\bye