0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: python, mergesort, quicksort, heapsort, stupidsort, sleepsort, twittersort, timsort, сортировка массива, алгоритмы сортировки, run, min_run, n/min_run, galloping, режим галопа</p>
1
<p>Теги: python, mergesort, quicksort, heapsort, stupidsort, sleepsort, twittersort, timsort, сортировка массива, алгоритмы сортировки, run, min_run, n/min_run, galloping, режим галопа</p>
2
<p>Сортировка массива - базовая операция. Каждый программист может написать несколько, а просто назвать алгоритмов сортировки - ещё больше.</p>
2
<p>Сортировка массива - базовая операция. Каждый программист может написать несколько, а просто назвать алгоритмов сортировки - ещё больше.</p>
3
<p>"Естественная" необходимость и любовь к красивым решениям дала нам MergeSort, QuickSort, HeapSort и т.д. Самоирония, видимо, породила такие алгоритмы, как StupidSort, SleepSort и мой любимый - TwitterSort.</p>
3
<p>"Естественная" необходимость и любовь к красивым решениям дала нам MergeSort, QuickSort, HeapSort и т.д. Самоирония, видимо, породила такие алгоритмы, как StupidSort, SleepSort и мой любимый - TwitterSort.</p>
4
<h2>Что же использует Python? TimSort!</h2>
4
<h2>Что же использует Python? TimSort!</h2>
5
<p>Автором является широко известный в узких кругах Тим Питерс, а сам алгоритм был с портирован в Java и Android.</p>
5
<p>Автором является широко известный в узких кругах Тим Питерс, а сам алгоритм был с портирован в Java и Android.</p>
6
<p>Это гибридный адаптивный алгоритм, который совмещает под капотом MergeSort, InsertionSort и хитрые эвристики. Алгоритм ищет в сортируемой последовательности длины N уже отсортированные подпоследовательности (run). Если такая подпоследовательность меньше определённого порогового значения (min_run), то идущие за ней дальше элементы "досортировываются" с помощью InsertionSort, пока критерий не будет удовлетворен.</p>
6
<p>Это гибридный адаптивный алгоритм, который совмещает под капотом MergeSort, InsertionSort и хитрые эвристики. Алгоритм ищет в сортируемой последовательности длины N уже отсортированные подпоследовательности (run). Если такая подпоследовательность меньше определённого порогового значения (min_run), то идущие за ней дальше элементы "досортировываются" с помощью InsertionSort, пока критерий не будет удовлетворен.</p>
7
<p>В итоге, исходная последовательность превращается в<strong>N/min_run</strong>отсортированных run’ов. Run’ы сливаются последовательно и попарно, память выделяется только на элементы, которые действительно нужно перемещать.</p>
7
<p>В итоге, исходная последовательность превращается в<strong>N/min_run</strong>отсортированных run’ов. Run’ы сливаются последовательно и попарно, память выделяется только на элементы, которые действительно нужно перемещать.</p>
8
<p>Допустим есть две подпоследовательности: A = [1, 2, 8, 9] и B = [4, 5,10, 21, 42]</p>
8
<p>Допустим есть две подпоследовательности: A = [1, 2, 8, 9] и B = [4, 5,10, 21, 42]</p>
9
<p>В них 1, 2, 10, 21 и 42 уже находятся на своих финальных местах, что можно определить бинарным поиском<strong>B[0] в A</strong>и<strong>A[-1] в B</strong>. Память выделяется (и туда копируются) только на элементы из меньшей подпоследовательности, которые не стоят на своих финальных местах: 8 и 9. Дальше происходит слияние временной выделенного участка памяти и B с переносом элементов в A.</p>
9
<p>В них 1, 2, 10, 21 и 42 уже находятся на своих финальных местах, что можно определить бинарным поиском<strong>B[0] в A</strong>и<strong>A[-1] в B</strong>. Память выделяется (и туда копируются) только на элементы из меньшей подпоследовательности, которые не стоят на своих финальных местах: 8 и 9. Дальше происходит слияние временной выделенного участка памяти и B с переносом элементов в A.</p>
10
<h2>Galloping</h2>
10
<h2>Galloping</h2>
11
<p>И, конечно, нельзя не упомянуть про режим галопа. В нём во время слияния элементы перемещаются не попарным сравнением, а сразу целой "пачкой". Если сливаются<strong>temp = [8, 9]</strong>и<strong>B = [4, 5, 10, 21, 42] в A = [1, 2,<em>,</em>]</strong>, то поиском<strong>temp[0] в B</strong>можно определить, что элементы 4 и 5 нужно сразу перенести в A, после чего останется только дописать 8 и 9 в B.</p>
11
<p>И, конечно, нельзя не упомянуть про режим галопа. В нём во время слияния элементы перемещаются не попарным сравнением, а сразу целой "пачкой". Если сливаются<strong>temp = [8, 9]</strong>и<strong>B = [4, 5, 10, 21, 42] в A = [1, 2,<em>,</em>]</strong>, то поиском<strong>temp[0] в B</strong>можно определить, что элементы 4 и 5 нужно сразу перенести в A, после чего останется только дописать 8 и 9 в B.</p>
12
<p>И это ещё не все тонкости! Как выбирать min_run? Как искать элемент в массиве в режиме галопа? Для каких последовательностей сразу использовать InsertionSort без всей описанной "мишуры"? Есть в чём покопаться.</p>
12
<p>И это ещё не все тонкости! Как выбирать min_run? Как искать элемент в массиве в режиме галопа? Для каких последовательностей сразу использовать InsertionSort без всей описанной "мишуры"? Есть в чём покопаться.</p>
13
<p><em>Спрашивайте в комментариях, если возникнут вопросы!</em></p>
13
<p><em>Спрашивайте в комментариях, если возникнут вопросы!</em></p>
14
14