ОСНОВНЫЕ МЕТОДЫ СОРТИРОВКИ ЛИНЕЙНЫХ СТРУКТУР ДАННЫХ

Процесс сортировки, проводимой любым методом, состоит из не­скольких циклов. В каждом цикле осуществляется просмотр всей после­довательности и производятся определенные операции с ее элементами. Один цикл обработки называется проходом.

В зависимости от используемого метода сортировки упорядоченная последовательность размещается на том же участке памяти, что и исход­ная, или требует для своего формирования свободного участка памяти. В первом случае метод, минимален по памяти. Рассмотрим основные мето­ды сортировки.

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

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

Для сорти­ровки последовательности из N элементов требуется N— 1 проходов, так как на каждом проходе в соответствующую позицию упорядоченной последовательности заносится только один элемент.

Метод обмена. При сортировке этим методом упорядоченная после­довательность создается на том же месте в памяти, где располагалась исходная последовательность.

В процессе сортировки производится по­парное сравнение соседних элементов. Если порядок между сравнивае­мыми элементами нарушен, они меняются местами. Этот метод обмена называется часто методом пузырька, так как наименьшие эле­менты с каждым проходом, подобно пузырькам, "всплывают" по направлению к первой позиции последовательности.Число проходов равно N — 1

Метод вставок. При использовании этого метода сортировки упоря­доченная последовательность создается на свободном участке памяти. Под сортировку выделяется объем памяти, равный длине отсортиро­ванного массива записей. Так как исходная и упорядоченная последо­вательности располагаются в разных участках памяти, используем для их обозначения различные символы. Элементы исходной последователь­ности обозначим Ai, а элементы упорядоченной последовательнос­ти Bj.

Первый элемент А_i исходной последовательности А занимает пер­вую позицию в свободном участке памяти, т.е. становится первым элементом B1 последовательности D. Элемент А₂ сравнивается c B1. Если

в результате сравнения оказалось, что А₂ <B1,to элемент B1 передви­гается на одну позицию, а элемент А₂ занимает его прежнее место. Теперь в свободном участке памяти размещены два элемента B1 и B2, образующих последовательность, упорядоченную по возрастанию значе­ний ключа. Последовательность из N элементов будет отсортирована за N прохо­дов.

Метод подсчета. Упорядоченная последовательность В создается в свободной области памяти в результате сортировки исходной последо­вательности А.

Метод основан на том, что (К + 1)-й элемент упорядочен­ной последовательности превышает ровно К элементов и, следовательно, занимает (К + 1)-ю позицию. В процессе сортировки на каждом i-м про­ходе i-й элемент исходной последовательности попарно сравнивается со всеми остальными элементами. Если в результате сравнения установле­но, что Ai > Аj то значение числа К увеличивается на единицу. По окончании прохода значение К оказывается равным числу элементов, мень­ших чем Ai. Номер позиции i-гo элемента в последовательности В равен K+1. Для сортировки последовательности из N элементов требуется N про­ходов, на каждом проходе выполняется N сравнений.

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

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

ВНЕШНЯЯ СОРТИРОВКА

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

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

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

Сортировка методом слияния. Существует еще один метод сортировки элементов массива, эффективность которого сравнительно велика, - метод слияний.
Этот метод состоит в разбиении данного массива на несколько частей, которые сортируются по отдельности и впоследствии “сливаются” в одну.

Пусть массив а [1...n ] разбивается на части длиной k, тогда первая часть - а [ 1 ], а [ 2 ],...., а [ k ], вторая - а [ k +1 ], а [ k + 2 ],...., а [ 2k ] и так далее. Если n не делится на k, то в последней части будет менее k элементов. После того как массивы - части упорядочены, можно объединить их в упорядоченные массивы - части, состоящие не более чем из 2 k элементов, которые далее объединить в упорядоченные массивы длиной не более 4 k, и так далее, пока не получится один упорядоченный массив.

Не нашли, что искали? Воспользуйтесь поиском: