Menyortir menggunakan tumpukan read-only

Pertimbangkan pengaturan berikut:

• kami diberi tumpukan $s$ yang berisi item.$n$
• kita dapat menggunakan jumlah tumpukan ekstra konstan .$O(1)$
• kita dapat menerapkan operasi berikut pada tumpukan ini:
  1. periksa apakah tumpukan kosong,
  2. membandingkan item teratas dari dua tumpukan,
  3. hapus item teratas dalam tumpukan,
  4. cetak item teratas dalam tumpukan,
  5. salin item teratas dari tumpukan ke tumpukan lain,
  6. salin konten dari satu tumpukan ke tumpukan lain.

Perhatikan bahwa ini adalah satu-satunya operasi yang diizinkan. Kami tidak dapat menukar item dan kami tidak diizinkan untuk mendorong item apa pun ke tumpukan mana pun dengan pengecualian menyalin item teratas ke dalam tumpukan (setelah itu konten tumpukan target sebelumnya dibuang dan hanya akan berisi item yang disalin) .

Berikut ini adalah algoritma untuk mengurutkan tumpukan dengan perbandingan $O(n^2)$ :

last := empty
for i from 1 to n
  min := empty
  w := s
  while w is not empty
    if w.top > last and w.top < min
      min := w.top
    delete w.top
  print min
  last := min

Bisakah kita berbuat lebih baik?

Apakah ada program yang mencetak daftar item yang diurutkan di tumpukan menggunakan hanya perbandingan ?$O(n\log n)$

Saya pikir saya sekarang dapat menunjukkan batas bawah nontrivial. Idenya adalah untuk mengimplementasikan program semacam itu dengan keluarga program percabangan perbandingan. Asumsi `read-only 'berarti bahwa keluarga kami dari program percabangan menggunakan sedikit, yaitu , ruang. Kemudian kita menerapkan batas bawah S T = Ω ( n 2 ) dibuktikan oleh Borodin et al. di "Pengorbanan Waktu-Ruang untuk Mengurutkan pada Mesin yang tidak sadar." Ini memberi kita a$O(\log n)$$ST=\Omega(n^2)$ batas bawah untuk saat itu.$n^2/\log n$

Dengan sedikit lebih detail: Kita dapat membuang operasi 5 di atas. Secara longgar, jika kita sudah dapat membandingkan kepala dua daftar dan mencetak kepala daftar, maka tidak perlu bagi kita untuk mengisolasi kepala daftar pada daftar tertentu. Dengan asumsi ini, kita melihat bahwa setiap register di mesin hanya pernah menyimpan substring terakhir dari input.

Misalkan program register kita memiliki baris kode dan register k , X $\ell$$k$ .$X_1,\dots,X_k$

Perbaiki . Kami membangun program percabangan perbandingan untuk string dengan panjang n sebagai berikut. Buat simpul untuk setiap tupel ( i , d 1 , … , d k ) di mana 1 ≤ i ≤ ℓ dan 0 ≤ d 1 , … , d k ≤ n . Idenya adalah, perhitungan dalam mesin register sesuai dengan jalur dalam program percabangan, dan kami berada di simpul ( i , d 1 , ... , $n$$n$$(i,d_1,\dots,d_k)$$1\le i\le \ell$$0\le d_1 ,\dots, d_k \le n$ jika kita berada pada baris i di mesin register dan panjang string yang disimpan dalam X i adalah d i . Sekarang, kita harus mendefinisikan tepi diarahkan dari program percabangan$(i,d_1 ,\dots, d_k)$$i$$X_i$$d_i$

Jika baris adalah dari formulir$i$

jika maka goto i 1 goto i $X_u<X_v$$i_1$$i_2$

maka untuk semua , simpul ( i , d 1 , ... , d k ) dilabeli dengan membandingkan elemen d u -th dan d v -th input, dan memiliki edge "true" masuk ke ( i 1 , d 1 , … , d k ) , dan "false" edge to ( i 2$d_1,\dots,d_k$$(i,d_1,\dots,d_k)$$d_u$$d_v$$(i_1,d_1,\dots,d_k)$ .$(i_2,d_1,\dots,d_k)$

Jika baris adalah dari formulir$i$

, goto line i $X_1 \leftarrow tail(X_2)$$i'$

lalu ada panah dari sembarang simpul ke ( i ′ , d 2 - 1 , … , d k ) .$(i,d_1,\dots,d_k)$$(i',d_2-1,\dots,d_k)$

Jika baris adalah dari formulir$i$

$print(head(X_u))$ , goto line $i'$

lalu ada panah dari sembarang simpul ke ( i ′ , d 1 , … , d k ) yang dilabeli oleh$(i,d_1,\dots,d_k)$$(i',d_1,\dots,d_k)$ simpul -th input.$d_u$

Semoga contoh-contoh ini memperjelas bagaimana saya bermaksud membangun program percabangan saya. Ketika semua dikatakan dan dilakukan, program percabangan ini memiliki paling banyak node, sehingga memiliki ruang O ( log n $\ell\cdot n^k$$O(\log n)$

Apakah Anda dapat menghitung elemen? Lalu, saya pikir, ada implementasi Mergesort yang cukup mudah. Jika Anda dapat menempatkan simbol tambahan pada tumpukan, Anda dapat menyelesaikannya dengan 3 tumpukan seperti ini:

Jika kami hanya memiliki satu elemen, daftar sudah diurutkan. Sekarang asumsikan kita telah mengurutkan bagian atas tumpukan. Kita dapat menyalin bagian atas (dalam urutan terbalik) ke tumpukan kedua dan menempatkan simbol pemisahan di atasnya. Sekarang kita memiliki 3 tumpukan (karena kita dapat mengabaikan simbol yang sudah disortir di bawah simbol pemisahan) dan dapat mengurutkan setengah bagian bawah. Akhirnya kita dapat menyalin bagian bawah yang diurutkan ke tumpukan ketiga dalam urutan terbalik dan menggabungkan kedua bagian kembali ke tumpukan asli.

Semua biaya operasi waktu linear, oleh karena itu kami telah mengurutkan daftar di $O(n \log n)$

(Perhatikan, bahwa kita membutuhkan tumpukan ukuran $n \log n$ karena simbol pemisahan, tetapi ini dapat dengan mudah diperbaiki dengan menggunakan tumpukan lain)

Karena Anda tidak dapat meletakkan elemen baru di tumpukan, Anda mungkin mendapatkan masalah di titik pemisahan. Untuk mengatasi ini, Anda dapat melakukan yang berikut dengan beberapa tumpukan tambahan:

Salin bagian atas ke tumpukan tambahan, kemudian lanjutkan dengan elemen yang tersisa seperti sebelumnya. Sekarang Anda tahu persis jumlah elemen yang perlu Anda pertimbangkan dalam setiap langkah dan karenanya tidak memerlukan simbol pemisahan.$n-2^{\lfloor \log n\rfloor}$

$\log n$$c$$cn \log n+c\frac{n}{2} \log \frac{n}{2}+c\frac{n}{4} \log \frac{n}{4}+\ ... = O(n \log n)$$O(n \log n)$