Основные алгоритмы и их реализация на Python
2.1 Линейные алгоритмы. Операции с числами и строками
Линейный алгоритм — алгоритм, в котором вычисления выполняются строго последовательно. Типичная блок-схема линейного алгоритма показана на рис. 2.1.
Далее рассмотрим типичные задачи с линейной структурой алгоритма.
Блок-схема такого алгоритма показана на рис. 2.2.
Текст программы на «псевдоязыке»:
Метод решения с использованием особенностей Python: использовать два кортежа. В первом будут определены переменные a и b и их значения, а второй сформируем из этих же переменных, но в обратном порядке.
Текст программы на Python:
# Перестановка местами двух чисел с использованием кортежа
(a, b)=input(‘Введите исходные значения (a, b) через запятую: ‘)
print ‘Новое значение а: ‘, a, ‘\n’, ‘Новое значение b: ‘, b
Как описано в разделе 1.4.2, комбинация ‘\n’ означает директиву на перевод строки для команды print.
Задача 2. Известны оклад (зарплата) и ставка процента подоходного налога. Определить размер подоходного налога и сумму, получаемую на руки.
Блок-схема алгоритма показана на рис. 2.3.
Текст программы на «псевдоязыке»:
Программа на Python:
print «Сумма на руки: «, summa
print «Налог: «, nalog
Если все числа в этом примере использовать как целые, то результат может получиться неверным. Поэтому при вычислении налога используется преобразование числителя из целого числа в вещественное (функция float() ).
Задача 3. Используя данные таблицы определить общую стоимость обеда в столовой. Определить, во сколько раз возрастёт стоимость обеда, если цена котлеты увеличится вдвое. 1 Источник: В.А.Молодцов, Н.Б.Рыжикова. Информатика: тесты, задания, лучшие методики. Ростов-на-Дону: Феникс, 2009.
Объяснение алгоритмов сортировки с примерами на Python
Авторизуйтесь
Объяснение алгоритмов сортировки с примерами на Python
В этой статье будут рассмотрены популярные алгоритмы, принципы их работы и реализация на Python. А ещё сравним, как быстро они сортируют элементы в списке.
В качестве общего примера возьмём сортировку чисел в порядке возрастания. Но эти методы можно легко адаптировать под ваши потребности.
Пузырьковая сортировка
Этот простой алгоритм выполняет итерации по списку, сравнивая элементы попарно и меняя их местами, пока более крупные элементы не «всплывут» в начало списка, а более мелкие не останутся на «дне».
Алгоритм
Сначала сравниваются первые два элемента списка. Если первый элемент больше, они меняются местами. Если они уже в нужном порядке, оставляем их как есть. Затем переходим к следующей паре элементов, сравниваем их значения и меняем местами при необходимости. Этот процесс продолжается до последней пары элементов в списке.
При достижении конца списка процесс повторяется заново для каждого элемента. Это крайне неэффективно, если в массиве нужно сделать, например, только один обмен. Алгоритм повторяется n² раз, даже если список уже отсортирован.
Для оптимизации алгоритма нужно знать, когда его остановить, то есть когда список отсортирован.
Реализация
Время сортировки
Если взять самый худший случай (изначально список отсортирован по убыванию), затраты времени будут равны O(n²), где n — количество элементов списка.
Сортировка выборкой
Этот алгоритм сегментирует список на две части: отсортированную и неотсортированную. Наименьший элемент удаляется из второго списка и добавляется в первый.
Алгоритм
На практике не нужно создавать новый список для отсортированных элементов. В качестве него используется крайняя левая часть списка. Находится наименьший элемент и меняется с первым местами.
Теперь, когда нам известно, что первый элемент списка отсортирован, находим наименьший элемент из оставшихся и меняем местами со вторым. Повторяем это до тех пор, пока не останется последний элемент в списке.
Реализация
По мере увеличения значения i нужно проверять меньше элементов.
Время сортировки
Затраты времени на сортировку выборкой в среднем составляют O(n²), где n — количество элементов списка.
Сортировка вставками
Как и сортировка выборкой, этот алгоритм сегментирует список на две части: отсортированную и неотсортированную. Алгоритм перебирает второй сегмент и вставляет текущий элемент в правильную позицию первого сегмента.
Алгоритм
Переходя к другим элементам несортированного сегмента, перемещаем более крупные элементы в отсортированном сегменте вверх по списку, пока не встретим элемент меньше x или не дойдём до конца списка. В первом случае x помещается на правильную позицию.
Реализация
Время сортировки
Время сортировки вставками в среднем равно O(n²), где n — количество элементов списка.
Пирамидальная сортировка
Также известна как сортировка кучей. Этот популярный алгоритм, как и сортировки вставками или выборкой, сегментирует список на две части: отсортированную и неотсортированную. Алгоритм преобразует второй сегмент списка в структуру данных «куча» (heap), чтобы можно было эффективно определить самый большой элемент.
Алгоритм
Сначала преобразуем список в Max Heap — бинарное дерево, где самый большой элемент является вершиной дерева. Затем помещаем этот элемент в конец списка. После перестраиваем Max Heap и снова помещаем новый наибольший элемент уже перед последним элементом в списке.
Этот процесс построения кучи повторяется, пока все вершины дерева не будут удалены.
Реализация
Создадим вспомогательную функцию heapify() для реализации этого алгоритма:
Время сортировки
В среднем время сортировки кучей составляет O(n log n), что уже значительно быстрее предыдущих алгоритмов.
Сортировка слиянием
Этот алгоритм относится к алгоритмам «разделяй и властвуй». Он разбивает список на две части, каждую из них он разбивает ещё на две и т. д. Список разбивается пополам, пока не останутся единичные элементы.
Соседние элементы становятся отсортированными парами. Затем эти пары объединяются и сортируются с другими парами. Этот процесс продолжается до тех пор, пока не отсортируются все элементы.
Алгоритм
Список рекурсивно разделяется пополам, пока в итоге не получатся списки размером в один элемент. Массив из одного элемента считается упорядоченным. Соседние элементы сравниваются и соединяются вместе. Это происходит до тех пор, пока не получится полный отсортированный список.
Сортировка осуществляется путём сравнения наименьших элементов каждого подмассива. Первые элементы каждого подмассива сравниваются первыми. Наименьший элемент перемещается в результирующий массив. Счётчики результирующего массива и подмассива, откуда был взят элемент, увеличиваются на 1.
Реализация
Время сортировки
В среднем время сортировки слиянием составляет O(n log n).
Быстрая сортировка
Этот алгоритм также относится к алгоритмам «разделяй и властвуй». Его используют чаще других алгоритмов, описанных в этой статье. При правильной конфигурации он чрезвычайно эффективен и не требует дополнительной памяти, в отличие от сортировки слиянием. Массив разделяется на две части по разные стороны от опорного элемента. В процессе сортировки элементы меньше опорного помещаются перед ним, а равные или большие — позади.
Алгоритм
Быстрая сортировка начинается с разбиения списка и выбора одного из элементов в качестве опорного. А всё остальное передвигаем так, чтобы этот элемент встал на своё место. Все элементы меньше него перемещаются влево, а равные и большие элементы перемещаются вправо.
Реализация
Существует много вариаций данного метода. Способ разбиения массива, рассмотренный здесь, соответствует схеме Хоара (создателя данного алгоритма).
Время выполнения
В среднем время выполнения быстрой сортировки составляет O(n log n).
Обратите внимание, что алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементам списка. При таких условиях, в отличие от сортировок кучей и слиянием, обе из которых имеют в худшем случае время сортировки O(n log n), быстрая сортировка в худшем случае будет выполняться O(n²).
Встроенные функции сортировки на Python
Иногда полезно знать перечисленные выше алгоритмы, но в большинстве случаев разработчик, скорее всего, будет использовать функции сортировки, уже предоставленные в языке программирования.
Отсортировать содержимое списка можно с помощью стандартного метода sort() :
Или можно использовать функцию sorted() для создания нового отсортированного списка, оставив входной список нетронутым:
Оба эти метода сортируют в порядке возрастания, но можно изменить порядок, установив для флага reverse значение True :
В отличие от других алгоритмов, обе функции в Python могут сортировать также списки кортежей и классов. Функция sorted() может сортировать любую последовательность, которая включает списки, строки, кортежи, словари, наборы и пользовательские итераторы, которые вы можете создать.
Функции в Python реализуют алгоритм Tim Sort, основанный на сортировке слиянием и сортировке вставкой.
Сравнение скоростей сортировок
Для сравнения сгенерируем массив из 5000 чисел от 0 до 1000. Затем определим время, необходимое для завершения каждого алгоритма. Повторим каждый метод 10 раз, чтобы можно было более точно установить, насколько каждый из них производителен.
Пузырьковая сортировка — самый медленный из всех алгоритмов. Возможно, он будет полезен как введение в тему алгоритмов сортировки, но не подходит для практического использования.
Быстрая сортировка хорошо оправдывает своё название, почти в два раза быстрее, чем сортировка слиянием, и не требуется дополнительное место для результирующего массива.
Сортировка вставками выполняет меньше сравнений, чем сортировка выборкой и в реальности должна быть производительнее, но в данном эксперименте она выполняется немного медленней. Сортировка вставками делает гораздо больше обменов элементами. Если эти обмены занимают намного больше времени, чем сравнение самих элементов, то такой результат вполне закономерен.
Вы познакомились с шестью различными алгоритмами сортировок и их реализациями на Python. Масштаб сравнения и количество перестановок, которые выполняет алгоритм вместе со средой выполнения кода, будут определяющими факторами в производительности. В реальных приложениях Python рекомендуется использовать встроенные функции сортировки, поскольку они реализованы именно для удобства разработчика.
Лучше понять эти алгоритмы вам поможет их визуализация.
Базовые алгоритмы с помощью Python
Немного про алгоритмизацию и псевдокод
Алгоритмизация — очень важная штука в жизни программиста. Все владеют этим навыком на разном уровне, однако владеть базовыми вещами должен каждый.
Во многих книгах для алгоритмов используется особый язык — псевдокод.
Пример псевдокода на английском
Как мы видим, тут используются отступы, символ ∈ для перебора элементов множества и многое другое, что в обычных языках не увидишь. Однако если внимательно посмотреть, то многое станет понятным. Использовать псевдокод сегодня мы не будем, информация предоставлена для дополнительного понимания происходящего.
Что здесь будет происходить?
Существует куча алгоритмов, подходящих для определенной задачи. Сегодня мы посмотрим на три базовых алгоритма, о которых будет чуть позже.
Данная статья будет по такой схеме:
Надеюсь всё понятно, теперь поговорим о языке, который мы будем использовать.
Python
Для демонстрации работы таких алгоритмов в реальном языке программирования нам необходим очень понятный и интуитивно понятный синтаксис. Как вы уже поняли из названия, в качестве такого языка я выбрал Python. Объясню несколько вещей, которые могут быть непонятны тем, кто не работал с этим языком:
a, b = b, a — распаковка кортежа(в данном случае обмен значениями двух переменных).
for a in list: — перебор всех элементов массива(эквивалентно foreach в C#)
while a 
Т.к. b в определенный момент может стать больше a, при такой ситуации «свапаем» их значения.
Тестирование
Выглядеть это всё дело будет примерно так:
Теперь оформим тестирование. Для этого воспользуемся форматированием строки.
Конструкция a, b = pair — распаковывает кортеж, присваивая переменной a значение pair[0], а переменной b — pair[1]. Далее подставляем все необходимые значения в строку и смотрим результат:
Все тесты наш алгоритм прошел, что не может не радовать. Теперь подумаем над улучшением нашего алгоритма.
Улучшение
Сейчас нам предстоит подумать над улучшением алгоритма. Мы можем убрать распаковку кортежа и просто через конструкцию if/else изменять числа. Выглядеть это будет так:
Заново протестируем наш алгоритм:
Результат всё тот же. Мы немного улучшили алгоритм и улучшили его читабельность(всё-таки распаковка кортежа может быть кому-то непонятна), при этом не повлияв на результат его работы.
Решето Эратосфена
Реализация
Задача: вывести все простые числа до натурального числа a(a > 2).
Ввод: a ∈ N
Для такой задачи возможно использование простого перебора, однако это будет неэффективно. Здесь мы будем использовать решето Эратосфена, подробное описание есть в Википедии(там даже есть интересная наглядная анимация работы этого алгоритма).
Для тех, кому лень читать, объясню кратко. Суть такова: мы создаем массив всех натуральных чисел от 2 до a по возрастанию. Затем мы берём каждый индекс i и приравниваем к нулю каждый элемент с индексом k*i(k = 1, 2, 3, …).
Здесь мы создаем маску, заполненную единицами(мы можем заменить 1 и 0 на True, False соответственно).
Далее работаем с индексами с помощью вложенного цикла. Здесь мы меняем значения в маске, а позже по маске осуществляем выбор элементов из массива. Для простоты пользуемся методом типа list — list.append().
Тестирование
По традиции, вручную создадим несколько тестов. Алгоритм довольно прост, потому нам понадобятся 3 наборa.
Также само тестируем алгоритм:
Улучшение
Если рассматривать пути улучшения, то можно убрать выбор по маске и воспользоваться возможностями языка в помощи очистки массива от полученных нулей. Получим нечто такое:
С помощью конструкции list(set()) мы очищаем массив от повторений. Затем удаляем лишний ноль и сортируем массив, из-за того, что set() не сохраняет порядок.
Однако такой метод мне не очень нравится, поскольку мы использовали слишком много особенных возможностей языка.
Бинарный поиск
Реализация
Задача: дан отсортированный массив натуральных чисел. Также дано число K. Установить номер позиции, куда необходимо вставить K, чтобы массив не перестал был отсортированным. Если в массиве встречаются числа, равные K, вставлять K следует перед ними.
Ввод: K ∈ N, arr : array;
Для этой задачи подойдёт и способ перебора, однако он имеет линейную сложность (O(N)), а бинарный поиск(тот самый алгоритм, который мы сейчас будем реализовывать) имеет логарифмическую сложность — O(log(N)).
Немного про О большое. Оценка сложности алгоритма служит для понимания, как будут увеличиваться затраты на вычисление в зависимости от изменения вводных данных. Например, если нам на ввод подается число N и для вычисления нам потребуется два цикла, один из которых вложенный, длиною N, то сложность алгоритма оценивается как O(N^2). Обычно константы в О-большом откидываются, ведь никак не влияют на результат(это только отчасти правда, иногда именно константы решают всё).
Именно поэтому существует запись log(N). Разложим log 2 (N) = log A (N) / log A (2), где A — любое число больше нуля и не равны единице. Т.к. log A (2) это константа, то её мы откидываем. Получаем log A (N). А так как A любое число, то мы просто пишем log(N).
Суть бинарного поиска — разделение массива на две части и путём сравнения откидывание одной из них.
Для нашей задачи алгоритм будет выглядеть примерно так:
Отбираем особый случай, когда массив пуст, а дальше ничего сложного.
Тестирование
Теперь мы случайно будем генерировать тестовые данные. Для этого воспользуемся генераторами(не будем вникать в тонкости их работы, просто расскажу, что делает фрагмент кода ниже).
Наш генератор принимает два параметра: N — кол-во возвращаемых массивов и l — их длину. Далее создаем массив с помощью спискового включения, и увеличиваем коэффициенты для следующего.
Теперь, по образцу, запускаем тестирование.
Конечно же, у вас будут другие массивы, т.к. их мы генерируем с помощью random(не забудьте импортировать этот модуль в начале программы).
Насчет улучшения, то тут предоставлена стандартная реализация алгоритма, читабельная и понятная, потому пункт «Улучшение» мы пропустим.
Заключение
Сегодня мы реализовали три базовых алгоритма на языке Python. Вышло довольно неплохо, надеюсь полученные сегодня знания пригодятся вам в будущем. В этой статье переплетаются очень много тем, по которым можно написать отдельные материалы(например О-большое), так что можете попробовать найти интересную информацию об этом в интернете.
Весь код из статьи, разделенный по блокам, можете найти тут.
Также рекомендую прочитать статью Паттерн Декоратор (Decorator)
Язык программирования Python: преимущества, недостатки и область применения
Как устроен Python, чем он хорош, а также кто, как и зачем использует его в работе. Гайд для программистов и интересующихся Python.
Python — это скриптовый язык программирования. Он универсален, поэтому подходит для решения разнообразных задач и многих платформ, начиная с iOS и Android и заканчивая серверными ОС.
Преимущества Python
Это интерпретируемый язык — он не компилируется, то есть до запуска представляет из себя обычный текстовый файл. Программировать можно практически на всех платформах, язык хорошо спроектирован и логичен.
Разработка идёт в разы быстрее, потому что кода здесь куда меньше, чем на других языках. И ещё Python отлично подходит новичкам. Именно с него можно начать свой путь программиста, пройдя практический курс «Python-разработчик» от Skillbox.
Пишет о программировании, в свободное время создает игры. Мечтает открыть свою студию и выпускать ламповые RPG.
Как используется Python
Его можно встретить в вебе и на мобильных устройствах, в приложениях и решениях, связанных с машинным обучением (нейросети и искусственный интеллект), а также в качестве встроенной системы.
Веб-разработка
Чаще всего Python используется в веб-разработке. Для работы с ним подключают фреймворки: Pyramid, Pylons, TurboGears, Flask, CherryPy и — самый популярный — Django.
Существуют и движки для создания сайтов на Python:
Также на Python пишут парсеры для сбора информации в интернете.
Программы
Хоть язык не компилируется, с помощью него создают десктопные программы. Вот, к примеру, что было разработано на Python:
Мобильные приложения
Мобильная разработка на Python менее популярна. Для Android чаще пишут на Java, C#, C++ или Kotlin, а для iOS — на Swift или Objective-C. На Python обычно программируют серверную часть приложения. Например, клиент Instagram для iOS написан на Objective-C, а сервер — на Python.
Многие компьютерные игры были полностью или частично написаны на Python. Существует заблуждение, что этот язык не подходит для серьёзных проектов, но на самом деле он использовался в разработке таких хитов, как:
Несмотря на возможность реализации пользовательского интерфейса и работы с графикой, на Python в основном пишут скрипты — например, взаимодействия персонажей, запуска сцен, а также обработки событий.
Встроенные системы (embedded systems)
На Python разрабатывают встроенные системы для различных устройств. Например, язык прижился в Raspberry Pi (компьютер размером с карту памяти) и в «Сбербанке» для управления банкоматами.
Еще проекты со встроенной системой на Python:
Язык применяется во встроенных системах станков с ЧПУ, средствах автоматического регулирования (температуры, расхода жидкостей, давления и так далее) и в телекоммуникационном оборудовании.
Создание скриптов
Python подходит для написания плагинов и скриптов к уже готовым программам. Например, для реализации игровой логики или создания дополнительных модулей. Скрипты на этом языки встраивают и в программы на других языках, чтобы автоматизировать какие-либо задачи.
Где используется Python
Python широко распространен во многих сферах: от системного администрирования до Data Science.
Системное администрирование
Системным администраторам Python нужен для автоматизации задач. Он простой, мощный и поддерживает специальные пакеты, которые повышают его эффективность. И, самое главное, он по умолчанию установлен на все серверы с ОС Linux.
Благодаря лаконичности Python можно быстро прочитать код и найти слабые места. Форматирование в языке — часть синтаксиса.
Научные исследования
В Python есть несколько библиотек, которые пригодятся для проведения исследований и вычислений:
Благодаря библиотекам и простоте освоения языка многие учёные выбирают Python — особенно он популярен у математиков и физиков.
Data Science
Python — один из самых используемых в Data Science языков. На нём пишут алгоритмы программ с машинным обучением и аналитические приложения. С помощью него обслуживают хранилища данных и облачные сервисы.
Также он помогает парсить данные из интернета. Например, в Google Python применяют для индексации сайтов.
Какие компании используют Python
В основном Python используется стартапами и компаниями, которые разрабатывают крупные проекты. Вот лишь часть огромного списка:
Кроме того, его используют в Instagram, Positive Technologies, Houdini, Facebook, Yahoo, Red Hat, Dropbox, Pinterest, Quora, Mail.ru и Яндексе.
Недостатки языка Python
Несмотря на все достоинства, у языка есть и недостатки.
Программы на Python считаются одними из самых медленных.
Приложения для iOS на Swift работают в 8,7 раз быстрее, чем на Python. Реализация PyPy по скорости близка к Java, но в ней есть не все возможности оригинального языка. Python не подходит для задач, требующих большого объёма памяти, — их лучше решать вставками на C или C++.
Сильная зависимость языка от системных библиотек
Из-за этого затрудняется перенос на другие системы. Для этих целей существует инструмент Virtualenv, но и он с недостатками: избыточность полных методов изоляции, костыли, дублирование системных библиотек.
Global Interpreter Lock (GIL) не позволяет выполнять несколько потоков Python одновременно в реализации CPython.
Однако GIL можно отключить на какое-то время, как это сделано в математическом пакете NumPy.
Трудоустройство и средняя зарплата Python-разработчика
По данным с hh.ru на начало 2019 года, в России
4500 вакансий для Python-разработчиков, из них
700 в Санкт-Петербурге. Это меньше, чем по запросу «Java» (
5500), но больше, чем по запросу «PHP» (
Тенденция в том, что Python медленно забирает позиции PHP с рынка веб-разработки. Хотя на PHP всё ещё написано около 80% всех сайтов в интернете.
Минимальная зарплата по России начинается с 70 000 рублей, а в Москве — с 80 000 рублей. В основном ищут опытных разработчиков, junior-специалисты менее востребованы.
На должность стажёра или младшего специалиста можно устроиться только в крупную компанию, а расположены они в больших городах типа Москвы и Санкт-Петербурга. Из-за этого новичкам крайне сложно устроиться в регионах — остаётся искать заказы на фрилансе.
Если вас заинтересовал Python, пройдите курс от Skillbox — тут вы не только получите необходимые знания и навыки, но и сможете составить привлекательное резюме и добавить дипломную работу в портфолио.