MergeSort + InsertionSort + хитрые эвристики = ? | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Разработчик чат-ботов и приложений для виртуальных ассистентов
-15%
PHP Developer. Professional Алгоритмы и структуры данных Scala-разработчик PHP Developer. Basic C# Developer. Professional
-23%
C# ASP.NET Core разработчик Python Developer. Basic Python Developer. Professional Cloud Solution Architecture Специализация iOS
-25%
HTML/CSS Android Developer. Professional React.js Developer Unity Game Developer. Professional NoSQL Java Developer. Professional Highload Architect C++ Developer. Basic Web-разработчик на Python Unity Game Developer. Basic Интенсив «Оптимизация в Java» Супер-практикум по использованию и настройке GIT Symfony Framework Java Developer. Basic Супер-интенсив "Tarantool"
Инфраструктура
MongoDB
-30%
Разработчик чат-ботов и приложений для виртуальных ассистентов
-15%
Administrator Linux. Professional
-26%
Network engineer Administrator Linux. Advanced Специализация Administrator Linux
-25%
Разработчик программных роботов (RPA) на базе UiPath и PIX
-27%
NoSQL Инфраструктурная платформа на основе Kubernetes Highload Architect Мониторинг и логирование: Zabbix, Prometheus, ELK Супер-практикум по использованию и настройке GIT Administrator Linux.Basic Экспресс-курс «IaC Ansible» Экспресс-курс по управлению миграциями (DBVC) Экспресс-курс "Версионирование и командная работа с помощью Git" Network engineer. Basic Основы Windows Server
Корпоративные курсы
Безопасность веб-приложений MongoDB
-30%
Разработчик чат-ботов и приложений для виртуальных ассистентов
-15%
Agile Project Manager Руководитель поддержки пользователей в IT
-10%
Промышленный ML на больших данных Cloud Solution Architecture Внедрение и работа в DevSecOps Spark Developer Reverse-Engineering IT-Recruiter Machine Learning. Professional Интенсив «Оптимизация в Java» Супер-практикум по использованию и настройке GIT Экcпресс-курс «ELK» Enterprise Architect Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes» Экспресс-курс «Введение в непрерывную поставку на базе Docker» Вебинар CERTIPORT
Специализации Курсы в разработке Подготовительные курсы Подписка
+7 499 938-92-02

MergeSort + InsertionSort + хитрые эвристики = ?

PythonDeep_16.05_Site.png

Сортировка массива — базовая операция. Каждый программист может написать несколько, а просто назвать алгоритмов сортировки — ещё больше.

«Естественная» необходимость и любовь к красивым решениям дала нам MergeSort, QuickSort, HeapSort и т.д. Самоирония, видимо, породила такие алгоритмы, как StupidSort, SleepSort и мой любимый — TwitterSort.

Что же использует Python? TimSort!

Автором является широко известный в узких кругах Тим Питерс, а сам алгоритм был с портирован в Java и Android.

Это гибридный адаптивный алгоритм, который совмещает под капотом MergeSort, InsertionSort и хитрые эвристики. Алгоритм ищет в сортируемой последовательности длины N уже отсортированные подпоследовательности (run). Если такая подпоследовательность меньше определённого порогового значения (min_run), то идущие за ней дальше элементы «досортировываются» с помощью InsertionSort, пока критерий не будет удовлетворен.

В итоге, исходная последовательность превращается в N/min_run отсортированных run’ов. Run’ы сливаются последовательно и попарно, память выделяется только на элементы, которые действительно нужно перемещать.

Допустим есть две подпоследовательности: A = [1, 2, 8, 9] и B = [4, 5,10, 21, 42]

В них 1, 2, 10, 21 и 42 уже находятся на своих финальных местах, что можно определить бинарным поиском B[0] в A и A[-1] в B. Память выделяется (и туда копируются) только на элементы из меньшей подпоследовательности, которые не стоят на своих финальных местах: 8 и 9. Дальше происходит слияние временной выделенного участка памяти и B с переносом элементов в A.

Galloping

И, конечно, нельзя не упомянуть про режим галопа. В нём во время слияния элементы перемещаются не попарным сравнением, а сразу целой «пачкой». Если сливаются temp = [8, 9] и B = [4, 5, 10, 21, 42] в A = [1, 2, , ], то поиском temp[0] в B можно определить, что элементы 4 и 5 нужно сразу перенести в A, после чего останется только дописать 8 и 9 в B.

И это ещё не все тонкости! Как выбирать min_run? Как искать элемент в массиве в режиме галопа? Для каких последовательностей сразу использовать InsertionSort без всей описанной «мишуры»? Есть в чём покопаться.

Спрашивайте в комментариях, если возникнут вопросы!

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться
🔥 Выгодные предложения
Подборка курсов, которые можно приобрести по выгодной цене только до конца июля!