Сортировка

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

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

Сортировка выбором

Сортировка выбором может быть реализована в четыре этапа:

1. Зафиксировать первый элемент массива, с которым будем сравнивать остальные элементы массива.
2. Найти максимум (минимум) в неотсортированном массиве.
3. Поменять местами найденный максимум (минимум) с зафиксированным элементом массива.
4. Если массив не стал полностью отсортированным, то зафиксировать следующий элемент массива и повторить пункты 2 и 3.

Пример. Для массива [5, 3, 4, 2, 1] сортировка выбором будет выглядеть следующим образом:

Пример. Сортировка выбором на Python можно реализовать следующим образом:

Алгоритм сортировки пузырьком

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

Пример. Для массива [2, 1, 4, 3, 5] сортировка пузырьком будет выглядеть следующим образом:

Пример. Сортировка пузырьком на языке Python можно реализовать следующим образом:

Сортировка методом вставок

Суть сортировки вставками заключается в двух правилах:

1. Перебираются элементы в неотсортированной части массива.
2. Каждый элемент вставляется в отсортированную часть массива на то место, где он должен находиться.

Пример. Для массива [3, 2, 1, 5, 4] сортировка вставками можно проиллюстрировать в виде:

Пример. Данная сортировка сложнее описывается на Python, зато быстрее обрабатывает большие массивы. Пример кода для массива [3, 2, 1, 5, 4] представлен ниже:

Функция sort()

В Python существует функция sort(), которая позволяет выполнить сортировку массива. Нет необходимости присваивать данную функцию какой-либо переменной, так как sort() принимает значения и меняет порядок элементов исходного массива.

Чтобы выполнить сортировку массива a по возрастанию достаточно просто вызвать функцию:

a.sort()

При необходимости выполнять сортировку массива а по убыванию, достаточно дописать в скобки параметр reverse, равным 1:

a.sort(reverse = 1)