Сортировка. Метод выбора

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

Общее число сравнений С=сумма (от i=1 до N-1)(N-i)=0.5N(N-1) (1)

При сортировке рассмотренным методом число сравнений не зависит от степени упорядоченности исходной последовательности. Поэтому полученное выражение определяет минимальное, максимальное и сред­нее число сравнений. Для оценки среднего числа сравнений можно ис­пользовать следующую аппроксимацию выражения (1): 0,5N². Такая аппроксимация дает ошибку 1 %. При N=100

Количество перестановок элементов зависит от того, как располо­жены элементы исходной последовательности. Однако в любом случае в течение одного прохода потребуется не более одной перестановки; следовательно, максимальное количество перестановок равно N — 1. В лучшем случае, когда исходная последовательность уже упорядочена, не потребуется ни одной перестановки. Следовательно, среднее число пере­становок пропорционально N/2.

Метод обмена (пузырька)

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

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

Число сравнений для этого метода зависит от числа проходов, необ-ходимых для сортировки. В худшем случае, когда последовательность имеет обратную упорядоченность, в течение каждого i-го прохода выполняются перестановки, а число проходов равно N - 1. При этом для сортировки потребуется максимальное число сравнений Сmax = сумма (от i=1 до N-1)(N-i)=0.5N(N-1)

Число обменов при сортировке методом пузырька зависит от степе­ни упорядоченности исходной последовательности. Если исходная после­довательность полностью упорядочена, то обменов нет.

Метод вставок

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

Первый элемент А1 исходной последовательности А занимает пер­вую позицию в свободном участке памяти, т.е. становится первым элементом B1 последовательности B. Элемент А2 сравнивается с В1. Если в результате сравнения оказалось, что А2< В1, то элемент B1 передви­гается на одну позицию, а элемент А2 занимает его прежнее место. Теперь в свободном участке памяти размещены два элемента В1 и В2, образующих последовательность, упорядоченную по возрастанию значе­ний ключа.

В течение каждого i-го прохода процесса сортировки элемент A i сравнивается поочередно со всеми элементами последовательности В на­чиная с В1. При обнаружении Bj, большего Ai, элементы Bj,B_j+1, Bj₊₂...Bi-1

передвигаются на одну позицию, освобождая место для элемента Ai, который занимает j-ю позицию.

Последовательность из N элементов будет отсортирована за N проходов. В первом проходе сравнений не требуется, так как первый элемент просто размещается в первой ячейке памяти. В дальнейшем в течение каждого i-го прохода будет выполнено в худшем случае i -1 сравнение. Худшим окажется тот случай, когда исходная последовательность уже отсортирована в нужном порядке. Сmax= сумма (от i=1 до N-1)(N-i)=0.5N(N-1)

Метод подсчета

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

Пример сортировки методом подсчета приведен на рис. 11.4. В ре­зультате первого прохода устанавливается, что первый элемент исходной последовательности А (1) = 10 оказался больше четырех элементов и для него устанавливается К = 4. Этот элемент займет пятую позицию в упорядоченной последовательности В. Аналогично определяются позиции всех остальных элементов последовательности.

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

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

Метод Шелла

Этот широко используемый метод, предложенный Д.Л. Шеллом в 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 и т.д.

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

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

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

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

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

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

Последовательный поиск

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

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

Последовательный поиск в массиве из Nзаписей требует в среднем (N + 1)/2 сравнений (единица в числителе появляется при нечетном N). В худшем случае, когда искомая запись окажется последней в массиве или ее не будет там вовсе, потребуется N сравнений.

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

Процедура последовательного поиска в неупорядоченном массиве может быть несколько ускорена.

Любой алгоритм поиска содержит блок проверки на окончание мас­сива. Проверка обычно осуществляется всякий раз перед обращением к очередной записи. Однако проверка на окончание массива может осуще­ствляться не при каждом сравнении. Для этого в конец массива включа­ется (N + 1)-я фиктивная запись с ключом, равным искомому. Тогда проверка на окончание массива осуществляется лишь при совпадении ар­гумента поиска со значением ключа текущей записи. Если эта запись находится внутри массива, то поиск заканчивается удачно и нужная запись считается найденной. Если же эта запись оказалась (N+1)-й, то поиск считается неудачным, т.е. нужной записи нет в массиве.

Последовательный поиск в неупорядоченном массиве потребует меньше времени, если для массива организован общий справочник Так как объем справочника существенно меньше объема основ­ного массива, то и поиск в нем будет происходить быстрее.