При сортировке этим методом упорядоченная последовательность записей создается на том же участке памяти, что и исходная последовательность. В течение первого прохода осуществляется поиск наименьшего элемента. После того как этот элемент найден, его меняют местами с первым элементом исходной последовательности, в результате чего наименьший элемент занимает первую позицию в формируемой упорядоченной последовательности. Затем осуществляется поиск следующего наименьшего элемента среди оставшихся. Найденный элемент меняется местами со вторым элементом исходной последовательности. После второго прохода окажется сформированной последовательность из двух элементов, первый из которых меньше второго. Поиск элементов со следующими наименьшими значениями ключа и помещение их в соответствующие позиции исходной последовательности продолжается до тех пор, пока все элементы не будут отсортированы в восходящем порядке.
Общее число сравнений С=сумма (от i=1 до N-1)(N-i)=0.5N(N-1) (1)
При сортировке рассмотренным методом число сравнений не зависит от степени упорядоченности исходной последовательности. Поэтому полученное выражение определяет минимальное, максимальное и среднее число сравнений. Для оценки среднего числа сравнений можно использовать следующую аппроксимацию выражения (1): 0,5N2. Такая аппроксимация дает ошибку 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,Bj+1, Bj+2...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 2.
Рассмотренный алгоритм сортировки методом подсчета можно использовать лишь в тех случаях, когда в исходной последовательности отсутствуют одинаковые элементы, иными словами, когда в упорядочиваемом массиве нет записей с одинаковыми значениями ключей. Для сортировки массивов, имеющих записи с одинаковыми значениями ключей, алгоритм нужно модифицировать.
Метод Шелла
Этот широко используемый метод, предложенный Д.Л. Шеллом в 1959 г., минимален по памяти и обеспечивает высокую скорость сортировки. Метод использует сравнения и перестановки элементов, как и метод вставок, однако в отличие от последнего в сравнении участвуют не соседние элементы, а отстоящие друг от друга на определенном расстоянии. При необходимости перестановки элементы перемещаются скачком на это же расстояние, а не на одну позицию, как в методе вставок.
Для проведения сортировки описываемым методом последовательность из N элементов делится на N/2 групп или на (N - 1) /2, если N нечетно. Каждая группа содержит по два элемента. Если число элементов нечетно, то одна часть будет содержать три элемента. Элементы, принадлежащие одной группе, отстоят Ha N/2 позиций. Это расстояние называют шагом. На рис. 11.5, иллюстрирующем этот метод, одиннадцать элементов исходной последовательности А разделены на пять групп с шагом, равным пяти. Элементы, принадлежащие одной группе, объединены скобками.
В течение первого прохода осуществляется упорядочивание элементов каждой группы методом вставок. Обратимся к примеру на рис. 11.5. В результате первого прохода изменяется порядок следования элементов первой группы. Элемент 1 займет первую позицию, элементыЗи5 передвинутся вправо и займут соответственно шестую и одиннадцатую позиции. Поменяются местами также элементы второй группы {11 и 7) и элементы пятой группы (9 и 2).
Для осуществления каждого следующего прохода Шелл предложил устанавливать шаг, равный половине предыдущего шага.
Для третьего прохода устанавливается шаг, равный 1, и упорядочивается единственная группа. В результате попарных сравнений и обменов исходная последовательность оказывается полностью упорядоченной после третьего прохода.
Для сортировки последовательности из TV элементов требуется около log2N проходов.
Число сравнений, необходимое для сортировки методом Шелла, существенно зависит от шага. До сих пор продолжает обсуждаться вопрос о том, как следует выбирать последовательность шагов. Самим Шеллом была предложена последовательность 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)-й, то поиск считается неудачным, т.е. нужной записи нет в массиве.
Последовательный поиск в неупорядоченном массиве потребует меньше времени, если для массива организован общий справочник Так как объем справочника существенно меньше объема основного массива, то и поиск в нем будет происходить быстрее.