Теория:
В Python есть встроенные возможности, которые быстро сортируют последовательность. Но задача сортировки настолько интересная и реализации её так разнообразны, что мы рассмотрим несколько разных алгоритмов сортировок.
Для начала отсортируем список с использованием встроенной функции sorted и метода sort(). Здесь важно понять различия.
Рис. \(1\). Реализация встроенной функции sorted и метода sort()
Обрати внимание!
• На комментарии в программе.
• Мы использовали функцию id() для того, чтобы посмотреть, какой номер имеет наша последовательность в памяти. Благодаря контролю за номером последовательности мы убедились, что метод перезаписывает её на то же место в памяти.
• Прими во внимание, что метод sort применим только для сортировки списков, а функция sorted работает со всеми изменяемыми объектами.
• Мы использовали функцию id() для того, чтобы посмотреть, какой номер имеет наша последовательность в памяти. Благодаря контролю за номером последовательности мы убедились, что метод перезаписывает её на то же место в памяти.
• Прими во внимание, что метод sort применим только для сортировки списков, а функция sorted работает со всеми изменяемыми объектами.
Встроенная сортировка выполняется по алгоритму Timsort, написанном в \(2002\) году Тимом Петерсом (мы уже упоминали о нём как об авторе \(PEP20\)). Этот алгоритм работает быстрее обычных сортировок, но основан на двух из них: сортировке вставками и сортировке слиянием.
Рассмотрим алгоритм сортировки пузырьком.
План решения задачи будет таким: перебираем в цикле for каждую пару соседних элементов: если они стоят в неверном порядке, то меняем их местами, если в верном — сдвигаемся на следующую пару. Этот цикл for заключаем в другой цикл for и повторяем всё сначала столько раз, сколько элементов в списке.
Рис. \(2\). Пример \(9\) — сортировка методом пузырька
Обрати внимание!
• Для наглядности список выводится на печать после каждой итерации по \(i\). При решении задачи это делать необязательно.
• На обмен значений элементов \(a[j]\) и \(a[j+1]: a[j]\), \(a[j+1]=a[j+1]\), \(a[j]\). В Python реализовано такое множественное присваивание.
• На то, как на первом же проходе по циклу \(i\) максимальный элемент \(45\) перемещается в конец списка. Проанализируй эту первую итерацию, переместив печать списка внутрь цикла по \(i\).
• На обмен значений элементов \(a[j]\) и \(a[j+1]: a[j]\), \(a[j+1]=a[j+1]\), \(a[j]\). В Python реализовано такое множественное присваивание.
• На то, как на первом же проходе по циклу \(i\) максимальный элемент \(45\) перемещается в конец списка. Проанализируй эту первую итерацию, переместив печать списка внутрь цикла по \(i\).
Рис. \(3\). Вывод
Обрати внимание!
• Уже на \(6\)-й итерации по внешнему циклу \(i\) достигается нужный результат, но итерации продолжаются, что говорит о неэффективности алгоритма.
Немного улучшаем скорость работы введением флага, отмечающего, если ни одного обмена не произошло, что список отсортирован и нужно выйти из цикла.
Рис. \(4\). Усовершенствованная программа
Сортировка выбором основана на выборе в последовательности элемента с минимальным значением и перестановке его в начало. В последовательности образуется отсортированная часть, в которой элементы стоят уже в правильном порядке, и неотсортированная, в которой на каждом проходе ищем элемент с минимальным значением. Когда неотсортированная часть исчерпывается полностью, перебор заканчивается.
Рис. \(5\). Пример \(10\) — сортировка выбором
Обрати внимание!
• В сравнении с предыдущим алгоритмом сортировке выбором потребовались все \(12\) итераций для того, чтобы отсортировать список, но сложность алгоритма не должна зависеть от конкретного списка, при другой комбинации элементов могут быть другие результаты.
Сортировка вставками также делит список на две части: отсортированную и неотсортированную. Из неотсортированной части берут элемент и находят ему место в отсортированной части, и так до тех пор, пока неотсортированная часть не исчерпается.
Рис. \(6\). Пример \(11\) — сортировка вставками
Сортировка подсчётом применяется в том случае, когда необходимо отсортировать список с повторяющимися значениями. Например, измерение температуры тела учеников одного класса. Значения температуры тела колеблются в маленьком диапазоне, в районе одного градуса, а количество измерений достаточно большое.
Суть сортировки заключается в том, что значения назначаются индексом списка, а их количество — значением элемента списка (в случае с температурой тела нужно учесть, что значение индекса может быть только целым числом). После подсчёта количества вхождений одного и того же числа в новый список выводятся только те элементы, у которых ненулевое значение, причём выводится их индекс столько раз, каково значение элемента с этим индексом.
Суть сортировки заключается в том, что значения назначаются индексом списка, а их количество — значением элемента списка (в случае с температурой тела нужно учесть, что значение индекса может быть только целым числом). После подсчёта количества вхождений одного и того же числа в новый список выводятся только те элементы, у которых ненулевое значение, причём выводится их индекс столько раз, каково значение элемента с этим индексом.
Рис. \(7\). Пример \(12\) — сортировка подсчётом
Наиболее эффективной сортировка подсчётом всё же является на узком диапазоне значений. Сравним скорость сортировки, воспользовавшись шаблоном из урока по циклам (см. пример \(5\)).
Рис. \(8\). Сравнение скорости сортировки
Рис. \(9\). Вывод \(2\)
Источники:
Рис. 1. Реализация встроенной функции sorted и метода sort(). © ЯКласс.
Рис. 2. Пример 9 — сортировка методом пузырька. © ЯКласс.
Рис. 3. Вывод. © ЯКласс.
Рис. 4. Усовершенствованная программа. © ЯКласс.
Рис. 5. Пример 10 — сортировка выбором. © ЯКласс.
Рис. 6. Пример 11 — сортировка вставками. © ЯКласс.
Рис. 7. Пример 12 — сортировка подсчётом. © ЯКласс.
Рис. 8. Сравнение скорости сортировки. © ЯКласс.
Рис. 9. Вывод 2. © ЯКласс.
Рис. 2. Пример 9 — сортировка методом пузырька. © ЯКласс.
Рис. 3. Вывод. © ЯКласс.
Рис. 4. Усовершенствованная программа. © ЯКласс.
Рис. 5. Пример 10 — сортировка выбором. © ЯКласс.
Рис. 6. Пример 11 — сортировка вставками. © ЯКласс.
Рис. 7. Пример 12 — сортировка подсчётом. © ЯКласс.
Рис. 8. Сравнение скорости сортировки. © ЯКласс.
Рис. 9. Вывод 2. © ЯКласс.