Saya memiliki dataset yang merupakan sejumlah objek yang disusun dalam kotak 2-D. Saya tahu saya memiliki urutan ketat, meningkat saat Anda bergerak dari kiri ke kanan di setiap baris, dan meningkat dari atas ke bawah dalam setiap kolom. Sebagai contoh,
- 1 2 3
- 4 6 7
- 5 8 9
Bisakah saya meningkatkan penyortiran naif untuk mengurutkan seluruh dataset secara linier (sebagaimana diukur dalam perbandingan)?
Bagaimana dengan set data nd? Dataset terbatas sewenang-wenang dengan subset perbandingan yang diketahui?
ds.algorithms
total-ordering
sorting
Zachary Vance
sumber
sumber
Jawaban:
Sangat mudah untuk membuktikan Ω (n 2 log n) dengan batas bawah pada masalah ini (dalam model pengurutan perbandingan): jika elemen pada posisi (i, j) selalu dalam jarak 1/2 dari i + j, maka grid diagonal tidak saling tergantung satu sama lain, dan urutan yang diurutkan dalam setiap kisi diagonal adalah arbitrer. Jadi di bawah batasan ini, jumlah total pemesanan yang mungkin adalah produk (di atas semua diagonal grid) dari faktorial dari panjang diagonal, yang eksponensial dalam n 2 log n.
Yang mengatakan bahwa algoritma pengurutan perbandingan standar optimal asimtotik untuk kisi-kisi yang dipesan seperti yang Anda gambarkan.
sumber
Jika saya memahami masalahnya dengan benar (dan saya mungkin tidak, jangan ragu untuk memberi tahu saya jika saya tidak) Anda ingin mengubah grid 2D menjadi array 1D yang diurutkan, sedangkan setiap baris dan kolom sudah diurutkan dalam grid 2D?
Elemen pertama dalam daftar dalam kasus ini harus sudut kiri atas ((0,0), dengan definisi masalah). Setelah ini, ia harus menjadi elemen (1,0) atau (0,1), karena semua yang lain akan lebih besar dari ini menurut definisi.
Anda dapat menggeneralisasi dengan mengatakan bahwa elemen terkecil berikutnya dalam kisi selalu langsung di bawah elemen yang sudah digunakan (atau tepi kisi), dan juga di sebelah kanan elemen yang sudah digunakan (atau tepi kisi), karena keduanya didefinisikan lebih kecil dari itu. Jadi pada setiap iterasi Anda hanya harus mempertimbangkan nilai terkecil yang memenuhi persyaratan ini.
Anda dapat menyimpan kandidat yang mungkin dalam urutan diurutkan saat Anda menemukannya (tidak lebih dari dua akan tersedia dalam satu iterasi), dan pada setiap iterasi periksa nilai-nilai baru yang disediakan (jika ada). Jika mereka lebih rendah dari yang terendah dari kandidat sebelumnya, tambahkan langsung ke daftar dan ulangi, jika tidak tambahkan kandidat sebelumnya yang terendah dan bandingkan dengan yang terendah berikutnya dll.
Sayangnya saya tidak mengklaim dapat memberikan kompleksitas yang tepat dari ini, saya juga tidak mengklaim itu adalah yang paling efisien, itu tampaknya lebih baik daripada pendekatan naif, dan saya harap saya menjelaskannya dengan cukup baik untuk Anda mengerti.
EDIT: Untuk grid nd seperti ini saya percaya prinsip dasar yang sama berlaku, tetapi setiap iterasi membuat hingga n kandidat baru yang tersedia, dan kandidat ini harus menjadi elemen terkecil yang tidak digunakan dalam setiap n dimensi pada saat ini.
sumber