Ordenar secuencias de "k-tonic"

12

Espero que alguien sepa algo sobre esto, así que no tengo que leer la literatura ...

Considere una secuencia de números . Piense en la secuencia como n - 1 intervalos [ x 1 , x 2 ] , [ x 2 , x 3 ] , , [ x n - 1 , x n ] . Claramente, la secuencia original es bitónica si algún punto en la línea real apuñala en la mayoría de los 2 intervalos. Nos referiremos a una secuencia donde un punto apuñala en la mayoría de los intervalos k como kx1,,xnn1[x1,x2],[x2,x3],,[xn1,xn]kk-idiótico . Visualmente, si dibuja la gráfica de la secuencia (es decir, conecta los puntos en orden), lo anterior corresponde a la condición de que ninguna línea horizontal intersecte la gráfica más de k veces.pi=(i,xi)k

No es demasiado difícil (pero tampoco demasiado fácil) ver que las secuencias -idióticas se pueden clasificar en el tiempo O ( n log k ) , que es claramente óptimo.kO(nlogk)

Pregunta: Este resultado debe ser conocido. ¿Conoces alguna referencia apropiada?

Sariel Har-Peled
fuente

Respuestas:

10

Aquí hay una referencia de algoritmo de clasificación de Levcopoulos-Petersson, pero una diferente algo más antigua que la de la respuesta de Andreas:

Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adaptado para archivos preseleccionados", WADS '89: Actas del taller sobre algoritmos y estructuras de datos, Lecture Notes in Computer Science, 382, ​​Londres, Reino Unido: Springer-Verlag, pp. 499– 509, doi: 10.1007 / 3-540-51542-9_41.

O(logki)kixikkikO(nlogk)

David Eppstein
fuente
2
Frio. El árbitro de Wikipedia gana sobre el firewall cerrado ...
Sariel Har-Peled
1
@ SarielHar-Peled: Estoy de acuerdo.
Andreas Björklund el