Visualisasikan Gabung Sortir

30

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 , 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]
Laikoni
sumber
5
@dylnan Anda dapat menggunakan algoritme penyortiran lain atau fungsi penyortiran
bawaan
5
Beberapa ide bermain golf: bagian bawah dari hasil dapat dihasilkan dengan mengurutkan setiap sublist di babak pertama dan membalik urutan.
JungHwan Min
2
@Arnauld [[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.
Laikoni
2
@ l4m2 Ok, percobaan terakhir untuk jawaban: 1. Anda perlu pembatas karena juga bilangan bulat> 9 harus didukung. 2. Ini tidak valid untuk alasan yang sama seperti yang diberikan dalam komentar saya di atas. Jika kita membelah menjadi [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].
Laikoni
1
Sebenarnya kalimat setelah itu menjawab pertanyaan saya dengan tepat. Maaf telah melewatkannya. : P
Zgarb

Jawaban:

8

Haskell , 137 128 127 125 121 109 106 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.

import Data.List
g x|y<-x>>=h=x:[z|x/=y,z<-g y++[sort<$>x]]
h[a]=[[a]]
h x=foldr(\x[b,a]->[x:a,b])[[],[]]x

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:

[[6,5,4,3,2,1]]
[[6,4,2],[5,3,1]]
[[6,2],[4],[5,1],[3]]
[[6],[2],[4],[5],[1],[3]]
[[2,6],[4],[1,5],[3]]
[[2,4,6],[1,3,5]]
[[1,2,3,4,5,6]]
Will Ness
sumber
1
... p=printdan tiga kali p. Cobalah online!
nimi
@nimi hebat, lagi, dan terima kasih banyak! sekarang benar-benar terlihat golf . :)
Will Ness
Alih-alih mencetak dalam fungsi, gAnda dapat mengumpulkan semua langkah dalam daftar dan mengembalikannya. Cobalah online!
nimi
3
Saya tidak berpikir bahwa kita memiliki definisi yang tepat tentang "memvisualisasikan". Secara lebih umum tantangannya meminta "mengeluarkan" daftar dan per standar kami, ini dapat dilakukan melalui nilai balik suatu fungsi . Jawaban lain, misalnya 1 , 2 juga melakukannya dengan cara ini. - Saya kira saran saya tidak jauh berbeda, hanya mengumpulkan daftar perantara alih-alih mencetaknya. Jangan ragu untuk mengeditnya.
nimi
3
g x|y<-x>>=h=x:[z|x/=y,z<-g y++[sort<$>x]]menyimpan beberapa byte lagi.
Laikoni
7

Bahasa Wolfram (Mathematica) , 146 127 111 102 byte

Join[u=Most[#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&~FixedPointList~#],Reverse@Most@u/.a:{b}:>Sort@a]&

Cobalah online!

Mengembalikan a Listyang berisi langkah-langkah.

Penjelasan

#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&

Dalam input, pisahkan semua Listyang berisi 2 atau lebih bilangan bulat menjadi dua. Sublist pertama memiliki elemen diindeks ganjil (1-diindeks), dan yang kedua memiliki elemen diindeks genap.

u=Most[... &~FixedPointList~#]

Ulangi itu sampai tidak ada yang berubah (yaitu semua daftar panjang-1). Simpan semua hasil antara. Simpan ini ( Listsemua langkah) di u.

Reverse@Most@u

Jatuhkan elemen terakhir udan balikkan.

... /.a:{b}:>Sort@a

Dari hasil di atas, urutkan semua kemunculan daftar bilangan bulat.

JungHwan Min
sumber
6

Bersih , 228 206 168 157 140 121 104 byte

Buat daftar tahapan dari ujung ke dalam, menggunakan fakta bahwa nelemen -th dari ujung adalah versi yang diurutkan dari nelemen -th dari awal.

Ide dari komentar JungHwan Min

import StdEnv
@u#(a,b)=splitAt(length u/2)u
=if(a>[])[[u]:[x++y\\y<- @b&x<- @a++ @a++ @a]][]++[[sort u]]

Cobalah online!

Suram
sumber
4

Arang , 145 133 123 122 byte

≔⟦⪪S ⟧θW⊖L§θ⁰«⟦⪫Eθ⪫κ ¦|⟧≔EE⊗Lθ§θ÷λ²✂κ﹪λ²Lκ²θ»⟦⪫ΦEθ⪫ι ι|⟧W⊖Lθ«≔⮌θη≔⟦⟧θWη«≔⊟ηε≔⟦⟧ζF⊟η«≔εδ≔⟦⟧εFδ⊞⎇‹IμIλζεμ⊞ζλ»⊞θ⁺ζε»⟦⪫Eθ⪫κ ¦|

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Masih harus bekerja di sekitar bug Arang ... Sunting: Disimpan 5 byte dengan menggunakan ganda Mapsebagai pemahaman array orang miskin. Disimpan 4 byte dengan menggunakan Popuntuk menggandakan iterate pada array. Disimpan 3 byte dengan menggunakan rangkaian alih-alih Push. Disimpan 10 byte dengan menciptakan whilekondisi pegolf yang juga menghindari bug Charcoal. Disimpan 1 byte dengan mengetahui bahwa Charcoal memang memiliki operator filter. Penjelasan:

≔⟦⪪S ⟧θ

Pisahkan input pada spasi, dan kemudian bungkus hasilnya dalam array luar, simpan itu q.

W⊖L§θ⁰«

Ulangi sementara elemen pertama qmemiliki lebih dari satu elemen. (Elemen pertama qselalu memiliki elemen terbanyak karena cara daftar dibagi menjadi dua.)

⟦⪫Eθ⪫κ ¦|⟧

Cetak elemen qgabungan dengan spasi dan garis vertikal. (Array menyebabkan hasil untuk mencetak pada barisnya sendiri. Ada cara lain untuk mencapai ini untuk jumlah byte yang sama.)

≔EE⊗Lθ§θ÷λ²✂κ﹪λ²Lκ²θ»

Buat daftar dengan menduplikasi setiap elemen q, lalu petakan daftar itu dan ambil setengah dari setiap daftar (menggunakan pendekatan elemen alternatif), simpan hasilnya kembali q.

⟦⪫ΦEθ⪫ι ι|⟧

Cetak elemen qgabungan dengan spasi dan garis vertikal. Sebenarnya, pada titik ini elemen-elemen dari daftar qkosong 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 ⟦⪫Σθ|⟧).

W⊖Lθ«

Ulangi sementara qmemiliki lebih dari satu elemen. (Kode berikut ini membutuhkan jumlah elemen genap.)

≔⮌θη≔⟦⟧θ

Salin qke h, tetapi terbalik (lihat di bawah), dan reset qke daftar kosong.

Wη«

Ulangi sampai hkosong.

≔⊟ηε

Ekstrak elemen selanjutnya hmenjadi e. ( Popekstrak dari akhir, itulah sebabnya saya harus membalikkan q.)

≔⟦⟧ζ

Inisialisasi zke daftar kosong.

F⊟η«

Simpulkan elemen elemen berikutnya h.

≔εδ≔⟦⟧ε

Salin eke ddan setel ulang eke daftar kosong.

Fδ

Simpulkan elemen-elemen dari d.

⊞⎇‹IμIλζεμ

Dorong mereka ke zatau etergantung pada apakah mereka lebih kecil dari elemen saat ini dari elemen selanjutnya h.

⊞ζλ»

Dorong elemen saat ini dari elemen selanjutnya hke z.

⊞θ⁺ζε»

Gabungkan zdengan elemen apa pun yang tersisa edan dorong ke q. Ini melengkapi penggabungan dua elemen dari h.

⟦⪫Eθ⪫κ ¦|

Cetak elemen qgabungan dengan spasi dan garis vertikal.

Neil
sumber
Tunggu sebentar. Ada bug lain? : /
ASCII
@ ASCII-only Tidak, ini adalah while (...Map(...)...)bug yang sudah saya ceritakan.
Neil
2

JavaScript (ES6), 145 byte

f=a=>a.join`|`+(a[0][1]?`
${f([].concat(...a.map(b=>b[1]?[b.slice(0,c=-b.length/2),b.slice(c)]:[b])))}
`+a.map(b=>b.sort((x,y)=>x-y)).join`|`:``)

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:

f([[6,5,4,3,2,1]]):
  6,5,4,3,2,1
  f([[6,5,4],[3,2,1]]):
    6,5,4|3,2,1
    f([[6,5],[4],[3,2],[1]]):
      6,5|4|3,2|1
      f([[6],[5],[4],[3],[2],[1]]):
        6|5|4|3|2|1
      end f
      5,6|4|2,3|1
    end f
    4,5,6|1,2,3
  end f
  1,2,3,4,5,6
end f
Produksi ETH
sumber
2
Jadi, adakah titik di mana ada tiga jawaban terikat pada 145 byte?
Neil
2

Sekam , 14 byte

S+ȯ†O↔hUmfL¡ṁ½

Mengambil array yang berisi satu array. Cobalah online!

Penjelasan

S+ȯ†O↔hUmfL¡ṁ½  Implicit input, say A = [[4,17,32,1]].
           ¡    Iterate this function on A:
            ṁ½   Split each array in two, concatenate results: [[4,17],[32,1]]
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[],[17],[],[32],[],[1],[]],
                           ...
        mfL     Map filter by length, removing empty arrays.
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[17],[32],[1]],
                           ...
       U        Longest prefix of unique elements:
                       P = [[[4,17,32,1]],[[4,17],[32,1]],[[4],[17],[32],[1]]]
      h         Remove last element: [[[4,17,32,1]],[[4,17],[32,1]]]
     ↔          Reverse: [[[4,17],[32,1]],[[4,17,32,1]]]
   †O           Sort each inner array: [[[4,17],[1,32]],[[1,4,17,32]]]
S+ȯ             Concatenate to P:
                           [[[4,17,32,1]],
                            [[4,17],[32,1]],
                            [[4],[17],[32],[1]],
                            [[4,17],[1,32]],
                            [[1,4,17,32]]]
                Implicitly print.

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 menerapkan U.

Zgarb
sumber
1

Stax , 116 (÷ 3>) 38 29 byte CP437

-9 byte per komentar oleh @recursive. Sekarang input diberikan sebagai singleton yang satu-satunya elemen adalah array angka yang akan diurutkan.

ƒ3s}óºE/ßB╢↕êb∩áαπüµrL╞¶è,te+

Cobalah online!

Versi tanpa paket dengan 35 byte:

{c{Jm'|*Pc{2Mm:f{fc{Dm$wW{{eoJm'|*P

Penjelasan

Kode dapat dibagi menjadi dua bagian. Bagian pertama memvisualisasikan pemisahan dan yang kedua memvisualisasikan penggabungan.

Kode untuk memvisualisasikan pemisahan:

{                      w    Do the following while the block generates a true value
 c                          Copy current nested array for printing
  {Jm                       Use spaces to join elements in each part
     '|*                    And join different parts with vertical bar 
        P                   Pop and print

         c                  Copy current nested array for splitting
          {2Mm              Separate each element of the array to two smaller parts with almost the same size
                                That is, if the number of elements is even, partition it evenly.
                                Otherwise, the first part will have one more element than the second.
              :f            Flatten the array once
                {f          Remove elements that are empty arrays

                  c         Copy the result for checking 
                   {Dm$     Is the array solely composed of singletons?
                            If yes, ends the loop.

Kode untuk memvisualisasikan penggabungan:

W              Execute the rest of the program until the stack is empty
 {{eoJm        For each part, sort by numeric value, then join with space
       '|*     Join the parts with vertical bar
          P    Pop and print the result

Versi lama, sebenarnya membangun struktur daftar bersarang.

{{cc0+=!{x!}Mm',*:}}Xd;%v:2^^{;s~{c^;<~sc%v,*{2M{s^y!svsm}M}YZ!x!Q,dmU@e;%v:2^{;%v:2^-N~0{c;={scc0+=Cc%v!C:f{o}{scc0+=C{s^y!svsm}?}Y!cx!P,dcm

cc0+= digunakan tiga kali dalam kode untuk memeriksa apakah bagian atas tumpukan adalah skalar atau array.

{{cc0+=!{x!}Mm',*:}}Xmembangun 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).

{                  }X    Store the code block in X
 {           m           Map each element in the list with block
  cc                     Make two copies of the element
    0+                   + 0. If the element is a scalar, nothing will change
                              If the element is an array, the element 0 will be appended
      =!{  }M            If the element has changed after the `0+` operation
                             Which means it is an array
         x!              Recursively execute the whole code block on the element

              ',*        Join the mapped elements with comma
                 :}      Bracerizes the final result

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).

Weijun Zhou
sumber
Perbaikan yang sangat bagus. Saya belum sepenuhnya memahaminya, tetapi saya pikir cH!dapat digunakan sebagai pengganti cH%!.
rekursif
{Nd}Mbisa diganti Tjuga.
rekursif
Saya membuat beberapa adaptasi lagi. staxlang.xyz/… Jawaban Husk mengambil input sebagai array dalam array, jadi saya rasa itu legal.
rekursif
Saya menemukan solusi yang seharusnya 2 karakter ascii lebih pendek, tetapi saya menemukan bug dalam array transpos. Secara khusus, ini mem mutasi baris array. Saya akan menambahkannya ke dalam simpanan untuk 1.0.4
rekursif
BAIK. Saya menantikan pembaruan.
Weijun Zhou