Menyortir urutan "k-tonik"

Saya harap seseorang tahu referensi untuk ini, jadi saya tidak perlu membaca literatur ...

Pertimbangkan urutan angka . Pikirkan urutan sebagai interval . Jelas, urutan asli adalah bitonic jika ada titik pada garis nyata menusuk paling banyak 2 interval. Kita akan merujuk pada urutan di mana titik menusuk paling banyak interval sebagai -idiotik . Secara visual, jika Anda menggambar grafik urutan (yaitu, hubungkan titik secara berurutan), maka yang di atas sesuai dengan kondisi bahwa tidak ada garis horizontal yang memotong grafik lebih dari kali.$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$

Tidak terlalu sulit (tetapi juga tidak terlalu mudah) untuk melihat bahwa urutan -idiotik dapat diurutkan dalam waktu O ( n log k ) , yang jelas-jelas optimal.$k$$O( n \log k )$

Pertanyaan: Hasil ini harus diketahui. Apakah Anda tahu referensi yang sesuai?

Berikut ini adalah referensi algoritma pengurutan Levcopoulos-Petersson, tetapi yang berbeda agak lebih tua dari yang ada di jawaban Andreas:

Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Diadaptasi untuk File yang Didahului", WADS '89: Prosiding Workshop tentang Algoritma dan Struktur Data, Catatan Kuliah dalam Ilmu Komputer, 382, ​​London, Inggris: Springer-Verlag, hlm. 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)$

Melihat

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

Salah satu ukuran gangguan menurut makalah ini adalah Shuffled Monotone Sub berikutnyaences (SMS, halaman 7 bawah) yang lebih dari yang Anda minta.

Kertas

"Mengurutkan urutan monoton yang diacak" oleh Christos Levcopoulos dan Ola Petersson

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

memberikan algoritma dengan wrime runtime optimal yang mengukur apa yang Anda cari.

Berikut ini saya melihat penyortiran jaringan untuk melakukan pekerjaan:

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

Joel Seiferas