Tri des séquences «k-toniques»

J'espère que quelqu'un connaît une référence à cela, donc je n'ai pas à lire la littérature ...

Considérons une séquence de nombres . Considérez la séquence comme intervalles . De toute évidence, la séquence d'origine est bitonique si un point quelconque de la ligne réelle est poignardé à 2 intervalles au maximum. Nous ferons référence à une séquence où un point poignarde à la plupart des intervalles comme étant -idiotique . Visuellement, si vous tracez le graphique de la séquence (c.-à-d. Connectez les points dans l'ordre), alors ce qui précède correspond à la condition qu'aucune ligne horizontale ne coupe le graphique plus de fois.$x_1, \ldots, x_n$$n-1$$[x_1, x_2], [x_2, x_3], \ldots, [x_{n-1},x_n]$$k$$k$$p_i =(i,x_i)$$k$

Il n'est pas trop difficile (mais pas trop facile non plus) de voir que les séquences idiotiques peuvent être triées en temps , ce qui est clairement optimal.$k$$O( n \log k )$

Question: Ce résultat doit être connu. Connaissez-vous une référence appropriée?

Voici une référence d'algorithme de tri Levcopoulos-Petersson, mais différente un peu plus ancienne que celle dans la réponse d'Andreas:

Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adapted for Presorted Files", WADS '89: Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 382, ​​Londres, Royaume-Uni: Springer-Verlag, pp. 499– 509, doi: 10.1007 / 3-540-51542-9_41.

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

Jeter un coup d'œil à

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

Une mesure du désordre selon l'article est les conséquences monotones mélangées (SMS, page 7 en bas), ce qui est plus que ce que vous aviez demandé.

Le papier

"Tri des séquences monotones mélangées" par Christos Levcopoulos et Ola Petersson

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

donne un algorithme avec le runtime optimal par rapport à cette mesure qui est ce que vous recherchez.

Dans ce qui suit, j'ai examiné les réseaux de tri pour faire le travail:

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

Joel Seiferas