Menyortir menggunakan kotak hitam

Asumsikan kita ingin mengurutkan daftar dari bilangan real. Anggaplah kita diberi kotak hitam yang dapat mengurutkan bilangan real secara instan. Berapa banyak keuntungan yang bisa kita peroleh dengan menggunakan kotak hitam ini?n $S$$n$$\sqrt n$

Misalnya, dapatkah kita mengurutkan angka hanya dengan panggilan ke kotak hitam? Algoritma terbaik yang saya temukan menggunakan panggilan ke kotak hitam. Tapi saya belum bisa memperbaikinya lebih lanjut. Berikut ini adalah algoritma saya yang mirip dengan merge-sort:$O(\sqrt n)$$n$

Pertama mempartisi daftar menjadi daftar dengan ukuran kira-kira . Kemudian gunakan panggilan ke kotak hitam untuk mengurutkan daftar ini. Akhirnya, gabungkan daftar yang diurutkan menggunakan kotak hitam sebagai berikut:$S$ s1,s2,. . . ,s$\sqrt n$$s_1, s_2, ..., s_{\sqrt n}$$\sqrt n$$\sqrt n$

Letakkan elemen terkecil dari daftar di daftar baru , lalu panggil kotak hitam untuk mengurutkannya. Jumlah di (pertama dan elemen terkecil ) akan menjadi nomor terkecil di . Kita bisa meletakkannya di tempat pertama dari daftar keluaran. Dengan asumsi elemen telah dipilih dari , kita ganti dengan elemen terkecil kedua daftar semacam , dan lagi menjalankan kotak hitam di atasnya untuk menghitung anggota terkecil kedua . Kami melanjutkan sampai semua elemen diurutkan. Jumlah total panggilan kotak hitam untuk bagian ini adalahL [ 1 ] L S s j L [ 1 ] s j S n - $L$$L[1]$$L$$S$
$s_j$$L[1]$$s_j$$S$
$n - \sqrt n$. Oleh karena itu secara keseluruhan jumlah total panggilan akan .$n$

Di sisi lain, sepertinya kita harus dapat memperoleh batas bawah menggunakan batas bawah pada perbandingan jumlah yang diperlukan untuk menyortir sebagai berikut: Kita dapat menerapkan kotak hitam menggunakan perbandingan. Jika kita dapat menyelesaikan masalah dengan panggilan ke kotak hitam dan menggabungkan waktu linear, kita dapat mengurutkan bilangan real dengan perbandingan yang tidak mungkin.o($\sqrt n \lg \sqrt n = \frac{1}{2} \sqrt n \lg n$no(nlgn$o(\sqrt n)$$n$$o(n \lg n)$

Saya kira kita dapat membuktikan bahwa adalah batas bawah untuk jumlah panggilan ke kotak hitam, karena banyak perbandingan yang digunakan dalam kotak hitam akan dibagikan dan karenanya diceritakan dalam argumen kami.$\Omega(n)$

UPDATE: Seperti yang disarankan oleh posting lain, sebuah juga dapat dicapai.$\sqrt n \lg n$

Dimungkinkan untuk menyortir dengan panggilan ke kotak hitam dan tidak ada perbandingan.$O(\sqrt n\log n)$

Pertama, pertimbangkan masalah pembagian berimbang berikut: diberikan elemen A [ 1 .. m ] (di mana $m$$A[1..m]$), bagi mereka menjadi dua kelompok, ukuran terkecil setidaknya sekitarm/4, sehingga semua elemen dalam kelompok pertama lebih kecil dari semua elemen dalam kelompok kedua. Ini dapat dilakukan denganO(m/$\sqrt n \le m \le n$$m/4$panggilan ke kotak hitam. (Saya akan jelaskan nanti.) Kemudian gunakan quicksort dengan algoritma partisi ini:$O(m/\sqrt n)$

def qsort(A[1..m]):
   if m < sqrt(n): sort A with one call to the black box
   else:
     Partition A[1..m] into two groups as described above.
     Recursively qsort the first group.
     Recursively qsort the second group.

Dengan asumsi setiap langkah partisi membutuhkan panggilan ke kotak hitam, algoritma di atas, diberi inputA[1 ..n], akan menghasilkanO($O(m/\sqrt n)$$A[1..n]$memanggil ke kotak hitam, karena pohon rekursi memiliki kedalamanO(logn)dan setiap tingkat pohon memiliki totalO(n/$O(\sqrt n\log n)$$O(\log n)$panggilan ke kotak hitam.$O(n/\sqrt n) = O(\sqrt n)$

Lakukan langkah pemartisian sebagai berikut:

def partition(A[1..m]):  (where sqrt(n) <= m <= n)
   Divide A into m/sqrt(n) groups of size sqrt(n) each.
   Sort each group with one call to the black box per group.
   Sort the medians of the groups with one call to the black box.
   (Note the number of groups is less than sqrt(n), because m <= n.)
   Let X be the median of the medians.
   Partition all m elements around X, using the black box as follows:
      For each group G, let Y be its median:
        Call the black box once on (G - {Y}) union {X}.
        (This gives enough information to order all elts w.r.t. X.)

Saya pikir pertanyaan Anda telah dialamatkan dalam makalah Beigel dan Gill " Menyortir n objek menggunakan k-sorter " dari tahun 1990 dan abstrak makalah ini mengatakan semuanya:

K-sorter adalah perangkat yang mengurutkan objek k dalam satuan waktu. Kompleksitas suatu algoritma yang menggunakan penyortir-k didefinisikan sebagai jumlah aplikasi penyusun-k. Dalam ukuran ini, kompleksitas pengurutan n objek adalah antara dan4nlog$\frac{n \log n}{k \log k}$ , hingga istilah orde pertama dalam n dan k.$\frac{4n \log n}{k \log k}$

Hal ini dimungkinkan untuk memilah obliviously dengan panggilan ke kotak hitam, masing-masing diterapkan pada subarray yang berdekatan dari input asli. Algoritma tidak pernah menyentuh data input kecuali melalui panggilan kotak hitam. Secara khusus, urutan yang sama dari panggilan kotak hitam hanya fungsi darin, bukan data input aktual (karenanya "tidak menyadari").$O(\sqrt{n}\log n)$$n$

Berikut ini adalah sketsa dari algoritma yang lebih sederhana, yang menggunakan kotak hitam yang mengurutkan subarrays dari ukuran bukan hanya $k$ . Jumlah total panggilan ke kotak hitam kira-kira2(n/k)2. Untuk kesederhanaan notasi, asumsikan bahwakadalah genap dan2n/kadalah bilangan bulat ganjil.$\sqrt{n}$$2(n/k)^2$$k$$2n/k$

BlockBubbleSort(X[0..n-1], k):
   m = floor(n/k)
   for i = 1 to m
      for j = 0 to m-1
          BlackBoxSort(X[j*k .. (j+1)*k-1])
      for j = 0 to m-1
          BlackBoxSort(X[j*k + k/2 .. (j+1)*k + k/2 - 1])

Berikut adalah diagram algoritma untuk dan k = 4 . Data bergerak dari kiri ke kanan; setiap kotak adalah k -sorter.$n=18$$k=4$$k$

$k/2$$k$

$O((n/k)^2)$$O((n/k)\log^2(n/k)) = O(\sqrt{n}\log^2 n)$$O((n/k)\log (n/k)) = O(\sqrt{n}\log n)$