6 алгоритмов сортировки в гифках

6 алгоритмов сортировки в гифках

Сортировка – важный аспект программирования. Отсортированные данные позволяют быстрее и эффективнее работать с данными.

Для описания эффективности алгоритма мы использовали два основных критерия: расход памяти и асимптотическую временную сложность (О-нотация).

С асимптотической сложностью можете ознакомиться в другой нашей статье.

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), давайте разберем, что это за структура данных. По сути, куча – бинарное дерево, которое удовлетворяет дополнительным условиям: