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
n
jumlah 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.
intersect
secara otomatis mengurutkan array. Saya kira Anda juga ingin menyingkirkannya. Bagaimana denganunique
(menghapus duplikat, mengurutkan hasilnya)?intersect
berada di bawah "mirip" jika secara otomatis mengurutkan array. Jika Anda menghapus duplikat Anda akan memberikan output yang salah.Jawaban:
Haskell,
878089Ini 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 fungsij
gabungan menggabungkan pasangan dalam daftar daftarr
menggabungkan daftar daftar lengkaps
adalah 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.
sumber
main = print (s [5,3,6,8])
, yang akan mengatur utama untuk mencetak hasil penyortiran.[]%s=s
, karena jika elemen pertama[]
,(x:a)
pertandingan gagal dan case terakhir membalik elemen, sehinggas%[]
berhasil.JavaScript (ES6),
195193191189188186183182179174172 byteIni adalah implementasi heapsort. Saya berharap seseorang menghasilkan mergesort yang lebih pendek, tetapi saya suka yang ini: P
Pembaruan: R mergesort dikalahkan. Ruby selanjutnya: D
Test (Firefox)
Tampilkan cuplikan kode
sumber
Python3, 132 byte
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
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).sumber
Julia, 166 byte
Fungsi utama dipanggil
M
dan itu memanggil fungsi pembantum
. Ini menggunakan semacam gabungan , yang memiliki O ( n log n ) sebagai kompleksitas kasus terburuknya.Contoh penggunaan:
Tidak Disatukan:
sumber
R, 181 byte, Mergesort
Diindentasi, dengan baris baru:
Kasus uji:
sumber
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):
Aplikasi yang berdiri sendiri (315 byte):
Pemakaian:
Input Contoh:
Keluaran:
Kendala & pertimbangan:
Atribusi:
m()
fungsi) yang terinspirasi oleh jawaban ini: /codereview//a/21590/28856sumber
Jelly, 29 byte, menggabungkan semacam
Seperti orlp's Python answer, ini menggunakan
list.pop(0)
under the hood, yang manaO(n)
, tetapi implementasinya secara formalO(n log n)
.Coba di sini.
Penjelasan
sumber
.pop(0)
O (n), membuat fungsi gabungan O (n ^ 2). Tapi ini cukup buatan, karena.pop(0)
bisa saja dengan mudah O (1).Ḣ
diimplementasikan sebagai.pop(0)
.Ruby, 167 byte
Algoritme gabungan jenis golf, yang memiliki kasus terburuk O
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]]
sumber
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.
sumber
$stdin.readlines
sudah lebih sedikit byte daripadaopen(ARGV[0]).readlines
, sama denganputs
lebihopen(ARGV[1],"w"){|f|f.puts
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 .