Алгоритмы и структуры данных. Сортировка и поиск. Алгоритмы и виды сортировок

Это задание является последним по дисциплине «Алгоритмы и структуры данных». На следующей неделе вы сдаете экзамен. Студенты, добросовестно выполнявшие все задания по дисциплине в течение семестра, получат экзамен «автоматом». Студенты, не выполнившие ни одного задания, к экзамену допущены не будут. Остальные будут сдавать экзамен по программе всего семестра. I. Изучите по лекции тему «Алгоритмы сортировки и поиска». Лекция приводится в этом же файле далее. II. Выполните следующие задания: а) Проиллюстрируйте процесс упорядочивания заданной последовательности чисел всеми рассмотренными в лекции алгоритмами сортировки. Варианты 1, 3, 5: (20, 4, 45, 23, 1, 2, 6, 88). Варианты 2, 4, 6: (25, 6, 45, 4, 22, 2, 8, 85). б) Модифицируйте функцию для сортировки ключей по невозрастанию. Варианты 1, 3, 5: функцию SelectionSort. Варианты 2, 4, 6: функцию BubbleSort. в) Разработайте версию алгоритма бинарного поиска BinarySearch для случая, когда входной массив упорядочен по неубыванию. Сортировка и поиск Задача сортировки (sorting problem) заключается в упорядочении заданного списка каких-либо элементов в возрастающем порядке. Само собой разумеется, что для определенности задачи структура этих элементов списка должна позволять их упорядочить. На практике обычно требуется отсортировать по возрастанию список чисел, расположить символы и строки в алфавитном порядке или, что наиболее важно, упорядочить набор записей, содержащих различную информацию, наподобие той, что хранится в папках со сведениями об учащихся школы, в читательских формулярах библиотеки, в отделе кадров о сотрудниках организации. В случае набора записей необходимо выбрать фрагмент записи, содержащий данные, по которым будет осуществляться сортировка. Например, набор записей о студентах можно отсортировать по фамилии, идентификационному номеру или по среднему баллу. Специально отобранный фрагмент данных называется ключом (key). Специалисты по информатике часто говорят о сортировке списка ключей, даже если элементы этого списка являются не записями, а целыми числами. Зачем может понадобиться отсортированный список? Например, затем, чтобы облегчить поиск ответов на ряд вопросов, связанных со списком. Наибольшую важность при этом имеет быстрота поиска информации. Вот почему словари, телефонные справочники, списки учащихся и т.п. всегда упорядочиваются по алфавиту. Аналогично сортировка используется также как вспомогательный этап в некоторых важных алгоритмах, относящихся к 1 другим предметным областям, например, к геометрии. К настоящему моменту специалистами по вычислительной технике разработаны десятки алгоритмов сортировки. Несмотря на то, что часть алгоритмов оказывается лучше остальных, пока еще не придуман универсальный алгоритм сортировки, который бы наилучшим образом подходил для всех случаев. Одни из существующих алгоритмов являются простыми, но сравнительно медленными, другие работают быстрее, но более сложны. Некоторые из алгоритмов хорошо работают с неупорядоченными данными, тогда как для других нужно, чтобы списки были частично отсортированы. Часть алгоритмов пригодна только для сортировки списков данных, расположенных в оперативной памяти (т.е. в памяти с быстрым доступом), тогда как другие можно применить для сортировки больших массивов данных, расположенных на внешних носителях данных. Два свойства алгоритмов сортировки заслуживают особого внимания. Алгоритм сортировки называется устойчивым, если в нем сохраняется относительный порядок любых двух равных элементов, находящихся во входном списке. Другими словами, если во входном списке есть два одинаковых элемента, номера которых равны i и j, причем i < j, то в отсортированном списке, где их номера будут, соответственно, равны i’ и j’, будет выполняться отношение i’ < j’. Это свойство может пригодиться в случае, если, например, требуется отсортировать упорядоченный в алфавитном порядке список учащихся согласно их успеваемости (среднему баллу). В случае применения устойчивого алгоритма будет получен список, в котором учащиеся с одинаковым средним баллом будут упорядочены по алфавиту. Вообще говоря, алгоритмы сортировки методом обмена значениями ключей, расположенными на значительном расстоянии друг от друга, не являются устойчивыми, однако обычно они работают быстрее. Второе важное свойство алгоритмов сортировки связано с количеством дополнительной оперативной памяти, необходимой для работы алгоритма. Алгоритм называют обменным, если для его работы не требуется дополнительная оперативная память, кроме случаев возможного использования нескольких дополнительных ячеек памяти. Многие важные алгоритмы сортировки относятся к классу обменных, а другие, не менее важные – нет. Задача поиска связана с нахождением заданного значения, называемого ключом поиска, среди заданного множества. Существует огромное количество алгоритмов поиска, так что есть из чего выбирать. Их сложность варьируется от самых простых алгоритмов поиска методом последовательного сравнения, до чрезвычайно эффективных, но ограниченных алгоритмов бинарного поиска, а также алгоритмов, основанных на представлении базового множества в иной, более подходящей для выполнения поиска форме. Последние из упомянутых здесь алгоритмов имеют особое практическое значение, поскольку применяются в реально действующих приложениях, выполняющих выборку и хранение массивов информации в огромных базах данных. 2 Для решения задачи поиска также не существует единого алгоритма, который бы наилучшим образом подходил для всех случаев. Некоторые из алгоритмов выполняются быстрее остальных, но для их работы требуется дополнительная оперативная память. Другие выполняются очень быстро, но их можно применять только для предварительно отсортированных массивов, и т. п. В отличие от алгоритмов сортировки в алгоритмах поиска нет проблемы устойчивости, но при их использовании могут возникать другие сложности. В частности, в тех приложениях, где обрабатываемые данные могут часто изменяться, причем количество изменений сравнимо с количеством операций поиска, поиск следует рассматривать в неразрывной связи с двумя другими операциями – добавления элемента в набор данных и удаления из него. В подобных ситуациях необходимо видоизменить структуры данных и алгоритмы так, чтобы достигалось равновесие между требованиями, выдвигаемыми к каждой операции. Кроме того, организация очень больших наборов данных с целью выполнения в них эффективного поиска (а также добавления и удаления элементов) представляет собой чрезвычайно сложную задачу, решение которой особенно важно с точки зрения практического применения. Алгоритмы сортировки Постановка задачи. Пусть имеется последовательность (A1, A2, …, An). Необходимо изменить порядок (A1, A2, …, An) на (A'1, A’2, …, A’n) так, что A'1  A’2  …  A’n (или ). Сортировать можно массивы, связанные списки, строки (в лексикографическом порядке). На практике сортируемые значения редко являются изолированными, обычно это записи, а сортируются ключи. При сортировке ключей выполняется перестановка сопутствующих ключу данных, и если эти данные имеют значительный объем, то желательно проводить сортировку массива указателей на данные. Оценка алгоритмов сортировки производится по следующим параметрам. Время сортировки. Это основной параметр, характеризующий быстродействие алгоритма. Хорошей мерой эффективности могут служить: • число необходимых сравнений ключей; • число перестановок элементов. Эти характеристики являются функциями от n – количества сортируемых элементов. Память. Ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например на хранение кода программы. Устойчивость. Метод сортировки называется устойчивым, если в процессе сортировки не меняется относительное расположение элементов с равными ключами. 3 Естественность поведения. Эффективность метода при обработке уже отсортированных или частично отсортированных данных. Алгоритм ведет себя естественно, если учитывает эту характеристику входной последовательности. Сортировки делятся на внутренние и внешние. Внутренние сортировки используются для данных, которые можно поместить в оперативную память ЭВМ. Внешние сортировки упорядочивают информацию, расположенную на внешних носителях. Это накладывает некоторые дополнительные ограничения на алгоритм: • доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только один элемент; • объем данных не позволяет им разместиться в ОЗУ; • доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. В базах данных в большинстве случаев используются внешние сортировки, более того, данные могут располагаться на разных устройствах, соединенных локальной сетью или сетью Интернет. Сортировка выбором Мы начинаем сортировку выбором с поиска наименьшего элемента в списке и обмена его с первым элементом (таким образом, наименьший элемент помещается в окончательную позицию в отсортированном списке). Затем мы сканируем список, начиная со второго элемента, в поисках наименьшего среди оставшихся n – 1 элементов и обмениваем найденный наименьший элемент со вторым, т. е. помещаем второй наименьший элемент в окончательную позицию в отсортированном списке. В общем случае, при iом проходе по списку (0  i  n – 2) алгоритм ищет наименьший элемент среди последних n – i элементов и обменивает его с Ai: После выполнения n – 1 проходов список оказывается отсортирован. Ниже приводится псевдокод данного алгоритма, в котором для простоты предполагается, что список реализован в виде массива. 4 В качестве примера на рис. 1 приведена сортировка выбором следующего списка: 89, 45, 68, 90, 29, 34, 17. Рис. 1. Сортировка выбором списка 89, 45, 68, 90, 29, 34, 17. Каждая строка соответствует одной итерации алгоритма, т. е. сканированию части списка справа от вертикальной черты. Полужирным шрифтом выделены наименьшие элементы, обнаруживаемые при сканировании. Элементы справа от вертикальной черты находятся в окончательных позициях и не сканируются Анализ сортировки выбором выполняется достаточно просто. Размер входных данных определяется количеством n элементов в списке. Базовой операцией алгоритма является сравнение ключей A[j] < A[min]. Общее количество сравнений зависит только от размера массива и определяется следующей суммой: n  2 n 1 n2 n2 (n  1)n C (n)   1  [(n  1)  (i  1)  1]   (n  1  i)  . 2 i  0 j  i 1 i 0 i 0 Таким образом, для любых входных данных алгоритм сортировки выбором принадлежит (n2). Заметим, однако, что количество обменов элементов массива равно (n), точнее, ровно n – 1 – по одному для каждой итерации цикла i. Это свойство отличает сортировку выбором от многих других алгоритмов сортировки. Итоговая сложность алгоритма (n2). Метод может быть неустойчивым. Пусть имеется последовательность 5 из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них, например (2a 2b 1a). Здесь первое поле – ключ, второе – информационное. Работа алгоритма: (2a 2b 1a, 1a 2b 2a, 1a 2b 2a). Результат сортировки можно увидеть уже после шага 1, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a, так что метод неустойчив. Если входная последовательность почти упорядочена, то сравнений будет столько же, как и в случае неупорядоченной последовательности, значит, алгоритм ведет себя неестественно. Пузырьковая (обменная) сортировка Для последовательности A1, A2, …, An работает следующим образом. Начиная с конца последовательности, сравниваются два соседних элемента An и An-1. Если выполняется условие An-1 > An, то значения элементов меняются местами. Процесс продолжается для An-1 и An-2 и т. д., пока не будет произведено сравнение A2 и A1. После этого на месте A1 окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, последними сравниваются элементы A3 и A2. И так далее. На последнем шаге будут сравниваться только текущие значения An и An-1. Хорошо просматривается аналогия с пузырьком, поскольку наименьшие элементы (самые «легкие») постепенно «всплывают» к верхней границе массива. Рассмотрим пример сортировки массива. Рис. 2а. Пример сортировки методом пузырька В учебном пособии (Левитин, А. В. Алгоритмы: введение в разработку и анализ) приводится следующее описание пузырьковой сортировки. Неоднократно выполняя сравнение соседних элементов и их обмен, если они находятся не в надлежащем порядке, мы заставляем наибольший элемент «всплывать» к концу списка. Следующий проход приведет к всплыванию второго наибольшего элемента, и так до тех пор, пока после n – 1 итерации список не будет полностью отсортирован, i-ый проход (0  i  n – 2) пузырьковой сортировки можно представить следующей диаграммой: 6 Ниже приведен псевдокод данного алгоритма. Применение описываемого алгоритма к списку 89, 45, 68, 90, 29, 34, 17 показано на рис. 2б. Рис. 2б. Два первых прохода пузырьковой сортировки списка 89, 45, 68, 90, 29, 34, 17. Каждая новая строка представляет собой результат обмена двух элементов. Элементы справа от вертикальной черты находятся в окончательных позициях и в последующих итерациях алгоритма не участвуют Количество сравнений ключей в данной версии пузырьковой сортировки одинаково для всех массивов размером n. Оно представляется суммой, практически идентичной сумме для сортировки выбором: n  2n  2  i n2 n2 (n  1)n C (n)   1  [(n  2  i)  0  1]   (n  1  i)    n2 . 2 i 0 j 0 i 0 i 0 Количество же обменов элементов зависит от входных данных. В наихудшем случае уменьшающегося массива оно равно количеству сравнений:   7   (n  1)n   n2 . 2 2 Итоговая сложность алгоритма (n ). Sworst (n)  C (n)  Метод пузырька можно усовершенствовать: • если на некотором шаге не было произведено ни одного обмена, то выполнение алгоритма можно прекращать; • можно запоминать наименьшее значение индекса k, для которого на текущем шаге выполнялась последняя перестановка. Верхняя часть массива до элемента с этим индексом уже отсортирована, и на следующем шаге можно прекращать сравнения значений соседних элементов при достижении такого значения индекса, т. к. все пары соседних элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k вместо того, чтобы двигаться до установленной заранее верхней границы i; • метод пузырька работает неравноправно для «легких» и «тяжелых» значений. Минимальный элемент за один цикл сдвигается на свое место, а максимальный – всего лишь на одну позицию. Так что массив (2 3 4 5 1) будет отсортирован за 1 проход, а сортировка массива (5 1 2 3 4) потребует 4 прохода. Для улучшения работы алгоритма можно менять направление следующих один за другим проходов. Получившийся алгоритм называют шейкер-сортировкой (shaker sort). При его применении на каждом следующем шаге меняется направление последовательного просмотра. В результате на одном шаге «всплывает» очередной наиболее легкий элемент, а на другом – «тонет» очередной самый тяжелый. Сортировка вставкой В сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы A1, A2, …, Ai стоят на правильных местах и никуда более не переместятся. В рассматриваемом алгоритме подобное утверждение будет более слабым: последовательность A1, A2, …, Ai упорядочена. При этом по ходу алгоритма в нее будут вставляться новые элементы. Пусть имеется массив ключей A1, A2, …, An. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом: элемент Ai последовательно сравнивается с элементами Ai-1, Ai-2 … до тех пор, пока для очередного элемента Aj не выполнится соотношение Aj > Ai, тогда Ai и Aj меняются местами. Проверка продолжается дальше. Переход к обработке следующего элемента Ai+1 будет производиться в том случае, если удается встретить такой элемент Aj, что Aj  Ai, или если достигнута нижняя граница массива. Алгоритм завершается, если обработана верхняя граница массива. Рассмотрим пример сортировки вставкой. 8 Рис. 3а. Пример сортировки вставкой Хотя сортировка вставкой основана на рекурсивном подходе, более эффективной будет ее реализация снизу вверх, т.е. итеративная. Как показано на рис. 3б, элемент А[i] (начиная с элемента А[1] и заканчивая A[n – 1]) вставляется в соответствующее место среди первых i элементов массива (которые к этому моменту уже отсортированы). Однако в отличие от сортировки выбором элемент в общем случае вставляется не в окончательную позицию, которую он будет занимать в полностью отсортированном массиве. Рис. 3б. Итерация сортировки вставкой: А[i] вставляется в корректную позицию среди уже отсортированных элементов Ниже приведен псевдокод данного алгоритма. Работа алгоритма проиллюстрирована на рис. 4. 9 Рис. 4. Пример сортировки вставкой. Вертикальная черта отделяет отсортированную часть массива от остальных элементов; вставляемый элемент выделен полужирным шрифтом Базовой операцией алгоритма является сравнение ключей A[j] > v. Количество сравнений ключей в этом алгоритме, очевидно, зависит от природы входных данных. В худшем случае сравнение A[j] > v выполняется наибольшее количество раз, т.е. для всех j = i – 1, …, 0. Поскольку v = A[i], это происходит тогда и только тогда, когда A[j] > A[i] для j = i – 1, …, 0. (Заметим, что мы используем тот факт, что на i-ой итерации сортировки вставкой все элементы, предшествующие A[i], – первые i элементов входных данных, хотя и расположенные в отсортированном порядке.) Таким образом, для входных данных для наихудшего случая мы получаем A[0] > A[1] (для i = 1), A[1] > A[2] (для i = 2), ..., A[n – 2] > A[n – 1] (для i = n – 1). Другими словами, входные данные в наихудшем случае представляют собой массив строго уменьшающихся значений. Количество сравнений ключей для таких входных данных равно n 1 i 1 (n  1)n Cworst (n)   1    n2 . 2 i 1 j  0 Общая сложность алгоритма (n2).   Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это вместе с устойчивостью алгоритма делает метод хорошим выбором при относительно невысоких значениях n. Сортировка вставкой хорошо применима для сортировки связных списков. Каждый следующий элемент i извлекается из списка и устанавливается на свое место в отсортированном массиве [1..i – 1]. Пример сортировки списка изображен на рис. 5. Рис. 5. Сортировка связного списка методом вставки 10 Рисунок отражает один шаг преобразования сортировки связного списка. Элемент со значением 39 вставляется на свое место в отсортированной части списка, состоящей из элементов 25, 28 и 47. Изменения в структуре списка при этом такие же, как и при добавлении нового элемента в произвольную часть списка. Сортировка слиянием Алгоритм внутренней сортировки слиянием (merge sort) – один из популярных алгоритмов сортировки. Основная идея алгоритма заключается в методе слияния двух отсортированных последовательностей. Этот же принцип является основой внешней сортировки. Пусть имеются два отсортированных в порядке возрастания массива с элементами A1, A2, …, An и B1, B2, …, Bn и имеется пустой массив C1, C2, …, C2n, который мы хотим заполнить значениями массивов А и В в порядке возрастания. Для слияния выполняются следующие действия: сравниваются A1 и B1, и меньшее из значений записывается в C1. Предположим, что это значение A1. Тогда A2 сравнивается с B1, и меньшее из значений заносится в C2. Предположим, что это значение B1. Тогда на следующем шаге сравниваются значения A2 и B2 и т. д., пока мы не достигнем границ одного из массивов. Остаток другого массива просто дописывается в «хвост» массива С. Для сортировки со слиянием исходного неупорядоченного массива A1, A2, …, An заводится парный массив B1, B2, …, Bn. На первом шаге производится слияние A1 и An с размещением результата в B1, B2, слияние A2 и An-1 с размещением результата в B3, B4, и так далее. Результат слияния An/2 и An/2+1 помещается в Bn-1, Bn. На втором шаге производится слияние пар B1, B2 и Bn-1, Bn с помещением результата в A1, A2, A3, A4, слияние пар B3, B4 и Bn-3, Bn-2 с помещением результата в A5, A6, A7, A8, слияние пар Bn/2-1, Bn/2 и Bn/2+1, Bn/2+2 с помещением результата в An-3, An-2, An-1, An. И так далее. На последнем шаге производится слияние последовательностей элементов массива длиной n/2: A1, A2, …, An/2 и An/2+1, An/2+2, ..., An с помещением результата в B1, B2, …, Bn. (или, наоборот, в A1, A2, …, An в зависимости от значения n). Сортировка слиянием обычно реализуется рекурсивно. На каждом шаге рекурсии массив разбивается на два подмассива, каждый из которых также разбивается на два подмассива и так далее. Рекурсия достигает своего нижнего предела, когда длина сортируемой последовательности становится равной 1. В этом случае вся работа уже сделана, поскольку любую такую последовательность из одного элемента можно считать упорядоченной. 11 Рис. 6. Пример сортировки слиянием Ниже приведена функция Mergesort, которая реализует этот алгоритм. 12 Рис. 7. Другой пример работы алгоритма сортировки слиянием Оценим сложность алгоритма. Вызов любой рекурсивной функции выглядит как дерево. Такое дерево еще называют деревом рекурсии. Каждый уровень дерева представляет собой один или несколько вызовов функции. Узлы дерева, не имеющие потомков (терминальные листья), представляют те вызовы функции, которые прекращают рекурсию. Высота дерева в случае сортировки слиянием равна log2n, поскольку на каждом шаге исходный массив разбивается на два подмассива длиной n/2. После разбиения производится операция слияния. Операция слияния требует n сравнений и повторяется, соответственно, log n раз, то есть 1 раз для каждого уровня дерева. Асимптотика решения тогда равна O(nlogn). Алгоритмы поиска Последовательный (прямой, линейный) поиск Если нет никакой дополнительной информации о способе хранения данных, т. е. вероятнее всего данные расположены в произвольном порядке, то очевидный подход – простой последовательный просмотр массива. Задача последовательного поиска решается с помощью довольно простого алгоритма, который выполняет поиск заданного элемента (ключа поиска K ) в списке, состоящем из n элементов, путем последовательного сравнения ключа K с каждым из элементов списка. Работа алгоритма 13 завершается, либо когда заданный ключ найден, либо когда весь список исчерпан. Ниже этот алгоритм описан на псевдокоде. В нем для простоты полагается, что список задан в виде массива чисел. (Кроме того, предполагается, что второе условие A [i]  K не будет проверяться в случае, если не выполняется первое условие, в котором проверяется, не выходит ли индекс массива за его верхнюю границу.) Совершенно очевидно, что время работы этого алгоритма может отличаться в очень широких пределах для одного и того же списка размера п. В наихудшем случае, т.е. когда в списке нет искомого элемента либо когда искомый элемент расположен в списке последним, в алгоритме будет выполнено наибольшее количество операций сравнения ключа со всеми n элементами списка: Cworst (n)  n . Зачастую применяется простой дополнительный прием: если добавить ключ поиска в конец списка, то поиск обязательно будет успешным, следовательно, можно убрать проверку завершения списка в каждой итерации алгоритма. Далее приведен псевдокод такой улучшенной версии; предполагается, что входные данные имеют вид массива. 14 Сложность рассмотренного алгоритма также равна O(n). Если исходный список отсортирован, можно воспользоваться еще одним усовершенствованием: поиск в таком списке можно прекращать, как только встретится элемент, не меньший ключа поиска. Бинарный поиск Алгоритм бинарного поиска является одним из наиболее эффективных алгоритмов поиска в упорядоченном массиве. Упрощенно этот алгоритм состоит в следующем. Он работает путем сравнения искомого ключа K со средним элементом массива A[m]. Если они равны, алгоритм прекращает работу. В противном случае та же операция рекурсивно повторяется для первой половины массива, если K < A[m], и для второй, если K > A[m]: В качестве примера найдем ключ K = 70, применяя алгоритм бинарного поиска к массиву Итерации алгоритма показаны в следующей таблице: Хотя ясно, что бинарный поиск основан на рекурсии, его очень легко реализовать как нерекурсивный алгоритм. Вот псевдокод нерекурсивной версии. 15 Стандартный способ анализа эффективности бинарного поиска состоит в подсчете количества сравнений искомого ключа с элементами массива. Кроме того, из соображений простоты, мы будем считать, что используются тройные сравнения, т. е. что одно сравнение K и A[m] позволяет определить, меньше ли K, больше или равно значению A[m]. Количество сравнений в наихудшем случае Cworst (n)  log 2 n  1 log n. Если ограничиться только операцией сравнения ключей, то бинарный поиск является оптимальным алгоритмом, однако имеются алгоритмы поиска (интерполяционный поиск, хеширование) с лучшим временем работы в среднем, а один из этих алгоритмов (хеширование) даже не требует, чтобы массив был отсортирован! Однако эти алгоритмы, кроме сравнения ключей, требуют некоторых специальных вычислений. Идея, лежащая в основе бинарного поиска, имеет ряд применений помимо поиска. Кроме того, она может быть использована для решения нелинейных уравнений. 16