🚄 Сравнение 6 алгоритмов сортировки: пузырьком, выбором, кучей, вставками, слиянием и быстрая
В этой статье мы начнем изучение алгоритмов сортировки, разберем 6 методов сортировки и ознакомимся с оценкой их эффективности.
Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂
Все любят, когда данные отсортированы. Сортировка позволяет упорядочивать данные в нужной нам последовательности. В порядке возрастания и убывания. Представьте, что вы работаете в крупной компании и вам нужно отсортировать имена работников в зависимости от их зарплаты. Для этого используются алгоритмы сортировки.
Сегодня мы рассмотрим основные виды алгоритмов сортировки. Но сперва проясним, что из себя представляет сортировочный алгоритм.
Что такое алгоритм сортировки?
Сортировка больших объемов данных отнимает много сил и времени. Алгоритмы сортировки, как упоминалось ранее, позволяют облегчить выполнение этой задачи.
Алгоритмы сортировки позволяют упорядочить заданные списки и массивы данных с помощью операторов сравнения. Эти операторы применяются к элементам массива и определяют их последовательность в структуре данных.
К примеру, символы ниже идут в порядке возрастания согласно кодировке ASCII. В процессе сортировки идет сравнение элементов между собой. Чем выше значение символа в таблице ASCII, тем дальше от начала списка он будет расположен.
Какие существуют алгоритмы сортировки?
Существует множество различных алгоритмов. Сегодня мы рассмотрим 6 из них.
| Сортировка пузырьком | Один из простейших методов сортировки. Заключается в постепенном смещении элементов с большим значением в конец массива. Элементы последовательно сравниваются попарно, и если порядок в паре нарушен – меняются местами. |
| Сортировка выбором | Алгоритм ищет наименьший элемент в текущем списке и производит обмен его значения со значением первой неотсортированной позиции. То же самое происходит со вторым элементом с наименьшим значением. Цикл повторяется до тех пор, пока все элементы не займут нужную последовательность. |
| Быстрая сортировка | Считается одним из самых быстрых алгоритмов сортировки. Как и сортировка слиянием, работает по принципу «разделяй и властвуй». Временная сложность алгоритма может достигать O(n log n). |
| Сортировка кучей (Пирамидальная сортировка) | Алгоритм выстраивает данные в виде двоичного дерева (двоичной кучи). Существует два варианта расположения элементов – max-heap (значение родителя больше значений потомков) и min-heap (значение родителя меньше значений потомков). Наибольший / наименьший элемент (в зависимости от типа) располагается в корне дерева. Он меняется местами с последним элементом кучи и помещается в конец массива. Размер кучи уменьшается на 1, после чего она перестраивается. Цикл повторяется, пока размер кучи больше 1. |
| Сортировка вставками | Применяется для вставки элементов массива на «свое место». Сортировка вставками представляет собой простой метод сортировки и используется для раскладки колоды во время игры в бридж. |
| Сортировка слиянием | Следует принципу «разделяй и властвуй», согласно которому массив данных разделяется на равные части, которые сортируются по-отдельности. После они сливаются, в результате получается отсортированный массив. |
Сортировка, в результате которой относительная последовательность элементов не изменилась, называется устойчивой.
При неустойчивой сортировке элементы в массиве меняются местами.
Какие алгоритмы сортировки обеспечивают стабильность?
В таблице ниже представлена стабильность рассмотренных алгоритмов сортировки
| Алгоритм сортировки | Стабильность |
| Сортировка пузырьком | ✓ |
| Сортировка выбором | ✘ |
| Быстрая сортировка | ✘ |
| Сортировка кучей | ✘ |
| Сортировка вставками | ✓ |
| Сортировка слиянием | ✓ |
Можно ли оценить эффективность алгоритмов сортировки?
Да, это возможно.
Критериями оценки эффективности алгоритма сортировки является пространственная и временная сложность.
Пространственная сложность
Означает количество памяти, затраченной на выполнение алгоритма. Пространственная сложность включает вспомогательную память и память для хранения входных данных.
Вспомогательная память – дополнительное место, занимаемое алгоритмом помимо входных данных. Она учитывается при расчете пространственной сложности алгоритмов.
Временная сложность
Означает время, за которое алгоритм выполняет поставленную задачу с учетом входных данных. Может быть выражена с использованием следующих нотаций:
- Нотация «Омега» (Ω)
- Нотация «O» большое (O)
- Нотация «Тета» (Θ)
В таблице представлена оценка сложности алгоритмов, упомянутых ранее
| Алгоритм сортировки | Время работы в худшем случае | Время работы в среднем случае | Время работы в лучшем случае | Пространственная сложность |
| Сортировка пузырьком | n^2 | n^2 | n | 1 |
| Сортировка выбором | n^2 | n^2 | n^2 | 1 |
| Быстрая сортировка | n^2 | nlog n | nlog n | nlog n |
| Сортировка кучей | nlog n | nlog n | nlog n | 1 |
| Сортировка вставками | n^2 | n^2 | n | 1 |
| Сортировка слиянием | nlog n | nlog n | nlog n | n |
У каждого алгоритма сортировки своя временная и пространственная сложность. Использовать можно любой из представленных алгоритмов в зависимости от поставленных задач. Но по моему субъективному мнению лучшим алгоритмом является быстрая сортировка. Она позволяет выбрать опорный элемент и разделяет массив на 3 части: меньше, равно и больше опорного элемента.
Материалы по теме
- ☕ Разбираемся в алгоритме быстрой сортировки с помощью JavaScript
- 👨🎓️ Алгоритмы и структуры данных на C++ для новичков. Часть 1: Основы анализа алгоритмов
- ☕ Распространенные алгоритмы и структуры данных в JavaScript: полезные алгоритмы для веб-разработки