Сортировочный номер

В математике и информатике числа сортировки - это последовательность чисел, введенная в 1950 году Хьюго Штайнхаусом для анализа алгоритмов сортировки сравнения . Эти цифры дают наихудшее число сравнений , используемых как бинарной вставки сортировки и сортировки слиянием . Однако есть другие алгоритмы, которые используют меньше сравнений.

Формула и примеры [ править ]

Номер сортировки определяется формулой ^[1]${\ displaystyle n}$

${\ Displaystyle п \, S (п) -2 ^ {S (п)} + 1}$

куда

${\ Displaystyle S (n) = \ lfloor 1+ \ log _ {2} n \ rfloor.}$

Последовательность чисел, заданная этой формулой (начиная с ), равна${\ Displaystyle п = 1}$

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... (последовательность A001855 в OEIS ).

Такую же последовательность чисел можно получить из рекуррентного соотношения ^[2]

${\ Displaystyle А (п) = А {\ bigl (} \ lfloor n / 2 \ rfloor {\ bigr)} + ​​A {\ bigl (} \ lceil n / 2 \ rceil {\ bigr)} + ​​n-1. }$

Это пример 2-регулярной последовательности . ^[2]

Асимптотически значение th сортировочного числа колеблется между и в зависимости от соотношения между и ближайшей степенью двойки . ^[2]${\ displaystyle n}$${\ displaystyle n \ log _ {2} nn}$${\ displaystyle n \ log _ {2} n-0.915n}$${\ displaystyle n}$

Приложение к сортировке [ править ]

В 1950 году Хьюго Штайнхаус заметил, что эти числа подсчитывают количество сравнений, используемых при сортировке двоичной вставкой , и предположил (ошибочно), что они дают минимальное количество сравнений, необходимое для сортировки элементов с использованием любой сортировки сравнения . Гипотеза была опровергнута в 1959 г. Л. Р. Фордом-младшим и Селмером М. Джонсоном , которые нашли другой алгоритм сортировки, сортировку слиянием-вставкой Форда – Джонсона , с использованием меньшего количества сравнений. ^[1]${\ displaystyle n}$

Та же последовательность чисел сортировки также дает наихудшее количество сравнений, используемых сортировкой слиянием для сортировки элементов. ^[2]${\ displaystyle n}$

Другие приложения [ править ]

Сортировочные числа (сдвинутые на одну позицию) также дают размеры кратчайших возможных суперштейнеров для многоуровневых перестановок . ^[3]

Ссылки [ править ]