Sortieren von "k-tonischen" Sequenzen

12

Ich hoffe, dass jemand einen Hinweis darauf kennt, sodass ich die Literatur nicht lesen muss ...

Betrachten Sie eine Folge von Zahlen . Stellen Sie sich die Sequenz als n - 1 Intervalle [ x 1 , x 2 ] , [ x 2 , x 3 ] , , [ x n - 1 , x n ] vor . Es ist klar, dass die ursprüngliche Sequenz bitonisch ist, wenn ein Punkt auf der realen Linie höchstens 2 Intervalle sticht. Wir werden uns auf eine Sequenz beziehen, in der ein Punkt in den meisten k Intervallen als k stichtx1,,xnn1[x1,x2],[x2,x3],,[xn1,xn]kk-idiotisch . Wenn Sie den Graphen der Sequenz zeichnen (dh die Punkte Reihe nach verbinden), entspricht das Obige der Bedingung, dass keine horizontale Linie den Graphen mehr als k- mal schneidet .pi=(i,xi)k

Es ist nicht zu schwer (aber auch nicht zu leicht) zu erkennen, dass -idiotische Sequenzen in der Zeit O ( n log k ) sortiert werden können , was eindeutig optimal ist.kO(nlogk)

Frage: Dieses Ergebnis sollte bekannt sein. Kennst du einen passenden Hinweis?

Sariel Har-Peled
quelle

Antworten:

10

Hier ist eine Referenz zum Levcopoulos-Petersson-Sortieralgorithmus, aber eine andere, die etwas älter ist als die in Andreas 'Antwort:

Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Angepasst für vorsortierte Dateien", WADS '89: Proceedings des Workshops zu Algorithmen und Datenstrukturen, Lecture Notes in Computer Science, 382, ​​London, UK: Springer-Verlag, S. 499– 509, doi: 10.1007 / 3-540-51542-9_41.

Es gibt eine Beschreibung des Algorithmus in http://en.wikipedia.org/wiki/Cartesian_tree#Application_in_sorting, aus der die O (n log k) -Grenze leicht ersichtlich ist. Genauer gesagt ist die Zeit für den Algorithmus wobei k i die Anzahl der Intervalle ist, die das Eingabeelement x i enthalten . In einer k -idiotischen Sequenz ist jedes k i einheitlich durch k begrenzt, so dass die Gesamtzeit nur O ( n log k ) ist .Ö(Logkich)kichxichkkichkÖ(nLogk)

David Eppstein
quelle
2
Cool. Wikipedia Ref gewinnt über geschlossene Firewall ...
Sariel Har-Peled
1
@ SarielHar-Peled: da stimme ich zu.
Andreas Björklund
6

Schauen Sie sich an

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

Ein Maß für die Störung gemäß dem Papier sind die gemischten monotonen Folgen (SMS, Seite 7 unten), die mehr sind, als Sie gefordert haben.

Das Papier

"Sorting shuffled monotone sequence" von Christos Levcopoulos und Ola Petersson

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

Gibt einen Algorithmus mit der optimalen Laufzeit für das Maß, das Sie suchen.

Andreas Björklund
quelle