Seperti yang dibahas di ruang Lounge di Stack Overflow:
jika Anda tidak dapat mengimplementasikan algoritma Quicksort yang diberikan en.wikipedia.org/wiki/Quicksort dalam bahasa apa pun yang Anda memiliki pengetahuan minimal, Anda mungkin ingin mempertimbangkan profesi yang berbeda. @sbi
tapi SBI juga mencatat bahwa mungkin BrainF *** adalah pengecualian.
Jadi, inilah teka-teki / tantangannya: terapkan QuickSort di BrainF *** . Implementasinya harus
code-challenge
sorting
brainfuck
Ronald
sumber
sumber
Jawaban:
BrainF * (697 bytes)
Di bawah ini adalah versi beranotasi. Untuk melacak apa yang seharusnya terjadi saat mengembangkannya, saya menggunakan notasi komentar yang terlihat seperti ini:
|a|b=0|c=A0|@d|A0|A1|```|
Memori ditata dengan tumpukan partisi yang sedang tumbuh untuk diproses di sebelah kiri, ruang gores di tengah, dan array diurutkan ke kanan. Array indexing ditangani dengan memindahkan "data bus" yang berisi indeks dan ruang kerja melalui array. Jadi misalnya bus 3-lebar
|i|data|0|A0|A1|A2
, akan menjadi|A0|i-1|data|0|A1|A2
setelah bergeser dengan satu. Partisi dilakukan dengan menjaga bus antara elemen tinggi dan rendah.Ini versi lengkapnya:
sumber
if (i<j) {} else {}
beberapa kali untuk melakukan yang benar. Dan kasus tepi adalah pembunuh. Saya tidak tahu berapa kali saya berpikir "hanya satu hal kecil ini yang tersisa ..." dan kemudian menemukan sebuah test case yang menyebabkan beberapa jam lagi bekerja. Saya pikir saya bisa menguranginya dengan beberapa lusin karakter, tetapi saya tidak yakin saya ingin mengusahakannya.brainfuck (178 bytes)
Bahkan jika brainfuck rumit, itu membantu untuk bekerja dengan butir bahasa. Tanyakan kepada diri sendiri, "Apakah saya harus menyimpan nilai ini secara eksplisit di dalam sel?" Anda sering dapat memperoleh kecepatan dan kehebatan dengan melakukan sesuatu yang lebih halus. Dan ketika nilainya adalah indeks array (atau bilangan alami arbitrer), mungkin tidak muat dalam sel. Tentu saja, Anda bisa menerimanya sebagai batasan program Anda. Tetapi merancang program Anda untuk menangani nilai-nilai besar sering kali akan membuatnya lebih baik dengan cara lain.
Seperti biasa, versi kerja pertama saya dua kali lebih lama dari yang seharusnya — 392 byte. Sejumlah modifikasi dan dua atau tiga penulisan ulang utama menghasilkan versi 178 byte yang relatif anggun ini. (Meskipun mengherankan jenis waktu linear hanya 40 byte.)
Nilai input ditempatkan setiap tiga sel: untuk setiap sel (V), ada sel abel (L) (digunakan untuk navigasi) dan satu sel lagi untuk ruang gores (S). Tata letak keseluruhan array adalah
0 1 0 0 0 SVLSVL ... SVL 0 0 0 0 0 0 ...
Awalnya semua sel L diatur ke 1, untuk menandai bagian dari array yang masih perlu disortir. Ketika kita selesai mempartisi subarray, kita membaginya menjadi subarrays yang lebih kecil dengan mengatur sel L pivot menjadi 0, kemudian menemukan sel L paling kanan yang masih 1 dan mempartisi subarray berikutnya. Anehnya, ini semua pembukuan yang kita butuhkan untuk menangani pemrosesan rekursif subarrays dengan benar. Ketika semua sel L telah memusatkan perhatian, seluruh array diurutkan.
Untuk mempartisi subarray, kami menarik nilai paling kanan ke dalam sel S untuk bertindak sebagai pivot, dan membawanya (dan sel V kosong yang sesuai) ke kiri, membandingkannya dengan nilai satu sama lain di subarray dan bertukar sesuai kebutuhan. Pada akhirnya pivot akan ditukar kembali, menggunakan kode swap yang sama (yang menghemat 50 byte atau lebih). Selama mempartisi, dua sel L ekstra disimpan set ke 0, untuk menandai dua sel yang mungkin perlu ditukar satu sama lain; di akhir partisi, 0 kiri akan menyatu dengan 0 di sebelah kiri subarray, dan 0 kanan akan berakhir menandai porosnya. Proses ini juga meninggalkan 1 tambahan di sel L di sebelah kanan subarray; loop utama dimulai dan berakhir di sel ini.
sumber