Какой алгоритм сортировки быстрее?
Существует много видов сортировки: пузырьковая (bubble), выборкой (Selection), вставками (Insertion), куча (Heap), слиянием (Merge), быстрая (Quick). В этой статье мы постараемся определить, какой из этих алгоритмов быстрее.
Для решения поставленной задачи сгенерируем массив в Python, состоящий из пяти тысяч чисел от 0 до 1000. Потом определим время, нужное нам для завершения каждого алгоритма. И повторим каждый метод десять раз, дабы можно было точнее определить производительность.
Что получили?
Самым медленным алгоритмом оказалась пузырьковая сортировка. Возможно, она будет полезна при ознакомлении с темой алгоритмов сортировки, однако всё же Bubble Sort — не самый лучший вариант для практического применения.
А вот быстрая сортировка неплохо оправдала своё название, показав скорость, которая почти в 2 раза выше, чем при сортировке слиянием. При этом нам не потребуется дополнительное место для результирующего массива.
Идём дальше. Сортировка вставками при своей работе выполняет меньше сравнений, если сравнивать с сортировкой выборкой. Таким образом, в реальности Insertion Sort должна быть более производительна. Однако в нашем случае она сработала чуть-чуть медленней. Всё дело в том, что сортировка вставками выполняет намного больше обменов элементами. А когда эти обмены занимают гораздо больше времени, чем сравнение самих элементов, полученный в нашем эксперименте результат является закономерным.
Напоследок, добавим, что лучше понять вышеупомянутые алгоритмы поможет их визуализация. При этом масштаб сравнения и число перестановок, которые выполняет алгоритм совместно со средой выполнения кода, как раз таки и будут главными факторами, определяющими производительность. Что касается реальных приложений на Python, то мы рекомендуем применять встроенные функции сортировки, так как они реализованы с учётом удобства разработчика.
