Файл: Алгоритмы сортировки данных (Алгоритмы устойчивой сортировки).pdf

Введение

Данная курсовая работа будет посвящена одной из самой важных тем, на мой взгляд. Ведь в XXI веке данные – это крайне важный ресурс, сортировка которого позволяет систематизировать их, для упрощения работы с ними. Но для начала пройдемся по терминам, которые необходимо знать, изучая этот вопрос. Начнём с того, что такое данные. Данные - это информация, которая передаётся при помощи определённых способов кодирования: словами, цифрами, кодами, алгоритмами и т.д. Вообще, алгоритмы поиска делятся на поиск в неупорядоченном множестве данных и поиск в упорядоченном множестве данных. Упорядоченность – это наличие сортировки в ключевом поле. Сортировка - перестановка элементов в подмножестве данных по определенному критерию. Например: в качестве критерия используется некоторое числовое поле, называемое ключевым. Упорядочение элементов по ключевому полю предполагает, что ключевое поле каждого следующего элемента не больше предыдущего (сортировка по убыванию). Если ключевое поле каждого последующего элемента не меньше предыдущего, то говорят о сортировке по возрастанию. А теперь перейдём к самому интересному – видам сортировки данных. Они подразделяются на алгоритмы устойчивой сортировки и алгоритмы неустойчивой сортировки

Глава I. Алгоритмы устойчивой сортировки

1.1 Сортировка пузырьком

Есть достаточно много различных методов, большинство из них не имеет широкой известности. Сортировка методом пузырька , которую также называют сортировкой простого обмена.

Для начала , что такое сортировка в паскале и зачем она нужна? Сортировка - это метод упорядочить массив (обычно по возрастанию или убыванию) . В задачах встречаются такие строки "расположить элементы массива , начиная от минимального (максимального)" . Имейте ввиду , что это то же самое.

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

Сортировка методом пузырька

Теперь подробнее о самом алгоритме. Все достаточно просто :

1. Для сортировки используется 2 цикла , один вложен в другой . Один используется на шаги , другой на подшаги.

2. Суть алгоритма - это сравнение двух элементов . Именно двух . Поясняю , например имеем массив с 10-ю элементами. Элементы будут сравниваться парами : 1 и 2, 2и 3,3 и 4,4 и 5,6 и 7 и т.д. При сравнении пар , если предыдущий элемент оказался больше чем последующий - то их меняют местами . Например если второй элемент равен 5 , а третий 2 , то они их поменяют местами.

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

Идея алгоритма очень простая. Идём по массиву чисел и проверяем порядок (следующее число должно быть больше и равно предыдущему), как только наткнулись на нарушение порядка, тут же обмениваем местами элементы, доходим до конца массива, после чего начинаем сначала. Например:

Отсортируем массив {1, 5, 2, 7, 6, 3}

Идём по массиву, проверяем первое число и второе, они идут в порядке возрастания. Далее идёт нарушение порядка, меняем местами эти элементы

1, 2, 5, 7, 6, 3

Продолжаем идти по массиву, 7 больше 5, а вот 6 меньше, так что обмениваем из местами

1, 2, 5, 6, 7, 3

3 нарушает порядок, меняем местами с 7

1, 2, 5, 6, 3, 7

Возвращаемся к началу массива и проделываем то же самое

1, 2, 5, 3, 6, 7

1, 2, 3, 5, 6, 7

Это больше похоже на "всплытие" более "лёгких" элементов, как пузырьков, отчего алгоритм и получил такое название.

(см. приложение, Рисунок 1 Пример написания такой сортировки в JavaScript:)

1.2 Шейкер сортировка

Рассмотрев «пузырьковую» сортировку массива можно перейти к разбору её разновидности — «шейкер»-сортировке. Внимательно присмотревшись к тому, как проходит сортировка «пузырьком» — можно сказать следующее: часть массива, в котором перестановки элементов уже не происходят (отсортированная часть массива), то эту часть можно исключить из рассмотрения и не обрабатывать на следующих итерациях. Поэтому была придумана более эффективная форма сортировки «пузырьком» -«шейкер»-сортировка. В ней пределы той части массива в которой есть перестановки, сужаются. Плюс — внутренние циклы проходят по массиву то в одну, то в другую сторону, поднимая самый легкий элемент вверх и опуская самый тяжелый элемент в самый низ за одну итерацию внешнего цикла.

Шейкер-сортировка является усовершенствованным методом пузырьковой сортировки.

Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства:

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

при движении от конца массива к началу минимальный элемент "всплывает" на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.

Эти две идеи приводят к модификациям в методе пузырьковой сортировки.

От последней перестановки до конца (начала) массива находятся отсортированные элементы. Учитывая данный факт, просмотр осуществляется не до конца (начала) массива, а до конкретной позиции. Границы сортируемой части массива сдвигаются на 1 позицию на каждой итерации.

Массив просматривается поочередно справа налево и слева направо.

Просмотр массива осуществляется до тех пор, пока все элементы не встанут в порядке возрастания (убывания).

Количество просмотров элементов массива определяется моментом упорядочивания его элементов.

Рассмотрим алгоритм Шейкер-сортировки на примере. Дана последовательность

(см. приложение, рисунок 2 Пример)

(См. приложение, Рисунок 3 Пример написания такой сортировки в Pascal)

1.3 Гномья сортировка

Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, который перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов. В пример можно отнести причину названия этого способа гномьим. Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

Незамысловатый обменный алгоритм с неплохой сложностью O(n2), который, как ни парадоксально, совсем недавно был впервые описан в научной литературе.

«Новую сортировку» презентовал на страницах научного издания Newsletter Университета Глазго, некий Хамид Сарбази-Асад (Hamid Sarbazi-Azad) в 2000 году. Он предложил название «Глупая сортировка».

Голландский учёный Дик Грун (Dick Grune) исследовал метод подробнее и переименовал в «Гномью сортировку», под этим именем алгоритм сейчас и известен.

Алгоритм

«Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.»

Гномья сортировка это оптимизированная глупая сортировка. В глупой сортировке при нахождении неотсортированной пары соседей происходит обмен и возврат в начало массива. В гномьей сортировке просто делается один шаг назад.

Также алгоритм интересен тем, что используется всего лишь один цикл, что для алгоритмов сортировок большая редкость.

Оптимизация

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

Гномья сортировка

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

(см. приложение, Рисунок 4 Пример применения такой сортировки в Java)

1.4 Сортировка вставками

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

Начало d c a b

Проход 1 c d a b

Проход 2 a c d b

Проход 3 a b c d

В отличие от пузырьковой сортировки и сортировки посредством выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n - 1; в противном случае его производительность является величиной порядка n2.

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

Несмотря на то, что количество сравнений при определенных наборах данных может быть довольно низким, при каждой вставке элемента на свое место массив необходимо сдвигать. Вследствие этого количество перемещений может быть значительным.

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

(см. приложение, рисунок 5 Пример)

(см. приложение, рисунок 6 Пример реализации в Java)

1.5 Сортировка слиянием

Сортировка слиянием (marge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. (так говорит Википедия).

То есть, на входе мы получаем некий массив данных (для простоты и удобства, будем рассматривать целочисленный массив) на n элементов. Затем, делим этот массив на два подмассива размером n/2. И так до тех пор, пока массив не уменьшится до двух элементов, которые достаточно просто отсортировать. Как вы уже могли понять, процедура дробления осуществляется путем рекурсии.