Файл: Рекурсивные и итерационные алгоритмы: особенности и примеры использования (Структура итерационного алгоритма).pdf

Рис. 8: Программный код для сортировки вставкой (Источник: [4])

На рисунке 8 легко узнается цикл с предусловием.

Один из самых популярных в учебной литературе алгоритмов сортировки – это сортировка пузырьком. Ее смысл заключается в попарном сравнении ключей элементов массива, больший и меньший элемент меняются местами так, что постепенно элемент с наименьшим ключом как бы всплывает в начало массива. Неудобство метода состоит в том, что требуется много проходов по всему массиву, поэтому данный способ сортировки является, скорее, учебным, однако, на его основе были разработаны более совершенные методики – например, перемешиванием, быстрая [7].

Рис. 9: Сортировка пузырьком

Видим, что цикл сравнения i-того и i+1-го элемента повторяется, пока сортировки не перестанут требоваться.

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

Глава 4. Структура рекурсивного алгоритма

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

Наиболее часто приводится пример с вычислением факториала числа с использованием рекурсии.

Рис. 9: Вычисление факториала на JavaScript

Интересен сам процесс выполнения программы с рекурсией. При заданном значении n вызывается функция factorial для вычисления factorial(n); затем выполнение функции будет приостановлено, и вызывается эта же функция factorial для вычисления factorial (n - 1) и так далее до n = 0 – а это уже базовый случай. Таким образом, у нас появляется стек вызовов функции (n+1 вызов), которые будут выполняться от 0 до n [2].

Прямую связь с рекурсивными алгоритмами имеет метод программирования, называемый «Разделяй и властвуй» (divide-and-conquer, [4]). В общих чертах, соблюдается три этапа моделирования алгоритма:

1) Разделение основной задачи на подзадачи;

2) Рекурсивное решение подзадач (они также могут, в свою очередь, разбиваться на подзадачи, а достаточно малые подзадачи будут решаться как базовые случаи);

3) Слияние найденных решений подзадач в одно общее решение.

Этот метод будет необходим при рассмотрении некоторых других типов алгоритмов сортировки и поиска.

Глава 5. Примеры использования рекурсивных алгоритмов

5.1 Алгоритм бинарного поиска

Суть данного алгоритма заключается в том, что уже отсортированный массив разбивается на две части, и поиск проходит в части массива. Возможно представить его и в итерационном виде, но мы воспользуемся подходом divide-and-conquer.

Рис. 10: Описание процедуры бинарного поиска в рекурсивном представлении с использованием псевдокода (Источник: [3])

Что происходит при выполнении кода? Выбираем элемент массива с индексом середины массива и сравниваем ее ключ с искомым. Если найденный ключ больше искомого, рассматриваем часть массива от 1 до найденного, и наоборот. С просматриваемой частью массива процедура повторяется, пока сверяемый элемент не окажется искомым либо пока размер просматриваемой части массива не станет равен 0 – это приведет к результату Not Found.

5.2 Алгоритмы сортировки с использованием подхода divide-and-conquer

Ярким примером парадигмы divide-and-conquer является сортировка слиянием [4]. Рассмотрим ее общий смысл.

Разделение массива из n элементов на 2 подмассива размера n/2;

1. Рекурсивно сортируем подмассивы (то есть при сортировке двух подмассивов их также разбиваем пополам);
2. Соединяем получившиеся отсортированные подмассивы в один массив.

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

Рис. 11: Сортировка слиянием, описанная с помощью псевдокода (Источник: [3])

На процедуре MERGE заострять внимание в рамках этой работы мы не будем.

Сортировка слиянием, как было уже выше сказано, более требовательна к памяти, чем следующий алгоритм – быстрая сортировка. Этот способ также основан на подходе divide-and-conquer, но так же, как и пузырьковая сортировка, будет осуществляться «на месте» [3].

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

Рис. 12: Наглядное изображение работы алгоритма быстрой сортировки (Источник: [3])

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

Прежде чем перейти к практическим аспектам, подведем небольшой итог.

Мы рассмотрели два типа алгоритмов поиска – линейный (несколько его вариантов) и бинарный. С одной стороны, выполнение алгоритма бинарного поиска быстрее [4], но, в отличие от линейного, для его работы требуется предварительная сортировка элементов массива.

Также мы познакомились с пятью методами сортировки массива. Это сортировки выбором, вставкой, пузырьком, слиянием и быстрая. Две последних производятся с помощью парадигмы divide-and-conquer, используя рекурсию, первые же три решают поставленную задачу «в лоб» (так называемый метод грубой силы [6]). За исключением сортировки слиянием, все перечисленные способы сортировки дают в результате готовые отсортированные массивы. Последним этапом сортировки слиянием будет собственно слияние полученных отсортированных подмассивов.

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

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

Например, поговорим о механизмах сопоставления и ранжирования, используемых в поисковых системах. Недостаточно только найти совпадения на веб-страницах с поисковым запросом, требуется также расположить эти страницы в порядке релевантности для удобства пользователя. Поисковая система Google смогла стать лучшей в своей нише именно благодаря совершенствованию алгоритмов ранжирования [5].

Одной из первых поисковых машин стала AltaVista, появившаяся в 1995 году. Основой работы поисковой системы служит принцип индексирования – с каждым словом или фразой сопоставляется номер страницы, на которой оно встречается (аналогия – алфавитный указатель в конце книги). Такой индексированный список, очевидно, отсортирован, что помогает произвести в нем поиск. Также индексируются положения слов на странице – таким образом, у каждого слова как у объекта поиска есть два атрибута – номер страницы и номер положения на странице. Это существенно облегчает поиск по фразам, а также приближает нас к возможности найти релевантный ответ на свой запрос. Для этого искомые слова на найденной странице должны встречаться рядом. Также в AltaVista использовался и поиск в названии или теле веб-страницы с помощью метаслов, относящихся к коду страницы и не отображающихся в браузере. [5]

Но именно алгоритм PageRank, осуществляющий ранжирование найденных страниц по их релевантности к поисковому запросу помог вырваться Google на вершину успеха [5].

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

Также описанные в данной работе алгоритмы работают во всех программах, работающих с базами данных. Это и табличный процессор MS Excel, и такие СУБД, как Access или SQL, и более сложные компьютерные системы, в которых требуется поиск и/или каталогизация документов. Очень распространены CRM-системы, позволяющие хранить и просматривать все обращения конкретного клиента в компанию, отправлять и запрашивать документы, и многое другое (яркий пример - MS CRM). Программы Siri и OK Google, являющиеся, по сути, искусственным интеллектом [5], из нескольких возможных вариантов ответа на запрос также должны выдать адекватный ответ, идет в том числе поиск нужного ответа в базе возможных.