20.Сортировка методом Шелла

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

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

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

Для осуществления каждого следующего прохода Шелл предложил устанавливать шаг, равный половине предыдущего шага (у дробных чисел берется целая часть). Тогда для примера шаг между элементами группы на втором проходе равен двум. В течение второго прохода упорядочиваются две группы элементов: первая, состоящая из элементов 1, 6, 2, 11, 10, 5, и вторая группа, состоящая из элементов 7, 4, 3, 8, 9. В результате второго прохода элементы этих групп окажутся упорядоченными по возрастанию их значений

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

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

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

До настоящего времени не определена общая формула для расчета среднего числа сравнений. Приближенную оценку числа сравнений производят по формуле

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

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

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

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

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

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

Рассмотрим на примере как осуществляется двухленточное слияние. Напомним, что для такого слияния потребуется 4 МЛ.

Исходная последовательность, первоначально размещенная на МЛ3, разносится на две МЛ – МЛ1 и МЛ2 в том порядке, как это описывалось выше. Предположим, что в свободной области ОП могут разместиться по две записи. Тогда в результате первого этапа сортировки будут сформированы две цепочки, каждая из которых содержит по две записи, упорядоченные по возрастанию значений ключа. Эти цепочки разместятся на МЛ3 и МЛ4, а МЛ1 и МЛ2 оказываются свободными и могут вновь использоваться для записи на них данных.

Теперь начинается этап слияния. В первом цикле слияния попарно сравниваются и упорядочиваются элементы первых цепочек с МЛ3 и МЛ4, затем элементы вторых цепочек с МЛ3 и МЛ4 и т.д. Вновь сформированные упорядоченные цепочки длиной 2L размещаются на МЛ1 и МЛ2.

Во втором цикле сравниваются и упорядочиваются элементы первых цепочек МЛ1 и МЛ2, затем – элементы вторых цепочек с МЛ1 и МЛ2. Вновь сформированные упорядоченные цепочки длиной 4L размещаются на МЛ3 и МЛ4. И, наконец, в результате сравнений и упорядочивания цепочек с МЛ3 и МЛ4 формируется единая упядоченная цепочка записей, размещенная на МЛ1. Все сравнения осуществляются в ОП.