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

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

Теория алгоритма сортировки

1. Алгоритм вставки

Алгоритм вставки использует метод сравнения на месте. Его средняя сложность и сложность наихудшего случая составляет O (n²).

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

Для объяснения мы будем использовать следующий список чисел: numbers = [6, 4, 3, 10]. В примерах первый массив представляет отсортированный список, тогда как второй массив все еще нуждается в сортировке.

Шаг 1

Compare 6 and 4
1.1 -> [] [4, 6, 3, 10]  // 6 and 4 needed to swap places
1.2 -> [4] [6, 3, 10]    // 4 is now part of the sorted list

Шаг 2

compare 6 and 3
2.1 -> [4], [3, 6, 10]       // 6 and 3 needed to swap places
2.2 -> [] [4, 3, 6, 10]      // 3 < 4 -> reevaluate the sorted list

Шаг 3

compare 4 and 3
3.1 -> [] [3, 4, 6, 10]      // 4 and 3 needed to swap places
3.2 -> [3, 4] [6, 10]        // 3 < 4 -> no reevaluation needed

Шаг 4

compare 6 and 10
4.1 -> [3, 4] [6, 10]        // correct order already present
4.2 -> [3, 4, 6] [10]        // 6 > 4 -> no reevaluation needed

Шаг 5

check 10
5. 1 -> [3, 4, 6, 10]       // correct order already present

2. Алгоритм слияния

Сортировка слиянием использует технику «разделяй и властвуй». По сути, он делит список на равные части до тех пор, пока не останутся только атомарные значения, а затем объединяет их в отсортированном порядке. Его сложность в наихудшем случае составляет O (n log n).

Мы будем использовать тот же список чисел для объяснения: numbers = [6, 4, 3, 10]

Шаг 1

split list
1.1 -> [6, 4], [3, 10]           // split in equal parts
1.2 -> [6], [4], [3], [10]       // split in equal atomic parts

Шаг 2

merge and sort equal pairs
2.1 -> [4, 6], [3, 10]           // 6 and 4 needed to swap places

Шаг 3

repeat Step 2 until done
3.1 -> [3, 4, 6, 10]             // 3 needed reposition

3. Лучшее из обоих миров: алгоритм Timsort

Путь Python - это гибридный алгоритм сортировки, который основан на сортировке слиянием и вставкой. Для небольших прогонов (до минимального размера цикла 64) Timsort внутренне выбирает сортировку вставкой, в противном случае используется сортировка слиянием. Наихудший случай и средняя сложность - O (n log n), но производительность в лучшем случае - O (n).

Примеры использования алгоритма сортировки

Алгоритм сортировки реализован как list.sort () или sorted (list). Разница между этими двумя реализациями заключается в том, что list.sort () переупорядочивает исходный список, а s orted (list) возвращает новый список.

1. Параметры сортировки

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

  • ключ
  • задний ход
Syntax
sorted(list, key=…, reverse=…)
or
list.sort(key=…, reverse=…)

Ключ - это функция типа len, int, str.lower, которая служит ключом для сравнения. Обратный параметр определяет порядок. Значение по умолчанию - False, что означает сортировку в порядке возрастания. Используя reverse = True, мы переворачиваем список.

2. Основные примеры сортировки списка

Пусть следующие списки будут нашей базой:

scholarship = [«Udacity», «Bertelsmann», «Data», «Science», «Scholarship», «Program», «women», «who», «code»]
string_numbers = [« 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20]

Сортировка по умолчанию:

sorted(scholarship)
[‘Bertelsmann’, ‘Data’, ‘Program’, ‘Scholarship’, ‘Science’, ‘Udacity’, ‘code’, ‘who’, ‘women’]

→ стандартный порядок / по возрастанию, с учетом регистра, в алфавитном порядке

Определение настраиваемого ключа сортировки и порядка:

sorted(scholarship, reverse=True, key=len)
[‘Bertelsmann’, ‘Scholarship’, ‘Udacity’, ‘Science’, ‘Program’, ‘women’, ‘Data’, ‘code’, ‘who’]

→ обратная сортировка по длине

Для всех строк одинаковой длины применяется обратный алфавитный порядок: Стипендия ›Бертельсманн. В случае стандартного заказа результат будет заказан Бертельсманн ›Стипендия.

3. Особые случаи сортировки списка

Использование str.lower в качестве ключевого параметра:

sorted(scholarship, key=str.lower)
[‘Bertelsmann’, ‘code’, ‘Data’, ‘Program’, ‘Scholarship’, ‘Science’, ‘Udacity’, ‘who’, ‘women’]

→ порядок без учета регистра

Использование строковых представлений чисел:

sorted(string_numbers)
[‘1’, ‘10’, ‘2’, ‘20’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’]

→ стандартный алфавитный порядок, в котором за 1 следует 10

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

Есть несколько способов решить проблему:

  1. Изменение ключа на целочисленное сравнение:
sorted(string_numbers, key=int)
[‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘10’, ‘20’]

→ числовой порядок, тот же результат, что и числовая сортировка списка целых чисел

2. Изменение ключа на сравнение длины:

sorted(string_numbers, key=len)
[‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘10’, ‘20’]

→ сортировка по длине строки и стандартная сортировка применяется к той же длине, результат тот же, что и выше

Сравнение key = len имеет преимущество в производительности, поскольку нам не нужно выполнять приведение для сравнения. Этот метод также работает для смешанных списков, в то время как версия key = int может вызвать ошибку значения в случае неверно отформатированной строки или простой оплошности.

Заключение

Алгоритм Timsort, используемый в Python, использует преимущества алгоритмов вставки и слияния и, следовательно, является надежным инструментом для большинства случаев использования в Data Science. Кроме того, он предоставляет широкий спектр возможностей сортировки в виде ключей, которые можно изменить для каждой функции и даже для самоопределяемой функции. Это означает, что пользователь может полностью настроить результат алгоритма сортировки.

Дополнительный лакомый кусочек

В Python 3.2 алгоритм Timsort был обновлен, чтобы работать быстрее при вызове с помощью ключевой функции. Два массива ключей и значений теперь сортируются параллельно.

Ресурсы