. на Ведь ясно, что все пары соседних элементов с индек-обмев ;

м порядке. Поэтому следующие проходы можно заканчи-да этом индексе, вместо того чтобы двигаться до устз-овленной заранее нижней границы /. Однако внимательный рраммист заметит здесь странную асимметрию: один не-павильно расположенный пузырек в тяжелом конце LcopTHpoBaHHoro массива всплывет на место за один проход, 3 неправильно расположенный элемент в легком конце будет опускаться на правильное место только на один, jjjar на каждом проходе. Например, массив

12 18 42 44 55 67 94 06

будет рассортирован при помощи метода пузырька за один проход, а сортировка массива

94 06 12 18 42 44 55 67

потребует семи проходов. Эта неестественная асимметрия подсказывает третье улучшение: менять направление следующих один за другим проходов. Мы назовем полученный в результате алгоритм шейкер-сортировкой. Его работа показана в табл. 2.4 на тех же восьми ключах, которые использовались в табл. 2.3.

Ta6jHua 2.4. Пример шейкер-сортировки

меньшими этого индекса k, уже расположены в нуж-

Анализ сортировки методом пузырька и шейкер-сорти-Ровки. Число сравнений в алгоритме простого обмена равно

CUn~n), 2.10)

* *1Инимальное, среднее и максимальное количества пересы-к (присваиваний элементов) равны

imln = 0, Mep. = i(n-n). Мшах (2.11).

procedure shakersort;

var J,k,l,t: index; x: item; begin / := 2; r :~ n; k;= n; repeat

for j :=> r downto / do

if a[j-l] .key > a[j] .key then

begin X сЦ-Ц; о[У--1] := 4/J; := л:;

end ;

/ := k+l;

for jr ;= / to r do

if a[j-l] .key > a[j] .key then

-begin X a[j-l] ;= 4/1; 4J] = x;

k:=j end ;

until / > r

end [shakersort]

Программа 2.5. Шейкер-сортировка.

Анализ улучшенных методов, особенно метода шейкер-сорти-ровки, довольно сложен. Наименьшее число сравнений есл Стт = п-1. Для усовершенствованного метода пузырьи Кнут получил, что среднее число проходов пропорционально п - ki V и среднее число сравнений пропорционально ~[п^- п{1г2 + 1пп)]- Но мы замечаем, что все предложенные

выше усовершенствования никоим образом не влияют на число обменов; они лишь уменьшают число избыточных повторных проверок. К сожалению, обмен двух элементов-обычно намного более дорогостоящая операция, чем сравда ния ключей, поэтому все наши уссвершенствования дают зиа' чительно меньший эффект, чем можно было бы ожидать.

Анализ показывает, что сортировка обменом и ее неболь шие улучшения хуже, чем сортировка включениями и выбором, и действительно, сортировка методом пузырька вряд -ч имеет какие-то преимущества, кроме своего легко запом наювдегося названия. Алгоритм шейкер-сортировки выгодно использовать в тех случаях, когда известно, что элементе уже почти упорядочены - редкий случай на практике.

Можно показать, что среднее расстояние, на которое до жен переместиться каждый из п элементов во время сорт ровки, -это п/3 мест. Это число дает ключ к поиску ус° верптенствованных, т. е. более эффективных, методов сорт

Все простые методы в принципе перемещают каждый ент позицию на каждом элементарном щаге.

оМУ они требуют порядка таких шагов. Любое улуч-Поэ^ должно основываться на принципе пересылки элемен-ча один цикл на большее расстояние.

т^дддее мы обсудим три усовершенствованных метода - по иу для каждого основного метода сортировки: включе-2;-в*1бора и обмена.

224, Сортировка включениями с убывающим приращением

Некоторое усовершенствование сортировки простыми включениями было предложено Д. Л. Шеллом в 1959 г. Этот метод мы объясним и продемонстрируем на нашем стандартном примере из восьми элементов (см. табл. 2.5). На первом.

Таблица 2.Б. Сортировка включениями с убывающим приращением

12 42 94 18 06 67

94 55 12 67

1-еортировка;

06 12 18 42 44 55 67 94

Проходе отдельно группируются и сортируются все элементы, отстоящие дрг от друга на четыре позиции. Этот процесс иазывается 4-сортировкой. В нашем примере из восьми эле-teieHTOB каждая группа содержит ровно два элемента. После ртого элементы вновь объединяются в группы с элементами, отстоящи&1и друг от друга на две позиции, и сортируются Заново. Этот процесс называется 2-сортировкой. Наконец, на Третьем проходе все элементы сортируются обычной сортировкой, или 1-сортировкой.

Сначала может показаться, что необходимость нескольких Роходов сортировки, в каждом из которых участвуют все Менты, больше работы потребует, чем сэкономит. Однако