Доброго времени суток, читатели, зрители моего канала programmer's notes, любители языка Python. Не забывайте подписываться и писать свои
комментарии к моим статьям и видео.
Смешанная сортировка: слиянием и гномья на Python
Как я уже писал, сортировка слиянием хороша тем, что позволяет легко интегрировать в неё другие сортировки, добиваясь максимальной производительности.
Напомню как работает сортировка слиянием:
1. Разбиваем сортируемый массив на две части, например делением пополам.
2. Каждая из частей сортируется по одному из алгоритмов, например, опять же слиянием. Т.е. процесс деления повторяется.
3. Отсортированные части массива сливаются в один.
Суть в том, что можно делить массив пока одна из его частей ни станет равна единице. Тогда при выходе из рекурсии будет обратная сборка путем последовательного слияния. Но можно и поставить ограничение, некоторое значение - длина одной из половинок массива, пока мы будем продолжать деление. Как только условие не будет выполняться, то для сортировки будет вызвана некоторая функция, которая будет сортировать обе половинки по тому или иному алгоритму. А далее будет происходить выход из рекурсии и слияние отсортированных частей. При этом алгоритм добавочной сортировки может быть любым. Для примера я выбрал гномью сортировку, о которой я писал ранее. Пример представлен в программе ниже. Сочетанием размера границы, до которой будет делиться массив и выбора дополнительной сортировки можно попытаться нащупать наиболее производительный вариант.
Предыдущая статья о сортировке...
Следующая статья о сортировке...
Хорошего программирования. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.
