16. Метод Шелла

Этот широко используемый метод, предложенный Д.Л. Шеллом в 1959 г., минимален по памяти и обеспечивает высокую скорость сортировки. Метод использует сравнения и перестановки элементов, как и метод вставок, однако в отличие от последнего в срав­нении участвуют не соседние элементы, а отстоящие друг от друга на определенном расстоянии. При необходимости перестановки элементы перемещаются скачком на это же расстояние, а не на одну позицию, как в методе вставок.

Для проведения сортировки описываемым методом последователь­ность из N элементов делится на N/2 групп или на (N - 1) /2, если N не­четно. Каждая группа содержит по два элемента. Если число элементов нечетно, то одна часть будет содержать три элемента. Элементы, принад­лежащие одной группе, отстоят Ha N/2 позиций. Это расстояние называют шагом. На рис. 11.5, иллюстрирующем этот метод, одиннадцать элемен­тов исходной последовательности А разделены на пять групп с шагом, равным пяти. Элементы, принадлежащие одной группе, объединены скобками.

В течение первого прохода осуществляется упорядочивание элемен­тов каждой группы методом вставок. Обратимся к примеру на рис. 11.5. В результате первого прохода изменяется порядок следования элементов первой группы. Элемент 1 займет первую позицию, элементыЗи5 пере­двинутся вправо и займут соответственно шестую и одиннадцатую позиции. Поменяются местами также элементы второй группы {11 и 7) и элементы пятой группы (9 и 2).

Для осуществления каждого следующего прохода Шелл предло­жил устанавливать шаг, равный половине предыдущего шага.

Для третьего прохода устанавливается шаг, равный 1, и упорядочи­вается единственная группа. В результате попарных сравнений и обменов исходная последовательность оказывается полностью упорядоченной после третьего прохода.

Для сортировки последовательности из TV элементов требуется около log₂N проходов.

Число сравнений, необходимое для сортировки методом Шелла, существенно зависит от шага. До сих пор продолжает обсуждаться вопрос о том, как следует выбирать последовательность шагов. Самим Шеллом была предложена последовательность N/2, N/4, N/8 и т.д.

17.Внешняя сортировка

Когда объем сортируемых данных велик и превышает свободный объем ОП, то для сортировки используются ВЗУ. Обычно применяют МЛ, как наиболее дешевые и емкие ВЗУ.

Наиболее общей формой внешней сортировки с применением МЛ является сбалансированное n-ленточное слияние. Для n-ленточного слия­ния требуется 2n МЛ и 2n лентопротяжных устройств.

Исходная неупорядоченная последовательность, размещенная на од­ной МЛ, разносится на n МЛ следующим образом. Первая запись - на первую МЛ, вторая — на вторую, n-я запись — на n-ю МЛ. В дальнейшем' (n + 1) -я запись снова записывается на первую МЛ, (n + 2) -я - на вторую и тд. до тех пор, пока вся исходная последовательность не будет распре­делена на n Мл.

Сбалансированное n-ленточное слияние осуществляется в два этапа. На первом этапе из записей, хранящихся на каждой МЛ, формируются упорядоченные цепочки длиной L. Так как все цепочки имеют одинако­вую длину, слияние называется сбалансированным. Упорядочение цепо­чек происходит в ОП и длина каждой цепочки L определяется исходя из выделенного для сортировки объема ОП. Упорядоченные цепочки разме­шаются на n свободных МЛ. Затем эти ленты перематываются к началу и выполняется второй этап внешней сортировки — слияние.

Процесс слияния осуществляется в несколько циклов. После каждо­го цикла слияния длина упорядоченных цепочек увеличивается в n раз. В результате слияния формируется единая упорядоченная последова­тельность записей. В литературе n-ленточное слияние называют также n-путевым слиянием.