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

Курсы

Программирование
iOS Developer. Basic
-23%
Python Developer. Professional
-13%
Разработчик на Spring Framework
-23%
Golang Developer. Professional
-17%
Python Developer. Basic
-16%
iOS Developer. Professional
-13%
Node.js Developer
-15%
Unity Game Developer. Professional
-11%
React.js Developer
-12%
Android Developer. Professional
-7%
Software Architect
-12%
C++ Developer. Professional
-8%
Разработчик C#
-8%
Backend-разработчик на PHP
-8%
Архитектура и шаблоны проектирования
-12%
Программист С Базы данных Framework Laravel PostgreSQL Reverse-Engineering. Professional CI/CD Agile Project Manager Нереляционные базы данных Супер - интенсив по паттернам проектирования Супер-практикум по использованию и настройке GIT IoT-разработчик Advanced Fullstack JavaScript developer Супер-интенсив "Azure для разработчиков"
Инфраструктура
Мониторинг и логирование: Zabbix, Prometheus, ELK
-17%
DevOps практики и инструменты
-18%
Архитектор сетей
-21%
Инфраструктурная платформа на основе Kubernetes
-22%
Супер-интенсив «IaC Ansible»
-16%
Супер-интенсив по управлению миграциями (DBVC)
-16%
Administrator Linux. Professional
-5%
Administrator Linux.Basic
-10%
Супер-интенсив «ELK»
-10%
Базы данных Сетевой инженер AWS для разработчиков Cloud Solution Architecture Разработчик голосовых ассистентов и чат-ботов Внедрение и работа в DevSecOps Супер-практикум по работе с протоколом BGP Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Супер-интенсив «СУБД в высоконагруженных системах»
Специализации Курсы в разработке Подготовительные курсы
+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 комментариев
Для комментирования необходимо авторизоваться