Tantangan
Cukup sederhana kok, urutkan daftar angka.
Detail
Anda harus mengurutkan daftar angka dalam urutan menaik, tanpa menggunakan fungsi penyortiran bawaan / perpustakaan / dll (yaitu list.sort()
dalam Python).
Input / output dapat dilakukan dengan metode apa pun yang Anda pilih, asalkan itu dapat dibaca manusia.
Celah standar tidak diizinkan seperti biasa.
Kode terpendek dalam byte menang.
Anda harus menjelaskan / mendaftar metode pengurutan apa yang Anda gunakan (Bubble, Insertion, Selection, dll.)
Input tidak akan berisi duplikat.
Contoh Input / Output
Memasukkan: 99,-2,53,4,67,55,23,43,88,-22,36,45
Keluaran: -22,-2,4,23,36,43,45,53,55,67,88,99
Catatan: Kebalikan dari Sort a List of Numbers
[7 2 4 1] -> [4 2 3 1]
. Juga, dapatkah daftar CSV berada di dalam kurung? Juga, format input spesifik sangat cocok untuk beberapa bahasa, dan buruk untuk yang lain. Ini membuat input mem-parsing bagian besar untuk beberapa pengiriman, dan tidak perlu untuk yang lain.Jawaban:
05AB1E , 2 byte
Kode:
Algoritma yang sama dengan jawaban Jelly . Menghitung semua permutasi dari input dan muncul yang terkecil.
Cobalah online!
Metode yang lebih efisien adalah:
Melakukan semacam seleksi . Menggunakan pengodean CP-1252 .
Cobalah online!
sumber
Jelly, 3 byte
Ini menghasilkan semua permutasi dari daftar input, kemudian memilih permutasi terkecil secara leksografis. Sangat efisien.
Kredit untuk @Adnan yang memiliki ide yang sama secara mandiri.
Cobalah online!
Jelly, 4 byte
Ini membangun rentang dari minimum daftar hingga maksimum daftar, lalu membuang elemen rentang yang tidak ada dalam daftar asli. Ini secara teknis semacam ember , dengan ember yang sangat kecil. Saya tidak mengetahui nama untuk varian spesifik ini.
Cobalah online!
Bagaimana itu bekerja
sumber
Python,
4645 byteSortir seleksi sederhana.
sumber
l[:]
bisa jadi1*l
Brachylog ,
127 byteIni menggunakan jenis permutasi, yang jelas mengerikan, tapi hei ini lebih pendek dari Pyth!
Penjelasan
sumber
Haskell, 38 byte
Fungsi biner
%
memasukkan elemen baruh
ke dalam daftar yang diurutkant
dengan mempartisit
ke dalam awalana
elemen<h
dan akhiranb
elemen>h
, dan menempel dih
antaranya.Operasi
foldr(%)[]
kemudian membangun daftar diurutkan dari kosong dengan memasukkan elemen berulang kali dari daftar input.Ini satu byte lebih pendek dari implementasi rekursif langsung
Strategi lain untuk 41 byte:
sumber
%
sebagai penyisipan loop batin danfoldr
menerapkannya sebagai loop luar.JavaScript (ES6), 51 byte
Setiap loop menemukan jumlah terkecil yang belum ditemukan sejauh ini.
sumber
[1,2,3,4,5,4,3,2,1]
menghasilkan[1, 2, 3, 4, 5, Infinity, Infinity, Infinity, Infinity]
Python 2, 34 byte
Mengambil input sebagai satu set, mencetak elemen-elemennya dalam urutan yang meningkat, mengakhiri dengan kesalahan.
Pengakhiran bersih dapat dilakukan dalam 41 byte:
atau
Input dapat diambil sebagai daftar untuk 39 byte, atau 38 byte dalam Python 3.5:
sumber
m=min(s)
/s - (m)
sebagai loop dalam untuk menemukan dan menghapus min dari elemen yang tidak disortir, dan rekursi sebagai bagian luar.Haskell,
424138 byteLoop melalui semua bilangan bulat (ditandatangani 64bit, di mesin saya) dan simpan yang ada di dalamnya
u
. Tentu saja itu tidak selesai dalam waktu yang wajar.Versi sebelumnya diulang
[minimum u..maximum u]
yang memiliki waktu berjalan terburuk yang sama.Sunting: @xnatau disimpan satu byte. Terima kasih!
sumber
filter
lebih pendek:f u=filter(`elem`u)[minimum u..maximum u]
[minimum u..]
berfungsi karena alasan tipe?f [1,3,0]
, elemen default untuk mengetikInteger
yang tidak terikat, jadi..
tidak pernah berakhir. Jika Anda harus menyebutnya sepertif ([1, 3, 0]::[Int])
maka saya kira, jenis anotasi harus dimasukkan dalam jumlah byte.Oracle SQL 11.2, 205 byte
Tidak bermain golf
Adapun metode macam apa itu, saya tidak tahu,
ORDER BY
memastikan saya melupakan mereka.sumber
kode mesin x86-16 (BubbleSort int8_t),
2019 bytekode mesin x86-64 / 32 (JumpDownSort)
2119 byteChangelog:
Terima kasih kepada @ ped7g untuk ide
lodsb
/cmp [si],al
, dan menempatkan itu bersama dengan peningkatan / reset pointer yang telah saya lihat. Tidak perlual
/ah
mari kita gunakan kode yang hampir sama untuk bilangan bulat yang lebih besar.Algoritma baru (tetapi terkait), banyak perubahan implementasi: Bubbly SelectionSort memungkinkan implementasi x86-64 yang lebih kecil untuk byte atau kata-kata; impas pada x86-16 (byte atau kata-kata). Juga hindari bug pada ukuran = 1 yang dimiliki BubbleSort saya. Lihat di bawah.
Ternyata Sortasi Bubbly Seleksi saya dengan swap setiap kali Anda menemukan min baru sudah merupakan algoritma yang dikenal, JumpDown Sort. Disebutkan dalam Bubble Sort: An Archaeological Algorithmic Analysis (yaitu bagaimana Bubble Sort menjadi populer meskipun mengisap).
Mengurutkan bilangan bulat bertanda 8-bit di tempat . (Unsigned adalah ukuran kode yang sama, cukup ubah
jge
ke ajae
). Duplikat bukan masalah. Kami bertukar menggunakan 16-bit rotate oleh 8 (dengan tujuan memori).Bubble Sort menyebalkan untuk kinerja , tetapi saya telah membaca bahwa itu salah satu yang terkecil untuk diterapkan dalam kode mesin. Ini tampaknya benar terutama ketika ada trik khusus untuk bertukar elemen yang berdekatan. Ini adalah satu-satunya keuntungan, tetapi kadang-kadang (dalam sistem embedded kehidupan nyata) itu cukup keuntungan untuk menggunakannya untuk daftar yang sangat singkat.
Saya menghilangkan penghentian awal tanpa swap . Saya menggunakan loop BubbleSort Wikipedia "yang dioptimalkan" yang menghindari melihat
n − 1
item terakhir ketika berjalan untuk yangn
ke-kali, sehingga penghitung lingkaran luar adalah batas atas untuk loop dalam.Daftar NASM (
nasm -l /dev/stdout
), atau sumber sederhanapush / pop di
cx
sekitar loop dalam berarti berjalan dengancx
= outer_cx ke 0.Perhatikan bahwa
rol r/m16, imm8
ini bukan instruksi 8086, itu ditambahkan kemudian (186 atau 286), tetapi ini tidak mencoba menjadi kode 8086, hanya x86 16-bit. Jika SSE4.1phminposuw
akan membantu, saya akan menggunakannya.Versi 32-bit ini (masih beroperasi pada bilangan bulat 8-bit tetapi dengan pointer / penghitung 32-bit) adalah 20 byte (awalan ukuran operan aktif
rol word [esi-1], 8
)Bug: size = 1 diperlakukan sebagai size = 65536, karena tidak ada yang menghentikan kita memasuki bagian luar do / while dengan cx = 0. (Anda biasanya menggunakan
jcxz
untuk itu.) Tapi untungnya JumpDown Sort 19-byte adalah 19 byte dan tidak memiliki masalah itu.Versi asli x86-16 20 byte (tanpa ide Ped7g). Dihapus untuk menghemat ruang, lihat riwayat edit untuknya dengan deskripsi.
Performa
Penyimpanan / pengisian ulang yang tumpang tindih sebagian (dalam rotasi tujuan-memori) menyebabkan kios penerusan toko pada CPU x86 modern (kecuali Atom yang dipesan). Ketika nilai tinggi menggelembung ke atas, latensi tambahan ini adalah bagian dari rantai ketergantungan yang digerakkan oleh loop. Simpan / muat ulang sucks di tempat pertama (seperti latensi 5-store-forwarding di Haswell), tetapi warung penerusan membuatnya lebih seperti 13 siklus. Eksekusi out-of-order akan mengalami kesulitan menyembunyikan ini.
Lihat juga: Stack Overflow: bubble sort untuk menyortir string untuk versi ini dengan implementasi yang sama, tetapi dengan awal ketika tidak diperlukan swap. Menggunakan
xchg al, ah
/mov [si], ax
untuk bertukar, yang 1 byte lebih panjang dan menyebabkan kios parsial-register pada beberapa CPU. (Tapi mungkin masih lebih baik daripada memori-dst rotate, yang perlu memuat nilainya lagi). Komentar saya ada beberapa saran ...Sortir JumpDown x86-64 / x86-32, 19 byte (macam int32_t)
Dipanggil dari C menggunakan konvensi pemanggilan Sistem V x86-64 sebagai
int bubblyselectionsort_int32(int dummy, int *array, int dummy, unsigned long size);
(nilai balik = maks (array [])).Ini adalah https://en.wikipedia.org/wiki/Selection_sort , tetapi alih-alih mengingat posisi elemen min, tukar kandidat saat ini ke dalam array . Setelah Anda menemukan min (unsorted_region), simpan ke akhir wilayah yang disortir, seperti Urut Pilihan normal. Ini menumbuhkan wilayah yang diurutkan berdasarkan satu. (Dalam kode,
rsi
arahkan ke satu melewati akhir wilayah yang disortir;lodsd
memajukannya danmov [rsi-4], eax
menyimpan min kembali ke dalamnya.)Nama Jump Down Sort digunakan dalam Bubble Sort: An Archaeological Algorithmic Analysis . Saya kira jenis saya benar-benar semacam Jump Up, karena elemen-elemen tinggi melompat ke atas, meninggalkan bagian bawah diurutkan, bukan akhir.
Desain pertukaran ini mengarah ke bagian array yang tidak disortir dan berakhir dalam urutan sebagian besar terbalik, yang mengarah ke banyak swap di kemudian hari. (Karena Anda mulai dengan kandidat besar, dan terus melihat kandidat yang lebih rendah dan lebih rendah, sehingga Anda terus bertukar.) Saya menyebutnya "ceria" meskipun itu memindahkan elemen ke arah yang lain. Cara elemen bergerak juga sedikit seperti penyisipan mundur jenis. Untuk melihatnya beraksi, gunakan GDB
display (int[12])buf
, atur breakpoint padaloop
instruksi bagian dalam , dan gunakanc
(lanjutkan). Tekan kembali untuk mengulangi. (Perintah "display" membuat GDB untuk mencetak seluruh status array setiap kali kita menekan breakpoint).xchg
dengan mem memilikilock
awalan implisit yang membuat ini sangat lambat. Mungkin tentang urutan besarnya lebih lambat daripada pertukaran beban / toko yang efisien;xchg m,r
adalah satu per 23c throughput pada Skylake, tetapi memuat / menyimpan / mov dengan reg tmp untuk swap (reg, mem) yang efisien dapat menggeser satu elemen per jam. Ini mungkin rasio yang lebih buruk pada CPU AMD di manaloop
instruksi cepat dan tidak akan bottleneck loop dalam sebanyak, tetapi cabang merindukan masih akan menjadi hambatan besar karena swap adalah umum (dan menjadi lebih umum ketika daerah yang tidak disortir menjadi lebih kecil) ).Ukuran kode yang sama untuk
int8_t
: penggunaanlodsb
/scasb
,AL
, dan mengubah[rsi/rdi-4]
ke-1
. Kode mesin yang sama berfungsi dalam mode 32-bit untuk elemen 8/32-bit. Mode 16-bit untuk elemen 8/16-bit perlu dibangun kembali dengan perubahan offset (dan mode pengalamatan 16-bit menggunakan pengkodean yang berbeda). Tapi masih 19 byte untuk semua.Ini menghindari awal
dec ecx
dengan membandingkan dengan elemen yang baru saja dimuat sebelum pindah. Pada iterasi terakhir dari loop luar, ia memuat elemen terakhir, memeriksa apakah itu kurang dari itu sendiri, kemudian dilakukan. Ini memungkinkannya bekerja dengan ukuran = 1, di mana BubbleSort saya gagal (memperlakukannya sebagai ukuran = 65536).Saya menguji versi ini (dalam GDB) menggunakan penelepon ini: Coba online! . Anda dapat menjalankannya di TIO, tetapi tentu saja tidak ada debugger atau pencetakan. Namun,
_start
panggilan yang keluar dengan status-keluar = elemen terbesar = 99, sehingga Anda dapat melihatnya berfungsi.sumber
cx
dan gunakanloop
untuk keduanya? Mungkin memutar ke arah lain, dari belakang ke depan array jadi kami menghitung indeks ke nol? (Dan kenaikanbx
karena bagian yang diurutkan adalah pada akhir Anda menuju).sub si, cx
sebagai bagian dari loop luar menggunakan pointer bukan pengindeksan, tapi saya belum memikirkanlodsb
/cmp [si], al
. Saya telah mempertimbangkanlodsw
/dec si
, ataulodsb
/xchg al,ah
masih mengaturcmp ah,al
cld
, atau saya kira kita bisa membuat bagian dari konvensi pemanggilan. AFAIK, setelahDF
dibersihkan bukan bagian standar dari konvensi panggilan 16-bit, hanya 32/64. Atau hanya karena Anda tidak dapat menganggapnya dalam bootloader? Tetapi dengan konvensi pemanggilan register kustom, ini merupakan fragmen kode sebanyak fungsi, jadi pastikan, mengapa tidak memerlukan DF = 0. (Dan jika kita mau, ES = DS sehingga kita bisascasb
alih-alihlodsb
jika itu lebih nyaman.)C, 72 byte
Bubblesort. Argumen pertama adalah pointer ke array, argumen kedua adalah panjang array. Bekerja dengan gcc.
sumber
MATL ,
1110 bytePemeriksaan yang sangat tidak efisien dari semua permutasi input.
Cobalah secara Online!
Penjelasan
sumber
Ruby, 40 byte
Sortir seleksi. Fungsi anonim; menganggap daftar itu sebagai argumen.
sumber
Python, 120 Bytes
Ini mungkin bukan jawaban yang terpendek tetapi saya merasa algoritma ini ada di sini. panggilan dengan daftar bilangan bulat, mereka akan dicetak dengan cara diurutkan ke stdout. Saya tidak akan mencobanya dengan jumlah yang terlalu besar.
sumber
MIPS, 68 byte
Saya menulis implementasi semacam bubble sederhana yang tidak dioptimalkan beberapa saat yang lalu. Hitungan byte dimulai pada
loop
dan berakhir padali $v0, 10
, dengan asumsi bahwa alamat daftar dan panjang daftar sudah ada dalam memori.Sekarang saya menunggu untuk diledakkan dari air dengan x86 ...
sumber
swapped=true
cek awal dan menghitung mundur berdasarkan ukuran array. Lihat versi 20 byte x86-16 saya yang menyortir integer 8-bit . Saya mungkin membuat versi x86 32 atau 64-bit yang normal yang menyortir bilangan bulat 32-bit pada beberapa titik, tetapi bilangan bulat 8-bit dalam mode 16-bit adalah semacam sweet spot untuk x86.Awk, 66 byte
Array dalam awk seperti kamus, bukan seperti array C. Indeks bisa tidak bersebelahan, dan mereka tumbuh (dan dibuat) sesuai kebutuhan. Jadi, kami membuat array
a
untuk input, dengan setiap baris menjadi kunci. Dan kami menyimpan nilai min dan maks. Lalu kami mengulang dari min ke max, dan mencetak semua kunci yang ada dia
.b
hanya untuk menghindari penggunaan berulang$0
.sumber
Python 3,
916247 byteTerima kasih kepada wnnmaw dan Seeq untuk bantuan golf.
Argumen
z
harus berupa daftar. Ini adalah varian dari jenis seleksi.Saya tidak yakin bagaimana
min
menghadapibuilt-in sorting functions
, karena saya tidak yakin bagaimana Python mengimplementasikanmin
. Semoga solusi ini tetap oke. Setiap saran golf dalam komentar atau obrolan PPCG dipersilakan.sumber
def f(z):\nwhile z:m=min(z);z.remove(m);yield m
MATL , 11 byte
Cobalah online!
Ini diurutkan dengan prosedur berikut, yaitu O ( n 2 ):
MATL berbasis stack. Array dengan nilai yang tersisa disimpan di bagian atas tumpukan. Nilai yang dihapus di bawah ini, secara berurutan. Di akhir program, semua nilai tersebut ditampilkan. Array di atas juga akan ditampilkan, tetapi karena kosong, tidak ditampilkan.
sumber
Pyth -
15131110 byteDua byte disimpan berkat @Jakube.
Bogosort.
Cobalah online di sini .
Saya tidak perlu
h
cuz kami dijamin tidak ada duplikat.sumber
Serius, 6 byte
Cobalah online!
Ini melakukan hal yang sama dengan banyak jawaban lain: menghasilkan semua permutasi, pilih minimum. Saya agak lupa bahwa ini akan berhasil ketika saya sedang mengerjakan solusi di bawah ini.
Penjelasan:
Serius, 25 byte (tidak bersaing)
Ini akan kompetitif jika bukan karena bug dalam perintah shuffle yang baru saja saya perbaiki.
Cobalah online! Ini mengimplementasikan algoritma penyortiran terbaik yang pernah ada: Bogosort !
Penjelasan:
sumber
MATL,
1716 byteDisimpan satu byte dengan membuat null array berkat @LuisMendo
Semacam ember. Jangan coba dengan rentang lebih dari 2 31 -1.
Cobalah online!
Penjelasan
TIL:
[]
dan menumbuhkannya, seperti di MATLAB(
untuk pengindeksan tugasM
clipboard otomatisHari baru, TIL baru:
vertcat
ajaib menciptakan array kosong ketika tidak ada di stack untuk menyatukansumber
[]
dapat diganti denganv
. Ini karena jumlah input defaultv
adalah jumlah elemen dalam stackvertcat(STACK{:})
Julia,
2827 byteCobalah online!
sumber
R, 68 Bytes
Mengambil input
i
dan outputo
yang merupakan daftar yang diurutkan.Penjelasan:
Menghindari permutasi berarti ia dapat mengurutkan daftar besar dengan relatif cepat. "Trik" adalah bahwa mengurangi nilai terkecil dari input meninggalkan 0 tunggal yang menentukan nilai terkecil dan posisi nilai terkecil.
sumber
Java 8,
11292 byteBerikut ini jenis seleksi lainnya. Inputnya adalah a
List t
bilangan bulat dan output yang diurutkan dicetak ke standar keluar.Memperbarui
sumber
t
, yang menjadikannya cuplikan; kami meminta pengiriman untuk menjadi program atau fungsi lengkap yang menggunakan format I / O standar kami . Kami juga mengharuskan impor untuk memperhitungkan faktor byte. Beri tahu saya jika Anda memiliki pertanyaan!Retina, 95
Jenis gelembung yang dimodifikasi. Saya menduga ada banyak cara yang lebih baik untuk melakukan ini, bahkan tanpa retina sortin.
n
sebagai digit; jatuhkan-
tanda tandanya.1
sebagai digit; tambahkan1
masing-masing, sehingga nol diwakili oleh1
.Cobalah online.
sumber
Ruby, 22 byte
Sebuah cepat permutasi semacam. Berjalan dalam ruang dan waktu O (n!).
sumber
Clojure,
7335 byteBogosort :)
Versi sebelumnya:
Mengurangi ke daftar yang diurutkan
r
dengan membaginya menjadi bagian "lebih kecil dari saya" dan "lebih besar dari saya". Saya kira ini adalah jenis penyisipan .sumber
recur
menggunakan fungsi anonim. Juga tidak tahushuffle
.Ruby,
2624 bytePilihan sortir, mirip dengan jawaban Value Ink, tetapi menggunakan pendekatan berbeda untuk golfiness yang lebih besar.
Menurut spesifikasi: "Input / output dapat dilakukan dalam metode apa pun yang Anda pilih, asalkan itu dapat dibaca manusia". Saya pikir ini cocok dengan deskripsi, output adalah array array dengan elemen tunggal.
contoh:
sumber
Java 7,
106104 byteIni semacam gelembung ole yang bagus. Parameter fungsi dimodifikasi di tempat jadi saya tidak perlu mengembalikan apa pun. Masih mencoba untuk memeras beberapa byte dari ini sehingga saya bisa mengalahkan java lambda yang diposting seseorang.
-1 byte terima kasih kepada Geobits untuk menunjukkan bahwa swapping beats normal xor'ing
-1 byte terima kasih kepada Leaky Nun karena menunjukkan bahwa saya dapat memindahkan semua deklarasi int ke for-loop
Cobalah online!
sumber
Ruby, 22 byte
Membangun array di luar rentang antara elemen minimum dan maksimum dari array input. Mengembalikan persimpangan antara dua array.
sumber