Sortowanie sekwencji „tonicznych”

Mam nadzieję, że ktoś wie o tym, więc nie muszę czytać literatury ...

Rozważ ciąg liczb . Pomyśl o sekwencji jako interwałach . Oczywiście, oryginalna sekwencja jest bitoniczna, jeśli jakikolwiek punkt na prawdziwej linii dźgnie co najwyżej 2 interwały. Będziemy odnosić się do sekwencji, w której punkt dźgnie w większości przedziałów, jako antybiotyk . Wizualnie, jeśli narysujesz wykres sekwencji (tj. punkty w kolejności), to powyższe odpowiada warunkowi, że żadna pozioma linia nie przecina wykresu więcej niż razy.$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$

Nie jest to zbyt trudne (ale nie zbyt łatwe, albo), aby zobaczyć, że -idiotic sekwencje mogą być sortowane w O ( n log k ) czas, który jest wyraźnie optymalne.$k$$O( n \log k )$

Pytanie: Ten wynik powinien być znany. Czy znasz jakieś odpowiednie referencje?

Oto odwołanie do algorytmu sortowania Levcopoulosa-Peterssona, ale inny nieco nieco starszy niż ten w odpowiedzi Andreasa:

Levcopoulos, Christos; Petersson, Ola (1989), „Heapsort - Adapted for Presorted Files”, WADS '89: Materiały z warsztatów nt. Algorytmów i struktur danych, Uwagi do wykładów z informatyki, 382, ​​Londyn, Wielka Brytania: Springer-Verlag, s. 499– 509, doi: 10.1007 / 3-540-51542-9_41.

Opis algorytmu znajduje się na stronie http://en.wikipedia.org/wiki/Cartesian_tree#Application_in_sorting, z którego łatwo można zobaczyć granicę O (n log k). Dokładniej czas dla algorytmu wynosi gdzie k i jest liczbą przedziałów zawierających element wejściowy x i . W k -idiotic sekwencji, każdy k i równomiernie ograniczony k więc łączny czas tylko O ( n log K ) .$O(\sum\log k_i)$$k_i$$x_i$$k$$k_i$$k$$O(n\log k)$

Spojrzeć na

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

Jedną z miar nieporządku według artykułu są Potasowane monotoniczne podsekwencje (SMS, strona 7 u dołu), które są czymś więcej niż prosiłeś.

Papier

„Sortowanie potasowanych sekwencji monotonicznych” Christos Levcopoulos i Ola Petersson

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

daje algorytmowi optymalne środowisko wykonawcze, które mierzy to, czego szukasz.

Poniżej spojrzałem na sortowanie sieci, aby wykonać zadanie:

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

Joel Seiferas