Сортировка – важный аспект программирования. Отсортированные данные позволяют быстрее и эффективнее работать с данными.
Для описания эффективности алгоритма мы использовали два основных критерия: расход памяти и асимптотическую временную сложность (О-нотация).
С асимптотической сложностью можете ознакомиться в другой нашей статье.
Bubble Sort
Сортировка пузырьком считается учебной и самой легкой в понимании. В её основе лежит поочередное сравнение соседних элементов. Если они стоят в неверном порядке, их меняют местами. Так, наибольший элемент «всплывает» наверх с каждым проходом.
Это самый медленный из алгоритмов с квадратичной скоростью O(n 2 ). Однако он самый легкий в реализации и не использует много памяти.
Insertion Sort
Сортировка вставками – алгоритм квадратичной сложности и тоже не злоупотребляет дополнительной памятью. Тем не менее, его средняя скорость выполнения примерно вдвое выше, чем у пузырьков.
Принцип прост. Все элементы просматриваются по очереди. Просмотренные элементы считаются отсортированными и каждый новый ставится на нужное место в ранее упорядоченной последовательности.
Shell Sort
Сортировка Шелла – это та же сортировка вставками, но с предварительными грубыми проходами. Принцип похожий, но сравнение идет не соседних элементов, а нескольких в определенном интервале. Это позволяет оптимизировать перебор.
Quick Sort
Быстрая сортировка или сортировка Хоара является одной из самых эффективных: на случайных данных достигает производительности O(n log(n)). Однако алгоритм является рекурсивным, поэтому использует много дополнительной памяти.
Принцип интересней прошлых примеров. Сначала мы определяем опорную точку в последовательности. Теоретически это может быть любой элемент, на практике выбирают либо медианный, либо средний. Потом перераспределяем так, чтобы все элементы меньше опорного были слева, а больше – справа. Применяем алгоритм рекурсивно к обеим половинам, пока в них больше одного элемента.
Merge Sort
Сортировка слиянием похожа по принципу на быструю и тоже является рекурсивной. Скорость алгоритма O(n log(n)) и требует дополнительной памяти в размере исходной последовательности.
На мой взгляд, слияние проще для понимания, чем сортировка Хоара. Сначала мы разбиваем исходную последовательность пополам, и сортируем каждую половину рекурсивно до тех пор, пока в каждой половине не останется по одному элементу. Затем осуществляем их слияние.
HeapSort
Пирамидальная сортировка или сортировка кучей тоже имеет асимптотическую сложность O(n log(n)), но на практике оказывается медленнее предыдущих двух и применяется достаточно редко, хоть и не требует дополнительного выделения памяти.
Алгоритм интересен своим подходом. Принцип похож на сортировку вставками. Только мы не ищем место элемента в массиве, а просеиваем его в двоичную кучу (Heap).
Чтобы понять, почему это ускоряет процесс с n до log(n), давайте разберем, что это за структура данных. По сути, куча – бинарное дерево, которое удовлетворяет дополнительным условиям: