Python. Алгоритмы

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

Исходя из определения графа (туть) можно хранить граф в виде списка вершин и списка ребер. Подобная структура позволяет легко проверить наличие вершины и ребра (A in V ), но задача проверки всех соседей становиться довольно сложной, т.к. нам надо перебрать весь список E и сопоставить его с V. Среди различных способов представления графов выделяют два самых популярных: Оба способа подходят для представления как ориентированных, так и неориентированных графов. Матрица смежности Она подходит для простых графов...

С данной статьи начнем разбирать тему графов и связанных с ними алгоритмов. Итак, Граф – это пара множеств V (англ. vertex) и E (англ. edge) где V – множество вершин E – множество неупорядоченных пар вершин из множества V (множество ребер) Граф может быть ориентированным (часто используют название «орграф»), неориентированным или смешанным. В ориентированном графе, ребра являются направленными (то есть пары в E являются упорядоченными, например, пары (a, b) и (b, a) это два разных ребра)...

Очередной шаг в изучении алгоритмов не мыслим без алгоритмов поиска. И так, перед нами может стоять задача "найти элемент в массиве данных", или "найти положение элемента". Простейшее решение - это пройтись по всему массиву пока мы не обнаружим искомый элемент, а в случае его отсутствия "скажем" что такового не имеется. Такой алгоритм называется Линейным поиском, потому что в худшем случае (когда элемент находится в конце списка размера N) мы совершим N операций сравнения, т.е. время работы алгоритма линейно зависит от размера входного массива - О(n)...

Мы уже упоминали такую структуру данных как стэк(туть). Обычно его описание ведут в сравнении с Очередью. Предлагаю разобраться как они могут быть устроены изнутри. Очередь. Очередь(англ. Queue) – это структура данных основанная на принципе «первый пришел, первый ушел» (англ. FIFO – First In, First Out). Т.е. по принципу очереди в кабинет ко врачу (если не пропускать тех кому "Мне только спросить"). В Python есть свои встроенные реализации (о них в конце статьи), но мы попробуем написать свою. И первое с чего следует начать это определить функциональность нашего класса...

На этой статье я хочу закончить разбирать алгоритмы сортировки (на какое-то время) и уже приступить к другим типам алгоритмов. Но перед этим подведем сравнительный итог по изученному. Как оценивают алгоритмы? Во всех статьях мы разбирали работу алгоритмов в худшем случае, но в реальных задачах нам попадаются совершенно разные данные, в том числе полностью или частично отсортированные. Отсюда возникает необходимость оценки для разных случаев: Расчет сложности для случаев отличных от худшего ведется по аналогии с тем как это проводилось в статьях о конкретной сортировке...

Знаменитая быстрая сортировка. В этой статье разберемся как она работает и насколько же она быстра. Описание: Быстрая сортировка похожа на алгоритм сортировки слиянием. Она так же основана на принципе «разделяй и властвуй» и использует рекурсию. Отличие заключается в том, что сортируемый массив разделяется на две части относительно какого-то элемента, который называют опорным. При этом в левой половине содержатся все элементы меньшие опорного, а в правой – большие. Вопрос: Куда мы денем элементы...

Данную сортировку уже сложно отнести к просто учебным, она имеет достаточно неплохую эффективность. Данный метод очень похож на сортировку выделением с той разницей что мы не ищем максимальный элемент, а всегда знаем где он находится. Это знание нам дает такая структура данных как Куча(Heap). Вооружившись реализацией Кучи из предыдущей статьи, сделать сортировку уже не так уж и сложно. Блок-схема: Программная реализация на Python 3: Алгоритмическая сложность: Мы (n-1) раз производим операцию обмена местами первого и последнего элемента...

У нас на очереди популярная и столь же быстрая как предыдущая пирамидальная сортировка. Но для понимания её принципа действия нам потребуется понять, что из себя представляет такая структура данных как «Куча» (англ. Heap). Именно ей мы и посветим данную статью. Куча представляет собой «пирамиду» из чисел. В программировании такая структура данных называется бинарное дерево. Бинарное дерево – это структура данных дерева, в которой у каждого родительского узла может быть не больше двух потомков. Т...

Сегодня разберем алгоритм, в котором используется несколько интересных приемов программирования. Будет много картинок, куда ж без них. Приятного просмотра! :) Сортировка слиянием – это рекурсивный алгоритм сортировки, основанный на принципе «разделяй и властвуй». Принцип «разделяй и властвуй» - это подход к разработке алгоритмов, заключающийся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче...

Что бы понять что такое рекурсия надо понять что такое рекурсия. Рекурсия — процесс повторения элементов самими элементами. В реальном мире подобное можно наблюдать если зайти в зеркальный лабиринт где есть зеркало №1 которое отражает зеркало №2 в котором отражено зеркало №1 которое… и т.д. Или если вэб-камеру направить на монитор, на который выводится изображение с неё. В программировании Рекурсия – это вызов функции из неё же самой (из тела этой функции). Рекурсию можно рассматривать, как своеобразный цикл...

Еще одна сортировка, не сильно отличающаяся по времени работы от изученных ранее. Алгоритм сортировки выделением достаточно прост и, наверное, это самый интуитивно понятный алгоритм. Описание: Как обычно рассмотрим алгоритм сортировки по возрастанию. В алгоритме выделением мы находим самый маленький элемент входного массива и меняем его местами с элементом в начале, после исключаем данный элемент из поиска и еще раз ищем минимальный элемент, но уже размещаем его после предыдущего минимального и так до тех пор, пока не пройдем по всем элементам массива...