Несколько дней новогоднего волшебства:
Успейте начать обучение в 2018-ом году со скидкой до 30%!
Выбрать курс

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 без всей описанной «мишуры»? Есть в чём покопаться.

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

Автор
0 комментариев
Для комментирования необходимо авторизоваться