Sebuah pertanyaan kode-golf menyortir klasik

11

Ini adalah pertanyaan kode-golf.

Memasukkan

Daftar bilangan bulat non-negatif dalam format apa pun adalah yang paling nyaman.

Keluaran

Daftar yang sama dalam urutan diurutkan dalam format apa pun adalah yang paling nyaman.

Larangan

  • Kode Anda harus dijalankan dalam waktu O (n log n) dalam kasus terburuk di mana njumlah bilangan bulat dalam input. Ini berarti bahwa quicksort acak keluar misalnya. Namun ada banyak pilihan lain untuk dipilih.
  • Jangan gunakan perpustakaan sortir / fungsi / serupa. Juga jangan gunakan apa pun yang sebagian besar berfungsi untuk Anda seperti perpustakaan tumpukan. Pada dasarnya, apa pun yang Anda implementasikan, implementasikan dari awal.

Anda dapat mendefinisikan suatu fungsi jika Anda suka tetapi kemudian tolong tunjukkan contohnya dalam program lengkap yang benar-benar berfungsi. Ini harus berjalan dengan sukses dan cepat pada semua test case di bawah ini.

Uji kasus

In: [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
Out:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In: [72, 59, 95, 68, 84]
Out:[59, 68, 72, 84, 95]

In: [2, 2, 1, 9, 3, 7, 4, 1, 6, 7]
Out:[1, 1, 2, 2, 3, 4, 6, 7, 7, 9]

In: [2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324,  667269]
Out:[667269,1925225, 2276714, 2397725,3088926, 3304534, 4274324, 4487711, 7806949, 8337622]

Jawaban anda

Silakan sebutkan algoritma penyortiran yang telah Anda terapkan dan lamanya solusi Anda dalam judul jawaban Anda.

Algoritma pengurutan waktu O (n log n)

Ada banyak algoritma waktu O (n log n) yang ada. Tabel ini memiliki daftar beberapa di antaranya.


sumber
Beberapa set fungsi seperti intersectsecara otomatis mengurutkan array. Saya kira Anda juga ingin menyingkirkannya. Bagaimana dengan unique(menghapus duplikat, mengurutkan hasilnya)?
Luis Mendo
@ DonMuesli saya lakukan .. Saya pikir intersectberada di bawah "mirip" jika secara otomatis mengurutkan array. Jika Anda menghapus duplikat Anda akan memberikan output yang salah.
Tentang memberikan input yang salah, serahkan itu kepada saya :-) Bisakah "menghapus duplikat dan mengurutkan" digunakan?
Luis Mendo
3
Nitpick: 0 bukan bilangan bulat positif. (Di Bawah Input )
gelas kimia
1
Saya suka bagaimana segera setelah pertanyaannya ada hubungannya dengan kinerja semua orang berduyun-duyun dari bahasa golf meskipun ini masih kode-golf dan solusi terpendek masih akan menang.
Cyoce

Jawaban:

8

Haskell, 87 80 89

s%[]=s
(x:a)%q|x<=q!!0=x:a%q
p%q=q%p
j(x:y:s)=x%y:j s
j a=a
r[x]=x
r s=r$j s
s=r.map(:[])

Ini adalah semacam gabungan, diterapkan dari bawah ke atas. pertama-tama kita mengemas setiap elemen ke dalam daftar itu sendiri, dan kemudian menggabungkannya dua demi dua, dan kembali menggabungkannya dua demi dua, hingga kita dibiarkan dengan satu daftar.

(%)adalah fungsi
jgabungan menggabungkan pasangan dalam daftar daftar
rmenggabungkan daftar daftar lengkap
sadalah fungsi penyortiran.

Penggunaan: Jalankan juru bahasa, dan masukkan s [3,5,2,6,7].

Sunting: cara saya menggabungkan sesuatu sebelumnya bukan urutan yang benar, Jadi untuk memperbaikinya saya membutuhkan 9 karakter lagi.

haskeller bangga
sumber
1
@Lembik jika Anda ingin menguji program, dan Anda tidak ingin menginstal Haskell, Anda dapat menggunakan ideone, dan menambahkan garis seperti main = print (s [5,3,6,8]), yang akan mengatur utama untuk mencetak hasil penyortiran.
haskeller bangga
Saya pikir Anda tidak perlu []%s=s, karena jika elemen pertama [], (x:a)pertandingan gagal dan case terakhir membalik elemen, sehingga s%[]berhasil.
nimi
Anda adalah pemenangnya! Satu-satunya jawaban menggunakan byte lebih sedikit tidak berjalan di O (n log n).
@Lembik Benar, saya lupa jawaban Jelly tidak sesuai.
haskeller bangga
1
Sekarang tampaknya :)
5

JavaScript (ES6), 195 193 191 189 188 186 183 182 179 174 172 byte

Ini adalah implementasi heapsort. Saya berharap seseorang menghasilkan mergesort yang lebih pendek, tetapi saya suka yang ini: P

Pembaruan: R mergesort dikalahkan. Ruby selanjutnya: D

S=l=>{e=l.length
W=(a,b)=>[l[a],l[b]]=[l[b],l[a]]
D=s=>{for(;(c=s*2+1)<e;s=r<s?s:e)s=l[r=s]<l[c]?c:s,W(r,s=++c<e&&l[s]<l[c]?c:s)}
for(s=e>>1;s;)D(--s)
for(;--e;D(0))W(0,e)}

Test (Firefox)

PurkkaKoodari
sumber
Saya ingin sekali menulis jawaban heapsort, tetapi itu tidak bekerja dengan baik pada Haskell. Percobaan saya berikutnya adalah JS, tetapi Anda sudah melakukannya. Mungkin saya masih akan melakukan itu. Idk
bangga haskeller
@proudhaskeller Ah ya .. saya baru saja mencari stackoverflow.com/a/2186785/2179021 .
3

Python3, 132 byte

def S(l):
 if len(l)<2:return l
 a,b,o=S(l[::2]),S(l[1::2]),[]
 while a and b:o.append([a,b][a[-1]<b[-1]].pop())
 return a+b+o[::-1]

Mergesort sederhana. Banyak byte yang dihabiskan untuk memastikan ini benar-benar berjalan di O (n log n), jika hanya algoritma , tetapi bukan implementasi yang perlu O (n log n), ini dapat dipersingkat:

Python3, 99 byte

def m(a,b):
 while a+b:yield[a,b][a<b].pop(0)
S=lambda l:l[1:]and list(m(S(l[::2]),S(l[1::2])))or l

Ini bukan O (n log n) karena .pop(0)O (n), membuat fungsi gabungan O (n ^ 2). Tapi ini cukup buatan, karena .pop(0)bisa saja dengan mudah O (1).

orlp
sumber
Terima kasih untuk ini. Saya pasti maksudkan algoritma dan implementasinya harus O (n log n).
Untuk menjadi jelas, ini berarti bahwa versi 132 adalah OK tetapi versi 99 byte tidak memenuhi.
2

Julia, 166 byte

m(a,b,j=1,k=1,L=endof)=[(j<=L(a)&&k<=L(b)&&a[j]<b[k])||k>L(b)?a[(j+=1)-1]:b[(k+=1)-1]for i=1:L([a;b])]
M(x,n=endof(x))=n>1?m(M(x[1:(q=ceil(Int,n÷2))]),M(x[q+1:n])):x

Fungsi utama dipanggil Mdan itu memanggil fungsi pembantu m. Ini menggunakan semacam gabungan , yang memiliki O ( n log n ) sebagai kompleksitas kasus terburuknya.

Contoh penggunaan:

x = [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
println(M(x))              # prints [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
println(M(x) == sort(x))   # prints true

Tidak Disatukan:

function m(a, b, i=1, k=1, L=endof)
    return [(j <= L(a) && k <= L(b) && a[j] < b[k]) || k > L(b) ?
            a[(j+=1)-1] : b[(k+=1)-1] for i = 1:L([a; b])]
end

function M(x, n=endof(x))
    q = ceil(Int, n÷2)
    return n > 1 ? m(M(x[1:q]), M([q+1:n])) : x
end
Alex A.
sumber
Senang melihat Julia di sini. Sekarang kita perlu nim dan karat juga :)
1
@Lembik Saya pikir Sp3000 dan Doorknob masing-masing adalah pakar Nim dan Rust kami. Semoga mereka ikut bersenang-senang juga. ;)
Alex A.
2

R, 181 byte, Mergesort

L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}

Diindentasi, dengan baris baru:

L=length
s=function(S)
    if(L(S)<2){
        S
    }else{
        h=1:(L(S)/2)
        A=s(S[h])
        B=s(S[-h])
        Z=c()
        if(A[L(A)]>B[1])
#Merge helper function incorporated from here ...
            while(L(A)&L(B))
                if(A[1]<B[1]){
                    Z=c(Z,A[1])
                    A=A[-1]
                }else{
                    Z=c(Z,B[1])
                    B=B[-1]
                }
#...to here. Following line both finishes merge function and handles 'else' case:
        c(Z,A,B)
    }

Kasus uji:

> L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}
> s(c(2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324,  667269))
 [1]  667269 1925225 2276714 2397725 3088926 3304534 4274324 4487711 7806949 8337622
> s(c(2, 2, 1, 9, 3, 7, 4, 1, 6, 7))
 [1] 1 1 2 2 3 4 6 7 7 9
> s(c(72, 59, 95, 68, 84))
 [1] 59 68 72 84 95
> s(c(9, 8, 3, 2, 4, 6, 5, 1, 7, 0))
 [1] 0 1 2 3 4 5 6 7 8 9
plannapus
sumber
2

Scala, fungsi 243 Byte (315 Bytes aplikasi yang berdiri sendiri), Mergesort

Jawaban ini dimaksudkan sebagai fungsi, tetapi dapat diperluas menjadi aplikasi yang berdiri sendiri.

Hanya fungsi (243 byte):

object G{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
}

Aplikasi yang berdiri sendiri (315 byte):

object G extends App{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
println(s(args(0).split(",").map(_.toInt).toStream).toList)
}

Pemakaian:

Fungsi: G.s(List(**[Paste your array here]**).toStream).toList

Aplikasi: sbt "run **[Paste your array here]**"

Input Contoh:

scala> G.s(List(10,2,120,1,8,3).toStream).toList

(OR)

$ sbt "run 5423,123,24,563,65,2,3,764"

Keluaran:

res1: Daftar [Int] = Daftar (1, 2, 3, 8, 10, 120)

ATAU

Daftar (2, 3, 24, 65, 123, 563, 764, 5423)

Kendala & pertimbangan:

  • Membutuhkan scalaz (perpustakaan sangat umum, tidak digunakan untuk menyortir di sini)
  • 100% fungsional (tidak ada yang bisa berubah!)

Atribusi:

Ruslan
sumber
2

Jelly, 29 byte, menggabungkan semacam

Seperti orlp's Python answer, ini menggunakan list.pop(0)under the hood, yang mana O(n), tetapi implementasinya secara formal O(n log n).

ṛð>ṛḢð¡Ḣ;ñ
ç;ȧ?
s2Z߀ç/µL>1µ¡

Coba di sini.

Penjelasan

               Define f(x, y):    (merge helper)
                 Implicitly store x in α.
ṛ    ð¡          Replace it with y this many times:
 ð>ṛḢ              (x > y)[0].
       Ḣ         Pop the first element off that list (either x or y).
        ;ñ       Append it to g(x, y).

               Define g(x, y):    (merge)
  ȧ?             If x and y are non-empty:
ç                  Return f(x, y)
                 Else:
 ;                 Return concat(x, y).

               Define main(z):    (merge sort)
       µL>1µ¡    Repeat (len(z) > 1) times:
s2                 Split z in chunks of length two.   [[9, 7], [1, 3], [2, 8]]
  Z                Transpose the resulting array.     [[9, 1, 2], [7, 3, 8]]
   ߀              Apply main() recursively to each.  [[1, 2, 9], [3, 7, 8]]
     ç/            Apply g on these two elements.     [1, 2, 3, 7, 8, 9]
Lynn
sumber
Tolong tambahkan beberapa penjelasan.
Ada banyak yang harus dijelaskan :) Biarkan saya melihat apakah saya bisa bermain golf di baris terakhir sedikit lebih
Lynn
Ketika Anda mengatakan implementasinya adalah O (n log n) tetapi menggunakan list.pop (0) di bawah kap, yaitu O (n) saya bingung. Maksud kamu apa?
Maksud saya persis apa yang orlp tulis dalam jawabannya: Ini bukan O (n log n) karena .pop(0)O (n), membuat fungsi gabungan O (n ^ 2). Tapi ini cukup buatan, karena .pop(0)bisa saja dengan mudah O (1).
Lynn
Jelly diimplementasikan dalam Python dan diimplementasikan sebagai .pop(0).
Lynn
1

Ruby, 167 byte

Algoritme gabungan jenis golf, yang memiliki kasus terburuk O

f=->x{m=->a,b{i,j,l,y,z=0,0,[],a.size,b.size
while i<y&&j<z
c=a[i]<b[j]
l<<(c ?a[i]:b[j])
c ?i+=1:j+=1
end
l+=a[i,y]+b[j,z]}
l=x.size
l>1?m[f[x[0,l/2]],f[x[l/2,l]]]:x}

Uji di sini!

Untuk menguji, menyalin dan menempelkan kode ke jendela, dan menambahkan puts f[x]di bagian bawah, di mana x adalah array dengan input. (Pastikan Anda memilih Ruby sebagai bahasa, tentu saja) Misalnya,puts f[[2, 2, 1, 9, 3, 7, 4, 1, 6, 7]]

Nilai Tinta
sumber
Terima kasih untuk ini! Bisakah Anda menunjukkannya juga berfungsi?
1
Saya menambahkan tautan sehingga Anda dapat mengujinya.
Nilai Tinta
1

Ruby, 297 byte

Gabungkan semacam. Program lengkap, alih-alih fungsi. Membutuhkan dua argumen saat runtime: file input dan file output, masing-masing dengan satu elemen per baris.

if $0==__FILE__;v=open(ARGV[0]).readlines.map{|e|e.to_i}.map{|e|[e]};v=v.each_slice(2).map{|e|a,b,r=e[0],e[1],[];while true;if(!a)||a.empty?;r+=b;break;end;if(!b)||b.empty?;r+=a;break;end;r<<(a[0]<b[0]?a:b).shift;end;r}while v.size>1;open(ARGV[1],"w"){|f|f.puts(v[0].join("\n"))if !v.empty?};end
jose_castro_arnaud
sumber
Jika itu akan memperpendek kode Anda, Anda harus mempertimbangkan mengadaptasi kode menjadi fungsi yang mendapatkan array sebagai input dan mengembalikan urutan yang diurutkan. tampaknya itu akan membantu Anda menghilangkan banyak byte.
haskeller bangga
Jika Anda akan menjadikannya sebagai program lengkap alih-alih fungsi, bolehkah saya menyarankan menggunakan STDIN dan STDOUT sebagai input / output, masing-masing? $stdin.readlinessudah lebih sedikit byte daripada open(ARGV[0]).readlines, sama dengan putslebihopen(ARGV[1],"w"){|f|f.puts
Nilai Tinta
2
Dan hal-hal seperti if $0==__FILE__benar-benar tidak perlu dalam kode golf. Anda juga dapat mengganti masing ;- masing dengan baris baru - ini adalah jumlah byte yang sama dan (mungkin) menghilangkan gulir kode secara horizontal. Juga, saya akan merekomendasikan memeriksa tips untuk bermain golf di Ruby .
daniero