Лекция №2. Алгоритмы сортировки и поиска

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

Введение

Что такое алгоритм сортировки?

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

Что можно сортировать?

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

Для чисел характерно поразрядное сравнение — сначала сравниваются старшие разряды, затем младшие (например сотни, десятки, единицы). Если у двух чисел количество разрядов разное, то меньшим считается то число, у которого число разрядов меньше.

Для строк обычно применяется лексикографическое сравнение (как в словаре). В нём все слова на букву «а» идут раньше чем слова на букву «б» независимо от их длины.

Сравнение алгоритмов

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

Но, как уже говорилось в предыдущей лекции, основным параметром сравнение алгоритмов является асимптотическая сложность — O(n), O(n·log(n)), O(n?) и т.д. Если Вы не знакомы с этим понятием, рекомендуем прочитать первую лекцию.

Алгоритмы сортировки

Сортировка пузырьком (Bubble sort)

Сама известная сортировка — сортировка пузырьком. Очень простая для понимая и лёгкая в реализации.

Алгоритм проходит по массиву много раз, каждый раз сравнивая пару соседних друг с другом чисел.

Если числа стоят не в том порядке, в котором должны, они меняются местами.

Элементы сравниваются каждый с каждым. Самый большой элемент «всплывает» наверх (как пузырёк воздуха в воде)

Асимптотическая сложность данного алгоритма — O(n?). Следовательно, это весьма медленная сортировка. Однако её можно применять, когда количество элементов не большое, и её достаточно легко запрограммировать. Чаще всего код представляет из себя два вложенных цикла, перебирающие все элементы массива. Кроме того, можно досрочно закончить сортировку, если в процессе проверки элементов не было сделано ни одной перестановки, т.к. в данном случае очевидно, что массив уже отсортирован.

Шейкерная сортировка (Shaker sort)

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

Второе, что вы могли заметить – это то, что максимальный (самый «тяжелый» элемент) при сортировке перемещается в самый конец массива, а «легкие» элементы сдвигаются только на одну позицию вниз.

Если предусмотреть и улучшить эти два нюанса, то получится более эффективная форма сортировки пузырьком — «шейкерная» (от англ. «shake» — трясти)

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

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

В среднем, такая сортировка работает немного быстрее. Но в общем случае асимптотическая сложность этой сортировки остаётся O(n?).

Сортировка расчёской (Comb sort)

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

Изначально элементы сравниваются на некотором расстоянии друг от друга.

С каждой итерацией это расстояние уменьшается, доходя до сравнения соседних элементов.

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

При анализе этого метода возникает вопрос:
На каком расстоянии стоит сравнивать элементы?

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

Число, на которое должен раз за разом уменьшаться разрыв, было названо фактором уменьшения и выведено авторами сортировки формулой, где ? — золотое сечение.

Асимптотическая сложность этой сортировки — O(n?).

Сортировка слиянием (Merge Sort)

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

Далее возникает вопрос:
Как получить эти два отсортированных массива?

Ответ весьма прост:
Разбить массив пополам и отсортировать каждую из полученных частей этим же методом. Рекурсивно.

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

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

• Разделение массива на две части, затем разделение каждой из этих частей на две ещё более мелкие части и так далее пока не останутся все части из одного элемента.
• Слияние в нужном порядке всех мелких частей в более крупные до получения единого отсортированного массива.

Асимптотическая сложность данного алгоритма — O(n·log(n)). Это значительно лучше предыдущих сортировок. Однако, есть и небольшой недостаток данного алгоритма. Для реализации данного метода требуется дополнительная память по объему равная исходному массиву.

Быстрая сортировка или сортировка Хоара (Quick Sort)

Быстрая сортировка, сортировка Хоара (за рубежом называемая quicksort), широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

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

Процесс перестановки элементов выполняется по следующему алгоритму:

• Задаётся указатель «left» — индекс крайнего левого элемента, который больше ключевого.
• Задаётся указатель «right» — индекс крайнего правого элемента, который меньше или равен ключевого.
• Если «left» находится правее чем «right», то перестановка закончена, меняем местами ключевой элемент и «left»-элемент,
  иначе меняем местами «left» и «right» элементы и снова задаём указатели вышеупомянутым способом.

Ключевой элемент выбирается произвольно. Это не влияет значимым образом на процесс сортировки.

В среднем и в большинстве своём случаев, данная сортировка выполняется за O(n·log(n)) операций. Но в худшем случае, алгоритм может деградировать до O(n?) — подробнее можно ознакомиться в разделе «Оценка сложности алгоритма» на странице Быстрая сортировка.

В заключение раздела по сортировкам представляем Вашему вниманию один из множества залипательных видеороликов визуализации алгоритмов сортировок

Алгоритмы поиска

Линейный поиск (последовательный)

Самый простой (но не всегда самый эффективный) – линейный поиск.

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

Недостатки:

• Асимптотическая сложность — O(n)

Преимущества:

• Исходный массив может быть неупорядоченным

Пример реализации:

Бинарный поиск

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

На каждой итерации

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

Недостатки:

• Исходный массив может быть упорядоченным

Преимущества:

• Асимптотическая сложность — O(log(n))

Пример реализации:

Поиск по бинарному дереву

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

Для бинарного дерева выполняются следующие условия:

• Оба поддерева — левое и правое — являются двоичными деревьями поиска
• У всех узлов левого поддерева любого узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
• У всех узлов правого поддерева любого узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X.

Поиск выполняется последовательным спуском по дереву с учётом сравнения со значениями рассматриваемых вершин.

Например, для построенного выше дерева ищем число 6:

1. Искомое число 6 меньше значения корня 8? — Да, переходим к левому поддереву.
2. Искомое число 6 меньше 3? — Нет, переходим к правому поддереву.
3. Искомое число 6 равно 6? — Да, число найдено.

Асимптотическая сложность в среднем — O(log(n)).
В худшем случае (если исходный массив отсортирован) — O(n).

Заключение

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

Будем рады, если Вы оставите отзыв о статье или предложите что-нибудь интересное в качестве дополнения.

Вы можете написать в сообщения сообществаОлимпиадное программирование МИЭТ vk.com/miet_acm

Источник: m.vk.com

Комментарии: