Merge sort adalah algoritma pengurutan yang berfungsi dengan memisahkan daftar yang diberikan menjadi dua, menyortir secara rekursif kedua daftar yang lebih kecil, dan menggabungkannya kembali menjadi satu daftar yang diurutkan. Kasus dasar rekursi adalah tiba pada daftar tunggal, yang tidak dapat dibagi lebih lanjut tetapi per definisi sudah diurutkan.
Eksekusi algoritma pada daftar [1,7,6,3,3,2,5]
dapat divisualisasikan dengan cara berikut:
[1,7,6,3,3,2,5]
/ \ split
[1,7,6,3] [3,2,5]
/ \ / \ split
[1,7] [6,3] [3,2] [5]
/ \ / \ / \ | split
[1] [7] [6] [3] [3] [2] [5]
\ / \ / \ / | merge
[1,7] [3,6] [2,3] [5]
\ / \ / merge
[1,3,6,7] [2,3,5]
\ / merge
[1,2,3,3,5,6,7]
Tugas
Tulis program atau fungsi yang mengambil daftar bilangan bulat dengan cara apa pun yang masuk akal sebagai input dan memvisualisasikan partisi yang berbeda dari daftar ini saat sedang diurutkan oleh algoritma pengurutan gabungan. Ini berarti Anda tidak perlu menampilkan grafik seperti di atas, tetapi daftar saja tidak apa-apa:
[1,7,6,3,3,2,5]
[1,7,6,3][3,2,5]
[1,7][6,3][3,2][5]
[1][7][6][3][3][2][5]
[1,7][3,6][2,3][5]
[1,3,6,7][2,3,5]
[1,2,3,3,5,6,7]
Selain itu, notasi daftar yang masuk akal baik-baik saja, oleh karena itu yang berikut ini juga akan menjadi output yang valid:
1 7 6 3 3 2 5
1 7 6 3|3 2 5
1 7|6 3|3 2|5
1|7|6|3|3|2|5
1 7|3 6|2 3|5
1 3 6 7|2 3 5
1 2 3 3 5 6 7
Akhirnya, cara untuk membagi daftar menjadi dua daftar yang lebih kecil adalah terserah Anda sepanjang panjang kedua daftar yang dihasilkan paling banyak berbeda satu per satu. Itu berarti alih-alih membelah [3,2,4,3,7]
menjadi [3,2,4]
dan [3,7]
, Anda juga bisa membelah dengan mengambil elemen pada indeks genap dan ganjil ( [3,4,7]
dan [2,3]
) atau bahkan mengacak perpecahan setiap waktu.
Ini adalah kode-golf , jadi kode terpendek dalam bahasa apa pun yang diukur dalam byte menang.
Uji kasus
Seperti disebutkan di atas, format aktual dan cara untuk membagi daftar menjadi dua terserah Anda.
[10,2]
[10][2]
[2,10]
[4,17,1,32]
[4,17][1,32]
[4][17][1][32]
[4,17][1,32]
[1,4,17,32]
[6,5,4,3,2,1]
[6,5,4][3,2,1]
[6,5][4][3,2][1]
[6][5][4][3][2][1]
[5,6][4][2,3][1] <- Important: This step cannot be [5,6][3,4][1,2], because 3 and 4 are on different branches in the the tree
[4,5,6][1,2,3]
[1,2,3,4,5,6]
sumber
[[1,2],[3],[4,5],[6]]
Panggung sebenarnya adalah solusi yang tepat, karena merge sort bekerja secara rekursif. Itu adalah jika kita mulai dengan[1,2,3,4,5,6]
dan membaginya menjadi[1,2,3]
dan[4,5,6]
, maka daftar tersebut diproses secara independen sampai mereka bergabung pada langkah terakhir.[3]
dan[2,1]
, maka itu ada di cabang yang berbeda, jadi kita tidak bisa menggabungkan[3]
dan[2]
setelah[2,1]
itu dibagi menjadi[2]
dan[1]
.Jawaban:
Haskell ,
137128127125121109106 byte(-2) + (- 4) = (- 6) byte berkat nimi ! Mengubahnya untuk mengumpulkan semua langkah dalam daftar (lagi karena nimi) menyimpan 12 byte lagi.
Lain 3 byte karena Laikoni , dengan penjaga pola mengikat dan penggunaan daftar pemahaman untuk menyandikan penjaga.
Cobalah online!
Memisahkan daftar ke dalam elemen aneh dan posisi diposisikan adalah kode yang lebih pendek daripada menjadi dua bagian berurutan, karena kita terhindar harus mengukur
length
, lalu.Bekerja dengan "mencetak" daftar, kemudian berulang dengan daftar terbagi (
x >>= h
) jika memang ada pemisahan, dan "mencetak" daftar yang diurutkan; dimulai dengan daftar satu input; dengan asumsi input tidak kosong. Dan alih-alih mencetak yang sebenarnya, kumpulkan saja dalam daftar.Daftar yang dihasilkan oleh
g[[6,5..1]]
, dicetak baris demi baris, adalah:sumber
p=print
dan tiga kalip
. Cobalah online!g
Anda dapat mengumpulkan semua langkah dalam daftar dan mengembalikannya. Cobalah online!g x|y<-x>>=h=x:[z|x/=y,z<-g y++[sort<$>x]]
menyimpan beberapa byte lagi.Bahasa Wolfram (Mathematica) ,
146127111102 byteCobalah online!
Mengembalikan a
List
yang berisi langkah-langkah.Penjelasan
Dalam input, pisahkan semua
List
yang berisi 2 atau lebih bilangan bulat menjadi dua. Sublist pertama memiliki elemen diindeks ganjil (1-diindeks), dan yang kedua memiliki elemen diindeks genap.Ulangi itu sampai tidak ada yang berubah (yaitu semua daftar panjang-1). Simpan semua hasil antara. Simpan ini (
List
semua langkah) diu
.Jatuhkan elemen terakhir
u
dan balikkan.Dari hasil di atas, urutkan semua kemunculan daftar bilangan bulat.
sumber
Bersih ,
228206168157140121104 byteBuat daftar tahapan dari ujung ke dalam, menggunakan fakta bahwa
n
elemen -th dari ujung adalah versi yang diurutkan darin
elemen -th dari awal.Ide dari komentar JungHwan Min
Cobalah online!
sumber
Arang ,
145133123122 byteCobalah online! Tautan adalah untuk mengucapkan versi kode.
Masih harus bekerja di sekitar bug Arang ...Sunting: Disimpan 5 byte dengan menggunakan gandaMap
sebagai pemahaman array orang miskin. Disimpan 4 byte dengan menggunakanPop
untuk menggandakan iterate pada array. Disimpan 3 byte dengan menggunakan rangkaian alih-alihPush
. Disimpan 10 byte dengan menciptakanwhile
kondisi pegolf yang juga menghindari bug Charcoal. Disimpan 1 byte dengan mengetahui bahwa Charcoal memang memiliki operator filter. Penjelasan:Pisahkan input pada spasi, dan kemudian bungkus hasilnya dalam array luar, simpan itu
q
.Ulangi sementara elemen pertama
q
memiliki lebih dari satu elemen. (Elemen pertamaq
selalu memiliki elemen terbanyak karena cara daftar dibagi menjadi dua.)Cetak elemen
q
gabungan dengan spasi dan garis vertikal. (Array menyebabkan hasil untuk mencetak pada barisnya sendiri. Ada cara lain untuk mencapai ini untuk jumlah byte yang sama.)Buat daftar dengan menduplikasi setiap elemen
q
, lalu petakan daftar itu dan ambil setengah dari setiap daftar (menggunakan pendekatan elemen alternatif), simpan hasilnya kembaliq
.Cetak elemen
q
gabungan dengan spasi dan garis vertikal. Sebenarnya, pada titik ini elemen-elemen dari daftarq
kosong atau elemen tunggal, jadi bergabung dengan mereka hanya mengubahnya menjadi string kosong atau elemen mereka. String kosong akan menambahkan garis trailing yang tidak perlu sehingga mereka disaring. Operator yang rata akan lebih pegolf (seperti⟦⪫Σθ|⟧
).Ulangi sementara
q
memiliki lebih dari satu elemen. (Kode berikut ini membutuhkan jumlah elemen genap.)Salin
q
keh
, tetapi terbalik (lihat di bawah), dan resetq
ke daftar kosong.Ulangi sampai
h
kosong.Ekstrak elemen selanjutnya
h
menjadie
. (Pop
ekstrak dari akhir, itulah sebabnya saya harus membalikkanq
.)Inisialisasi
z
ke daftar kosong.Simpulkan elemen elemen berikutnya
h
.Salin
e
ked
dan setel ulange
ke daftar kosong.Simpulkan elemen-elemen dari
d
.Dorong mereka ke
z
ataue
tergantung pada apakah mereka lebih kecil dari elemen saat ini dari elemen selanjutnyah
.Dorong elemen saat ini dari elemen selanjutnya
h
kez
.Gabungkan
z
dengan elemen apa pun yang tersisae
dan dorong keq
. Ini melengkapi penggabungan dua elemen darih
.Cetak elemen
q
gabungan dengan spasi dan garis vertikal.sumber
while (...Map(...)...)
bug yang sudah saya ceritakan.Python 2 ,
145144 byteIde dari komentar JungHwan Min
-1 byte terima kasih kepada Jonathan Frech
Cobalah online!
sumber
<2
sebagai gantinya==1
.JavaScript (ES6), 145 byte
Mengambil input sebagai array dalam array, yaitu
f([[6,5,4,3,2,1]])
. Bekerja dengan menghasilkan baris pertama dan terakhir dari output, kemudian membelah dan memanggil dirinya sendiri lagi, sampai setiap sub-array memiliki panjang 1. Berikut ini demonstrasi dasar cara kerjanya:sumber
Sekam , 14 byte
Mengambil array yang berisi satu array. Cobalah online!
Penjelasan
Built-in
½
mengambil array dan membaginya di tengah. Jika panjangnya ganjil, bagian pertama lebih panjang dengan satu elemen. Array tunggal[a]
menghasilkan[[a],[]]
dan array kosong[]
memberikan[[],[]]
, jadi perlu untuk menghapus array kosong sebelum menerapkanU
.sumber
Stax ,
116 (÷ 3>)3829 byte CP437-9 byte per komentar oleh @recursive. Sekarang input diberikan sebagai singleton yang satu-satunya elemen adalah array angka yang akan diurutkan.
Cobalah online!
Versi tanpa paket dengan 35 byte:
Penjelasan
Kode dapat dibagi menjadi dua bagian. Bagian pertama memvisualisasikan pemisahan dan yang kedua memvisualisasikan penggabungan.
Kode untuk memvisualisasikan pemisahan:
Kode untuk memvisualisasikan penggabungan:
Versi lama, sebenarnya membangun struktur daftar bersarang.
cc0+=
digunakan tiga kali dalam kode untuk memeriksa apakah bagian atas tumpukan adalah skalar atau array.{{cc0+=!{x!}Mm',*:}}X
membangun blok yang secara rekursif memanggil dirinya sendiri untuk menghasilkan array angka yang bersarang dengan benar. (Output default di Stax membuat vektor array yang bersarang sebelum mencetak).Ada dua blok lain yang melakukan pemisahan dan penggabungan, masing-masing. Mereka terlalu bertele-tele dan saya tidak peduli untuk menjelaskan (ada sedikit lebih banyak informasi dalam versi historis dari posting ini tetapi jangan berharap terlalu banyak).
sumber
cH!
dapat digunakan sebagai pengganticH%!
.{Nd}M
bisa digantiT
juga.