Сортировка «к-тонических» последовательностей

Я надеюсь, что кто-то знает ссылку на это, поэтому мне не нужно читать литературу ...

Рассмотрим последовательность чисел . Думайте о последовательности как о n - 1 интервалах [ x 1 , x 2 ] , [ x 2 , x 3 ] , … , [ x n - 1 , x n ] . Ясно, что исходная последовательность является битовой, если любая точка на реальной линии наносит удар не более чем за 2 интервала. Мы будем называть последовательность , где точкой уколов в большинстве K промежутков времени, будучи к$x_1, \ldots, x_n$$n-1$$[x_1, x_2], [x_2, x_3], \ldots, [x_{n-1},x_n]$$k$$k$-idiotic . Визуально, если вы рисуете график последовательности (то есть соединяете точки по порядку), то вышеприведенное соответствует условию, что никакая горизонтальная линия не пересекает график более k раз.$p_i =(i,x_i)$$k$

Нетрудно (но не слишком легко) увидеть, что идиотические последовательности могут быть отсортированы за время O ( n log k ) , что является явно оптимальным.$k$$O( n \log k )$

Вопрос: этот результат должен быть известен. Вы знаете какой-нибудь подходящий реф?

Вот ссылка на алгоритм сортировки Левкопулоса-Петерссона, но несколько более старая, чем в ответе Андреаса:

Левкопулос, Христос; Петерссон, Ола (1989), «Heapsort - адаптированный для предварительно отсортированных файлов», WADS '89: Материалы семинара по алгоритмам и структурам данных, Конспект лекций в области компьютерных наук, 382, ​​Лондон, Великобритания: Springer-Verlag, стр. 499– 509, дои: 10.1007 / 3-540-51542-9_41.

$O(\sum\log k_i)$$k_i$$x_i$$k$$k_i$$k$$O(n\log k)$

Взгляни на

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017 .

Согласно мерам, одним из показателей беспорядка является Перемешанные монотонные подпоследовательности (SMS, стр. 7 внизу), что больше, чем вы просили.

Бумага

«Сортировка перемешанных монотонных последовательностей» Кристоса Левкопулоса и Олы Петерссон

http://www.springerlink.com/content/79551g82q1p856n1/

дает алгоритм с оптимальным временем выполнения по той мере, которую вы ищете.

Далее я посмотрел на сортировку сетей, чтобы сделать работу:

http://www.sciencedirect.com/science/article/pii/S074373150500136X .

Джоэл Сейферас