Добавлен: 25.06.2023
Просмотров: 118
Скачиваний: 3
Рис. 1. Пример сортировки выбором
В этом примере первый проход ничего не меняет, поскольку в массиве нет элемента, меньшего самого левого элемента А. На втором проходе наименьшим среди оставшихся оказался другой элемент А, поэтому он меняется местами с элементом S, занимающим вторую позицию. На третьем проходе элемент Е из середины массива обменивается с О в третьей позиции, на четвертом проходе еще один элемент Е меняется местами с R в четвертой позиции и т.д. [10, С. 257].
Недостаток сортировки выбором заключается в том, что время ее выполнения лишь в малой степени зависит от того, насколько упорядочен исходный файл. Процесс нахождения минимального элемента за один проход файла дает очень мало сведений о том, где может находиться минимальный элемент на следующем проходе этого файла. Например, пользователь, применяющий этот метод, будет немало удивлен, когда узнает, что на сортировку почти отсортированного файла или файла, записи которого имеют одинаковые ключи, требуется столько же времени, сколько и на сортировку файла, упорядоченного случайным образом. Другие методы с большим успехом используют преимущества присутствия порядка в исходном файле [6, С. 459].
Несмотря на всю ее простоту и очевидный примитивизм подхода, сортировка выбором превосходит более совершенные методы в одном из важных приложений: этому методу сортировки файлов отдается предпочтение в тех случаях, когда записи файла огромны, а ключи занимают незначительное пространство. В подобного рода приложениях затраты ресурсов на перемещения записей намного превосходят стоимость операций сравнения, а что касается перемещения данных, то никакой алгоритм не способен выполнить сортировку файла с меньшим числом перемещений данных, нежели метод выбора [10, С. 259].
Сортировка вставками. Метод сортировки, который часто применяют игроки в бридж по отношению к картам на руках, заключается в том, что отдельно анализируется каждый конкретный элемент, который затем помещается в надлежащее место среди других, уже отсортированных элементов. В условиях компьютерной реализации следует позаботиться о том, чтобы освободить место для вставляемого элемента путем смещения больших элементов на одну позицию вправо, после чего на освободившееся место помещается вставляемый элемент [10, С. 259].
Сортируемый массив можно разделить на две части — отсортированная часть и неотсортированная. В начале сортировки первый элемент массива считается отсортированным, все остальные — не отсортированные. Начиная со второго элемента массива и заканчивая последним, алгоритм вставляет неотсортированный элемент массива в нужную позицию в отсортированной части массива. Таким образом, за один шаг сортировки отсортированная часть массива увеличивается на один элемент, а неотсортированная часть массива уменьшается на один элемент. Как и в случае с сортировкой выбора, элементы, находящиеся слева от текущего индекса, отсортированы в соответствующем порядке, тем не менее, они еще не занимают свои окончательные позиции, ибо могут быть передвинуты с целью освобождения места под меньшие элементы, которые обнаруживаются позже. Массив будет полностью отсортирован, когда индекс достигнет правой границы массива.
Рис. 2. Пример выполнения сортировки вставками
Во время первого прохода сортировки вставками элемент S во второй позиции больше A, так что перемещать его не надо. На втором проходе элемент O в третьей позиции меняется местами с S, так что получается упорядоченная последовательность A O S и т.д. Не заштрихованные и обведенные кружками элементы — это те, которые были сдвинуты на одну позицию вправо [10, С. 257].
Часто применяется альтернативный способ: сортируемые ключи хранятся в элементах массива от a[1] до a[N], а в a[0] заносится сигнальный ключ (sentinel key), значение которого по крайней мере не больше наименьшего ключа в сортируемом массиве. Тогда проверка, найден ли меньший ключ, проверяет сразу оба условия, и в результате внутренний цикл становится меньше, а быстродействие программы повышается.
Сигнальные ключи не всегда удобны: иногда бывает трудно определить значение минимально возможного ключа, а иногда в вызывающей программе нет места для дополнительного ключа. На рис. 2 предлагается один из способов обойти сразу обе эти проблемы: сначала выполняется отдельный проход по массиву, который помещает в первую позицию элемент с минимальным ключом. Затем сортируется остальной массив, а первый, он же наименьший, элемент служит в качестве сигнального ключа [10, С. 259].
Пузырьковая сортировка. Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются следующие действия: проход по файлу с обменом местами соседних элементов, нарушающих заданный порядок, до тех пор, пока файл не будет окончательно отсортирован. Основное достоинство пузырьковой сортировки заключается в том, что его легко реализовать в виде программы, однако вопрос о том, какой из методов сортировки реализуется легче других — пузырьковый, метод вставок или метод выбора — остается открытым [10, С. 261].
Сортировка пузырьком - самый естественный, он же самый медленный алгоритм сортировки. Алгоритм пузырьковой сортировки просматривает массив чисел от начала до конца до тех пор, пока любые два рядом стоящих числа не будут расположены по возрастанию. Для этого два неверно расположенные одно относительно другого числа меняются местами. При этом наименьшее число, как пузырёк, постепенно всплывает к началу массива (а наибольшее сразу "тонет" как камень!), отсюда и название алгоритма. Время сортировки пузырьком пропорционально квадрату количества чисел в массиве [10, С. 262].
Количество проходов алгоритма пузырьковой сортировки в худшем случае будет равно количеству элементов в массиве.
Рис. 3. Пример выполнения пузырьковой сортировки
В пузырьковой сортировке ключи с малыми значениями постепенно сдвигаются влево. Поскольку проходы выполняются справа налево, каждый ключ меняется местами с ключом слева до тех пор, пока не будет обнаружен ключ с меньшим значением. На первом проходе E меняется местами с L, P и M и останавливается справа от A; затем A продвигается к началу файла, пока не остановится перед другим A, который уже находится на свом месте. Как и в случае сортировки выбором, после i-го прохода i-й по величине ключ устанавливается в окончательное положение, но при этом другие ключи также приближаются к своим окончательным позициям [10, С. 262].
2.3. Производительность элементарных методов сортировки
Алгоритмы сортировки выбором, вставками и пузырьковая сортировка по времени выполнения находятся в квадратичной зависимости от числа элементов как в наиболее трудных, так и в обычных случаях, но в то же время они не нуждаются в дополнительной памяти. Таким образом, время их выполнения отличается только постоянным коэффициентом пропорциональности этой зависимости, хотя принципы их работы существенно различаются, о чем свидетельствуют рис. 4,5,6 [10, С. 263].
В общем случае время выполнения алгоритма сортировки пропорционально количеству операций сравнения, выполняемых этим алгоритмом, количеству перемещений или перемен местами элементов, а, возможно, и обоим сразу. В случае ввода данных, упорядоченных случайным образом, сравнение указанных методов сортировки предполагает изучение различий между соответствующими постоянными коэффициентами пропорциональности в зависимости от числа выполняемых операций сравнении и перемены сортируемых элементов местами, а также различий соответствующих постоянных коэффициентов пропорциональности в зависимости от числа выполняемых операций во внутренних циклах. В случае ввода данных со специальными характеристиками времена выполнения различных видов сортировок могут отличаться в большей степени, нежели по значениям указанных выше постоянных коэффициентов пропорциональности [10, С. 263].
Рис. 4. Динамические характеристики сортировки выбором и вставки
Эти снимки сортировки вставками (снизу) и выбором (сверху) на примере случайной последовательности иллюстрируют протекание процессов сортировки указанными выше методами [10, С. 264].
На рисунке процесс сортировки показан в виде графика зависимости a[i] от i для каждого i. Перед началом сортировки на графике представлена равномерно распределенная случайная величина; по окончании сортировки график представлен диагональю, проходящий из левой нижнего угла в правый верхний угол. Сортировка вставками никогда не забегает вперед по отношению к текущей позиции в массиве, в то время как сортировка выбором никогда не возвращается назад [10, С. 265].
На диаграмме ниже (рис. 5) показаны различия в том, как сортировки вставками, выбором, а также пузырьковая сортировка приводят конкретный файл в порядок. Сортируемый файл представлен в виде отрезков, которые сортируются по углу наклона. Черные отрезки соответствуют элементам, к которым в процессе сортировки производится доступ на каждом проходе; серые отрезки соответствуют элементам, которые не затрагиваются. В условиях сортировки вставками (слева) вставляемый элемент проходит примерно половину пути назад через отсортированную часть на каждом проходе. Сортировка выбором (в центре) и пузырьковая сортировка (справа) проходят на каждом проходе через всю неотсортированную часть массива с целью обнаружения там следующего наименьшего элемента; различие между этими методами заключается в том, что пузырьковая сортировка меняет местами каждую пару соседних элементов, нарушающих порядок, которые ей удается обнаружить, в то время как сортировка выбором помещает минимальный элемент в окончательную позицию. Это различие проявляется в том, что по мере выполнения пузырьковой сортировки, неотсортированная часть массива становится все более упорядоченной [10, С. 265].
Рис. 5. Операции сравнения и обмена элементов в условиях элементарных методов сортировки
Стандартная пузырьковая сортировка (слева) похожа на сортировку выбором тем, что на каждом проходе один элемент занимает свою окончательную позицию, но одновременно она асимметрично привносит упорядоченность в остальную часть массива. Поочередная смена направления просмотра массива (т.е. просмотр от начала до конца массива меняется на просмотр от конца до начала и наоборот) дает новую разновидность пузырьковой сортировки, получившей название шейкерной сортировки (справа), которая заканчивается быстрее [6, С. 450].
В общем случае время выполнения алгоритма сортировки пропорционально количеству операций сравнения, выполняемых этим алгоритмом, количеству перемещений или обменов элементов, а, возможно, и тому, и другому сразу. Для случайно упорядоченных данных сравнение элементарных методов сортировки сводится к изучению постоянных коэффициентов, на которые отличаются количества выполняемых операций сравнений и обменов, а также постоянных коэффициентов, на которые отличаются длины внутренних циклов. В случае входных данных с особыми характеристиками времена выполнения различных видов сортировок могут отличаться и более чем на постоянный коэффициент [10, С. 266].
Рис. 6. Динамические характеристики двух пузырьковых сортировок
Алгоритмы сортировки выбором, вставками и пузырьковая сортировка по времени выполнения находятся в квадратичной зависимости от числа элементов как в наиболее трудных, так и в обычных случаях, но в то же время они не нуждаются в дополнительной памяти. Таким образом, время их выполнения отличается только постоянным коэффициентом пропорциональности этой зависимости, хотя принципы их работы существенно различаются [10, С. 266].
Сортировка вставками не относится к категории быстродействующих, поскольку единственный вид операции обмена, который она использует, выполняется над двумя соседними элементами, в связи, с чем элемент может передвигаться вдоль массива лишь на одно место за один раз. Например, если элемент с наименьшим значением ключа оказывается в конце массива, потребуется сделать N шагов, чтобы поместить его в надлежащее место.
Сортировка методом Шелла представляет собой простейшее расширение метода вставок, быстродействие которого выше за счет обеспечения возможности обмена местами элементов, которые находятся далеко один от другого. Сортировка Шелла была названа в честь ее изобретателя – Дональда Шелла, который опубликовал этот алгоритм в 1959 году. Такая модификация метода сортировки позволяет быстро переставлять далекие неупорядоченные пары значений (сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов) [10, С. 269].
Идея заключается в переупорядочении файла таким образом, чтобы придать ему следующее свойство: совокупность h-ых элементов исходного файла (начиная с любого) образует отсортированный файл. В таком случае говорят, что файл h-упорядочен (h-sorted). Другими словами, h-упорядоченный файл представляет собой h независимо отсортированных взаимно проникающих друг в друга файлов. В процессе h -сортировки при достаточно больших значениях h можно менять местами элементы массива, расположенные достаточно далеко друг от друга, и тем самым ускорить последующую h -сортировку при меньших значениях h. Использование такого рода процедуры для любой последовательности значений h, которая заканчивается единицей, завершается получением упорядоченного файла: именно в этом и заключается суть сортировки методом Шелла [10, С. 270].