Народ, всем привет. Помните, мы тут недавно говорили про алгоритмы сортировки? Ну такие операции в программировании, необходимые для эффективного поиска, отображения и хранения данных. И если в прошлый раз мы говорили про самые простые и, скажем так, учебные алгоритмы, то сегодня у нас вторая часть и мы поговорим про более востребованные версии, которые чаще всего применяют на практике. Можно сказать, что это такие классические варианты сортировки:
- Quick Sort, она же быстрая сортировка
- Merge Sort, похожая на нее сортировка слиянием
- и Heap Sort или пирамидальная сортировка.
А теперь давайте про каждую подробнее. Кто не в курсе, о чем я тут вообще говорю, и кто не читал первую часть, ниже ссылочку приложу. Обязательно к прочтению начинающим программистам. И не просто к прочтению, а «на попробовать». Язык программирования при этом совершенно не важен.
Быстрая сортировка
Быстрая сортировка основана на принципе разделяй и властвуй. Идея состоит в выборе одного элемента массива в качестве опорного (pivot), после чего массив разделяется на две части:
- элементы меньше опорного,
- элементы больше опорного.
Затем каждая из частей рекурсивно сортируется. Рекурсивный, значит повторить само себя, по кругу. А теперь давайте подробнее, на кошках, так сказать. Все, что нам нужно, это выбрать опорный элемент (pivot). Часто берётся средний, последний или случайный элемент. А далее делим массив на:
- элементы меньше pivot (< pivot),
- элементы равные pivot (== pivot),
- элементы больше pivot (> pivot).
Далее повторяем подобное действия для левой и правой части. По итогу объединяем три части: левую + равные + правую. И так «внутрь» все глубже и глубже. Давайте на примере:
- берем массив arr = [9, 3, 7, 1, 8, 2, 5]
- выбираем pivot = 7
- меньше: [3, 1, 2, 5], равно: [7] и больше: [9, 8]
- рекурсивно сортируем [3, 1, 2, 5] и [9, 8], опять выбираем pivot внутри каждого из двух массивов и понеслась.
Как плюсы данный алгоритм очень быстрый на практике, и при этом использует малое количество памяти (in-place реализация возможна). Из минусов можно выделить только то, что он не сохраняет порядок равных элементов.
Если Вам нравятся наши статьи, и вы хотите отблагодарить автора (на развитие канала), нам будет очень приятно!
2. Сортировка слиянием (Merge Sort)
Сортировка слиянием тоже использует подход разделяй и властвуй. Алгоритм также разделяет массив на две половины и рекурсивно сортирует каждую из половин, пока в каждом подмассиве не останется 1 элемент, а затем объединяет их в правильном порядке, используя вспомогательную функцию слияния. Вопрос, что за функция слияния? Главная ее идея, это сравнивать первые элементы двух массивов и поочерёдно собирать результат. Давайте на примере:
- берем массив [4 2 5 1].
- делим пополам [4 2] и [5 1]
- делим пополам первый массив [4] и [2], и раз в каждом по одному элементу, то сортируем и склеиваем в один [2 4].
- делим пополам второй массив [5] и [1], и раз в каждом по одному элементу — сортируем и склеиваем в один [1 5].
- теперь у нас два новых массива [2 4] и [1 5], уже отсортированных, и нам нужно их склеить в один. - сравниваем первые элементы: 1 и 2, единица меньше двух, значит, в итоговый массив записываем 1, и у нас остаются два массива: [2 4] и [5].
- cравниваем первые элементы 2 и 5, двойка меньше пяти, значит, в итоговый массив записываем 2, и у нас остаются два массива: [4] и [5].
- точно так же сравниваем первые элементы до тех пор, пока в обоих массивах не исчезнут все элементы.
Как только это произойдёт — массив отсортирован. Из плюсов можно выделить надёжность и «нормальную» производительность. Скажем так, это устойчивая сортировка, когда никогда не подводит. Другой вопрос, что он требует больше памяти, чем быстрая сортировка и делает это медленнее.
3. Пирамидальная сортировка (Heap Sort)
Сортировка пирамидой основана на использовании кучи (как бы странно это не звучало), специальной структуры данных, представляющей собой бинарное дерево, где каждый родитель больше (или меньше) своих потомков. Ничего не понятно? По свей сути она похожа на сортировку выбором, где мы сначала ищем максимальный элемент и просто помещаем его в конец. Далее мы повторяем ту же операцию для оставшихся элементов. Давайте на примере:
Во-первых, разберемся со словом «куча». Это бинарное дерево. Легче стало? На самом деле это дерево из обычного несортированного массива. Начиная с нулевого элемента последовательно заполняем уровни дерева слева направо. Получается, что корень дерева — это нулевой элемент массива, его потомки — это первый и второй элемент и, соответственно, у левой ветки потомки – это 3 и 4 элемент, а у правого – 5 и 6 и так далее.
Важно, я говорю про нумерацию элементов массива, а не о их значениях.
Далее нам нужно преобразовать это дерево таким образом, чтобы в корне дерева находился максимальный элемент, а значение в каждом узле было больше, чем значения в его потомках. Для этого мы смотрим на предпоследний уровень дерева, и для каждого узла проверяем, выполняется условие: каждый потомок должен быть меньше своего родителя. Если нет, то находим максимальный элемент среди потомков и меняем его местом с родителем.
Так проходимся по каждому уровню дерева снизу вверх и в результате мы получаем сортирующее дерево, в корне которого находится максимальное число.
Ну хорошо, на дереве еще более-менее понятно. Но у нас вроде как массив, строчка. Но массив это и есть дерево. Все перестановки, которые мы якобы делаем в дереве, — это перестановки элементов в массиве. По сути, мы поменяли местами 1 <—> 4 элемент массива и 2 <—> 6. И если говорить еще проще, то вот у нас есть массив: [8, 3, 2, 7, 9, 1, 4].
И нам нужно поставить на первое место самый большой элемент. А для этого берем оставшуюся часть, и применяем к ней сортировку, делим пополам, рекурсивно делим, до одного элемента, как в примерах выше. И начинаем сравнивать их, «поднимая» высокие элементы все выше. Просто делятся они по номерам элемента массива, составляя дерево. После чего первый элемент меняем с последним (уводим самое большое значение в конец) и еще раз применяем тот же алгоритм.
Кажется сложным, но по факту вес довольно просто, надо только один раз попробовать. По факту это всегда гарантированное время выполнения алгоритма и не требует дополнительной памяти. Но стоит учитывать, что это неустойчивая сортировка, на почти отсортированных массивах этот алгоритм будет работать так же долго, как и на случайных. И как итог он менее эффективен на небольших массивах по сравнению с той же быстрой сортировкой.
Кстати, у нас есть и другой канал, FIT FOR FUN, про фитнес, бодибилдинг, правильное питание, похудение и ЗОЖ в целом. Кому интересно, ждем вас в гости!