Sortir Daftar Integer

22

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

Michelfrancis Bustillos
sumber
8
Saya sangat terkejut jika ini bukan duplikat, tetapi saya tidak punya waktu untuk memeriksa. Bagaimanapun, "fungsi penyortiran bawaan" harus didefinisikan lebih baik. Bisakah Anda menggunakan fungsi yang mengindeks semua nilai? [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.
Stewie Griffin
1
@StewieGriffin Saya telah melihat banyak tantangan penyortiran, tetapi tidak ada yang berurusan dengan penyortiran hanya daftar integer dasar. Ada banyak tantangan yang lebih mudah untuk beberapa bahasa, dan jauh lebih sulit di yang lain.
Michelfrancis Bustillos
Ini adalah sangat mirip, namun memiliki O (nLog (N)) pembatasan.
Nathan Merrill
2
Sangat terkait erat dengan pertanyaan ini , tetapi karena beberapa jawaban di sini (mis. Pemfilteran Dennis 'memerlukan input sebagai bilangan bulat, saya tidak akan memilih untuk menutup sebagai dupe.
Peter Taylor
Relevan: youtube.com/user/AlgoRythmics/videos - Saluran Youtube yang mengajarkan algoritma penyortiran melalui tarian Hungaria!
sergiol

Jawaban:

23

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:

E[ß,Ž

Melakukan semacam seleksi . Menggunakan pengodean CP-1252 .

Cobalah online!

Adnan
sumber
6
Menerima ini sementara karena saya tidak melihat ada yang mendapat kurang dari 2.
Michelfrancis Bustillos
6
@MichelfrancisBustillos yah, jika mereka melakukannya, itu akan menjadi builtin, bukan?
Lemon Destructible
Saya baru saja melihat 05AB1E / Base satu menit yang lalu, dan kemudian saya melihat ini. Kebetulan?
facepalm42
17

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

ṂrṀf

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

ṂrṀf  Main link. Argument: A (list/comma-separated string)

Ṃ     Compute the minimum of A.
  Ṁ   Compute the maximum of A.
 r    Yield the inclusive range from the minimum to the maximum.
   f  Filter the range by presence in A.
Dennis
sumber
O ( sangat ). Menggunakan banyak jenis.
mbomb007
22
Jadi O. Sangat bermanfaat. Banyak macamnya. Menakjubkan! (Maaf, apa?)
Dennis
Saya tidak hebat dalam kompleksitas algoritma, apakah ini O (n!)?
FlipTack
2
@FlipTack Tidak juga saya. Mungkin sedikit lebih tinggi, karena ada n! panjang array n .
Dennis
1
Hanya memilih leksografis terkecil adalah O (n * n!) Karena masing-masing n! array harus dibandingkan secara berurutan, dan perbandingan leksografis adalah O (n). Generasi dapat dilakukan dalam O (n * n!) Juga jika dilakukan secara efisien jadi saya berani bertaruh algoritma ini hanya O (n * n!) Jika diterapkan dengan baik
PunPun1000
12

Python, 46 45 byte

lambda l:[l.pop(l.index(min(l)))for _ in 1*l]

Sortir seleksi sederhana.

orlp
sumber
4
l[:]bisa jadi1*l
feersum
9

Brachylog , 12 7 byte

p.'(s>)

Ini menggunakan jenis permutasi, yang jelas mengerikan, tapi hei ini lebih pendek dari Pyth!

Penjelasan

p.       Unifies the output with a permutation of the input
  '(  )  True if what's inside the parentheses cannot be proven, else backtrack and
         try with another permutation of the input.
    s    Take an ordered subset from the output
     >   True if the first element is bigger than the second (hence not sorted)
         We don't need to check that the subset is 2 elements long because > will be false
         for inputs that are not 2 elements long anyway
Fatalisasi
sumber
9

Haskell, 38 byte

h%t|(a,b)<-span(<h)t=a++h:b
foldr(%)[]

Fungsi biner %memasukkan elemen baru hke dalam daftar yang diurutkan tdengan mempartisi tke dalam awalan aelemen <hdan akhiran belemen >h, dan menempel di hantaranya.

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

f(h:t)|(a,b)<-span(<h)$f t=a++h:b
f x=x

Strategi lain untuk 41 byte:

f[]=[]
f l|x<-minimum l=x:f(filter(/=x)l)
Tidak
sumber
Jadi ini adalah en.wikipedia.org/wiki/Insertion_sort , dengan %sebagai penyisipan loop batin dan foldrmenerapkannya sebagai loop luar.
Peter Cordes
8

JavaScript (ES6), 51 byte

a=>a.map(_=>m=Math.min(...a.filter(e=>e>m)),m=-1/0)

Setiap loop menemukan jumlah terkecil yang belum ditemukan sejauh ini.

Neil
sumber
Menyebut ini [1,2,3,4,5,4,3,2,1]menghasilkan[1, 2, 3, 4, 5, Infinity, Infinity, Infinity, Infinity]
Benjamin Gruenbaum
@BenjaminGruenbaum "Input tidak akan mengandung duplikat."
Neil
Saya memiliki bytecount yang sama persis dengan pendekatan yang berbeda
Bálint
Sebenarnya, 1 byte lebih sedikit
Bálint
Algoritma ini adalah en.wikipedia.org/wiki/Selection_sort
Peter Cordes
8

Python 2, 34 byte

def f(s):m=min(s);print m;f(s-{m})

Mengambil input sebagai satu set, mencetak elemen-elemennya dalam urutan yang meningkat, mengakhiri dengan kesalahan.

Pengakhiran bersih dapat dilakukan dalam 41 byte:

def f(s):
 if s:m=min(s);print m;f(s-{m})

atau

l=input()
while l:m=min(l);print m;l-={m}

Input dapat diambil sebagai daftar untuk 39 byte, atau 38 byte dalam Python 3.5:

def f(l):m=min(l);print m;f(set(l)-{m})
def f(l):m=min(l);print(m);f({*l}-{m})
Tidak
sumber
Ini adalah en.wikipedia.org/wiki/Selection_sort , menggunakan m=min(s)/ s - (m)sebagai loop dalam untuk menemukan dan menghapus min dari elemen yang tidak disortir, dan rekursi sebagai bagian luar.
Peter Cordes
8

Haskell, 42 41 38 byte

f u=filter(`elem`u)[(minBound::Int)..]

Loop 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!

nimi
sumber
filterlebih pendek:f u=filter(`elem`u)[minimum u..maximum u]
xnor
Betapa kasarnya kekuatan! Tidak [minimum u..]berfungsi karena alasan tipe?
xnor
@ xnor: Saya kira begitu. Saat memanggil, katakanlah f [1,3,0], elemen default untuk mengetik Integeryang tidak terikat, jadi ..tidak pernah berakhir. Jika Anda harus menyebutnya seperti f ([1, 3, 0]::[Int])maka saya kira, jenis anotasi harus dimasukkan dalam jumlah byte.
nimi
Bagaimana cara mendeteksi elemen yang terjadi lebih dari satu kali?
feersum
1
@feersum: tidak, tetapi tantangannya mengatakan: "Input tidak akan berisi duplikat".
nimi
8

Oracle SQL 11.2, 205 byte

WITH s AS(SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))),v(p,f)AS(SELECT e,e FROM s UNION ALL SELECT p||','||e,e FROM v,s WHERE e+0>f)SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1);         

Tidak bermain golf

WITH 
s AS  -- Split the string using ',' as separator
(     -- ||'' cast the xml type to varchar
  SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))
),  
v(p,f) AS  -- Recursive view : p = sorted string, f last number added
(
  SELECT e,e FROM s -- use each number as seed
  UNION ALL         -- only add a number if it is > the last added
  SELECT p||','||e,e FROM v,s WHERE e+0>f  -- +0 is needed to compare int and not strings
)  
-- The valid string has the same length as the input
SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1)          

Adapun metode macam apa itu, saya tidak tahu, ORDER BYmemastikan saya melupakan mereka.

Jeto
sumber
Saya hampir tidak tahu SQL, tetapi dari komentar Anda, saya pikir Anda memilih min atau maks dari elemen yang tidak disortir yang tersisa, dan menambahkannya ke akhir daftar yang diurutkan. Itu menjadikan ini en.wikipedia.org/wiki/Selection_sort .
Peter Cordes
8

kode mesin x86-16 (BubbleSort int8_t), 20 19 byte

kode mesin x86-64 / 32 (JumpDownSort) 21 19 byte

Changelog:

  • Terima kasih kepada @ ped7g untuk ide lodsb/ cmp [si],al, dan menempatkan itu bersama dengan peningkatan / reset pointer yang telah saya lihat. Tidak perlu al/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 jgeke a jae). 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 − 1item terakhir ketika berjalan untuk yang nke-kali, sehingga penghitung lingkaran luar adalah batas atas untuk loop dalam.

Daftar NASM ( nasm -l /dev/stdout), atau sumber sederhana

 2 address  16-bit       bubblesort16_v2:
 3          machine      ;; inputs: pointer in ds:si,  size in in cx
 4          code         ;; requires: DF=0  (cld)
 5          bytes        ;; clobbers: al, cx=0
 6                       
 7 00000000 49               dec     cx          ; cx = max valid index.  (Inner loop stops 1 before cx, because it loads i and i+1).
 8                       .outer:                 ; do{
 9 00000001 51               push    cx          ;   cx = inner loop counter = i=max_unsorted_idx
10                       .inner:                 ;   do{
11 00000002 AC               lodsb               ;     al = *p++
12 00000003 3804             cmp     [si],al     ;     compare with *p (new one)
13 00000005 7D04             jge     .noswap
14 00000007 C144FF08         rol     word [si-1], 8    ; swap
15                       .noswap:
16 0000000B E2F5             loop    .inner      ;   } while(i < size);
17 0000000D 59               pop     cx          ;  cx = outer loop counter
18 0000000E 29CE             sub     si,cx       ;  reset pointer to start of array
19 00000010 E2EF             loop    .outer      ; } while(--size);
20 00000012 C3               ret

22 00000013  size = 0x13 = 19 bytes.

push / pop di cxsekitar loop dalam berarti berjalan dengan cx= outer_cx ke 0.

Perhatikan bahwa rol r/m16, imm8ini bukan instruksi 8086, itu ditambahkan kemudian (186 atau 286), tetapi ini tidak mencoba menjadi kode 8086, hanya x86 16-bit. Jika SSE4.1 phminposuwakan 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 jcxzuntuk 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], axuntuk 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, rsiarahkan ke satu melewati akhir wilayah yang disortir; lodsdmemajukannya 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 pada loopinstruksi bagian dalam , dan gunakan c(lanjutkan). Tekan kembali untuk mengulangi. (Perintah "display" membuat GDB untuk mencetak seluruh status array setiap kali kita menekan breakpoint).

xchgdengan mem memiliki lockawalan implisit yang membuat ini sangat lambat. Mungkin tentang urutan besarnya lebih lambat daripada pertukaran beban / toko yang efisien; xchg m,radalah 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 mana loopinstruksi 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) ).

 2 Address               ;; hybrib Bubble Selection sort
 3        machine         bubblyselectionsort_int32:   ;; working, 19 bytes.  Same size for int32 or int8
 4        code               ;; input: pointer in rsi, count in rcx
 5        bytes              ;; returns: eax = max
 6                       
 7                           ;dec  ecx           ; we avoid this by doing edi=esi *before* lodsb, so we do redundant compares
 8                                               ; This lets us (re)enter the inner loop even for 1 element remaining.
 9                       .outer:
10                           ; rsi pointing at the element that will receive min([rsi]..[rsi+rcx])
11 00000000 56               push   rsi
12 00000001 5F               pop    rdi
13                           ;mov    edi, esi     ; rdi = min-search pointer
14 00000002 AD               lodsd
16 00000003 51               push   rcx          ; rcx = inner counter
17                       .inner:                   ; do {
18                           ; rdi points at next element to check
19                           ; eax = candidate min
20 00000004 AF               scasd                 ; cmp eax, [rdi++]
21 00000005 7E03             jle  .notmin
22 00000007 8747FC           xchg   [rdi-4], eax   ; exchange with new min.
23                         .notmin:
24 0000000A E2F8             loop  .inner          ; } while(--inner);
26                           ; swap min-position with sorted position
27                           ; eax = min.  If it's not [rsi-4], then [rsi-4] was exchanged into the array somewhere
28 0000000C 8946FC           mov    [rsi-4], eax
29 0000000F 59               pop   rcx           ; rcx = outer loop counter = unsorted elements left
30 00000010 E2EE             loop  .outer        ; } while(--unsorted);
32 00000012 C3               ret

34 00000013 13           .size: db $ - bubblyselectionsort_int32
           0x13 = 19 bytes long

Ukuran kode yang sama untuk int8_t: penggunaan lodsb/ 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 ecxdengan 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, _startpanggilan yang keluar dengan status-keluar = elemen terbesar = 99, sehingga Anda dapat melihatnya berfungsi.

Peter Cordes
sumber
Mungkin ada ruang untuk memperbaiki kondisi loop dalam, tampaknya menggunakan banyak byte. Mungkin push / pop cxdan gunakan loopuntuk keduanya? Mungkin memutar ke arah lain, dari belakang ke depan array jadi kami menghitung indeks ke nol? (Dan kenaikan bxkarena bagian yang diurutkan adalah pada akhir Anda menuju).
Peter Cordes
1
Mendapatnya hingga 19B, tetapi dengan banyak perubahan, juga masukan regs (beberapa perubahan mungkin tidak diperlukan, tetapi karena saya bermain-main, mereka tetap di sana dari percobaan sebelumnya) ... masih berdasarkan pada pekerjaan Anda, jadi enggan memposting sebagai jawaban, Anda dapat memeriksanya di pastebin: pastebin.com/0VMzdUjj
Ped7g
@ Ped7g: Bagus! Saya dianggap sub si, cxsebagai bagian dari loop luar menggunakan pointer bukan pengindeksan, tapi saya belum memikirkan lodsb/ cmp [si], al. Saya telah mempertimbangkan lodsw/ dec si, atau lodsb/ xchg al,ahmasih mengaturcmp ah,al
Peter Cordes
@ Ped7g: oh, versi Anda memerlukan cld, atau saya kira kita bisa membuat bagian dari konvensi pemanggilan. AFAIK, setelah DFdibersihkan 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 bisa scasbalih-alih lodsbjika itu lebih nyaman.)
Peter Cordes
1
@ Ped7g: Saya tidak tahu tentang konvensi 16-bit, yang saya tahu adalah Anda tidak bisa selalu menganggap DF telah dihapus. Tapi saya pikir itu sebagian besar dalam konteks bootloader. Saya tidak pernah menjalankan apa pun yang saya tulis di DOS sungguhan. Saya menggunakan Atari Mega 4 STe (68000/68020), kemudian Linux (pada Pentium MMX), jadi saya berhasil menghindari x86 16-bit sepenuhnya sampai pertanyaan SO menabraknya.
Peter Cordes
6

C, 72 byte

i,j;a(int*l,int n){for(i=0;i=i?:--n;j>l[n]?l[i]=l[n],l[n]=j:0)j=l[--i];}

Bubblesort. Argumen pertama adalah pointer ke array, argumen kedua adalah panjang array. Bekerja dengan gcc.

mIllIbyte
sumber
Ini benar-benar membutuhkan versi yang tidak diklik untuk dapat dibaca; sangat sulit untuk melacak di mana operator ternary memulai / mengakhiri.
Peter Cordes
5

MATL , 11 10 byte

Y@t!d0>AY)

Pemeriksaan yang sangat tidak efisien dari semua permutasi input.

Cobalah secara Online!

Penjelasan

        % Implicitly grab input array
Y@      % Compute all permutations (each permutation as a row)
t       % Duplicate this matrix
!d      % Transpose and take the differences between the values
0>A     % Find the rows where all differences are > 0
Y)      % Return only the row where this is true
        % Implicitly display the result
Suever
sumber
5

Ruby, 40 byte

Sortir seleksi. Fungsi anonim; menganggap daftar itu sebagai argumen.

->a{r=[];r<<a.delete(a.min)while[]!=a;r}
Nilai Tinta
sumber
4

Python, 120 Bytes

def f(a):import time,threading;[threading.Thread(None,lambda b=b,c=min(a):print(time.sleep(b-c)or b)).start()for b in a]

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.

Nama Pengguna yang Disensor
sumber
Posting pertama yang bagus! Dan nama pengguna yang bagus. : P
R
4

MIPS, 68 byte

Saya menulis implementasi semacam bubble sederhana yang tidak dioptimalkan beberapa saat yang lalu. Hitungan byte dimulai pada loopdan berakhir pada li $v0, 10, dengan asumsi bahwa alamat daftar dan panjang daftar sudah ada dalam memori.

 Address    Code        Basic                     Source

0x00400000  0x3c011001  lui $1,4097           5    main:   la      $s0, list       # List address
0x00400004  0x34300000  ori $16,$1,0               
0x00400008  0x2411000a  addiu $17,$0,10       6            li      $s1, 10         # List length
0x0040000c  0x24080000  addiu $8,$0,0         8    loop:   li      $t0, 0          # swapped
0x00400010  0x24090001  addiu $9,$0,1         9            li      $t1, 1          # for loop "i"
0x00400014  0x1131000b  beq $9,$17,11         11   for:    beq     $t1, $s1, fend  # break if i==length
0x00400018  0x00095080  sll $10,$9,2          13           sll     $t2, $t1, 2     # Temp index, multiply by 4
0x0040001c  0x01505020  add $10,$10,$16       14           add     $t2, $t2, $s0   # Combined address
0x00400020  0x8d4b0000  lw $11,0($10)         15           lw      $t3, 0($t2)     # list[i]
0x00400024  0x8d4cfffc  lw $12,-4($10)        16           lw      $t4, -4($t2)    # list[i-1]
0x00400028  0x21290001  addi $9,$9,1          18           addi    $t1, $t1, 1     # i++
0x0040002c  0x016c082a  slt $1,$11,$12        20           ble     $t4, $t3, for   # if list[i-1] > list[i]
0x00400030  0x1020fff8  beq $1,$0,-8               
0x00400034  0xad4bfffc  sw $11,-4($10)        21           sw      $t3, -4($t2)    # swap and store
0x00400038  0xad4c0000  sw $12,0($10)         22           sw      $t4, 0($t2)     
0x0040003c  0x24080001  addiu $8,$0,1         23           li      $t0, 1          # swapped=true
0x00400040  0x08100005  j 0x00400014          24           j       for
0x00400044  0x20010001  addi $1,$0,1          26   fend:   subi    $s1, $s1, 1     # length--
0x00400048  0x02218822  sub $17,$17,$1             
0x0040004c  0x1500ffef  bne $8,$0,-17         27           bnez    $t0, loop       # Repeat if swapped==true
0x00400050  0x2402000a  addiu $2,$0,10        29           li      $v0, 10        
0x00400054  0x0000000c  syscall               30           syscall

Sekarang saya menunggu untuk diledakkan dari air dengan x86 ...

qwr
sumber
1
Anda dapat meninggalkan swapped=truecek 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.
Peter Cordes
4

Awk, 66 byte

{b=$0;a[b]}m<b{m=b}n>b{n=b}END{for(i=n;i<=m;i++)if(i in a)print i}

Array dalam awk seperti kamus, bukan seperti array C. Indeks bisa tidak bersebelahan, dan mereka tumbuh (dan dibuat) sesuai kebutuhan. Jadi, kami membuat array auntuk 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 di a. bhanya untuk menghindari penggunaan berulang $0.

muru
sumber
4

Python 3, 91 62 47 byte

def f(z):
 while z:m=min(z);z.remove(m);yield m

Terima kasih kepada wnnmaw dan Seeq untuk bantuan golf.

Argumen z harus berupa daftar. Ini adalah varian dari jenis seleksi.

Saya tidak yakin bagaimana minmenghadapi built-in sorting functions, karena saya tidak yakin bagaimana Python mengimplementasikan min. Semoga solusi ini tetap oke. Setiap saran golf dalam komentar atau obrolan PPCG dipersilakan.

Sherlock9
sumber
Pastikan untuk menyatakan jenis penyortiran yang Anda gunakan.
Michelfrancis Bustillos
@MichelfrancisBustillos Sejujurnya saya lupa algoritma apa ini. Mungkin semacam seleksi?
Sherlock9
1
Hanya ingin tahu, mengapa tidak langsung mengambil daftar? Pertanyaannya memungkinkan untuk format input terbuka
wnnmaw
1
@wnnmaw Sial, saya menulis satu tetapi lupa mempostingnya. Terima kasih atas pengingatnya: D
Sherlock9
Hmm, mungkindef f(z):\nwhile z:m=min(z);z.remove(m);yield m
seequ
4

MATL , 11 byte

`t4#X<2#)tn

Cobalah online!

Ini diurutkan dengan prosedur berikut, yaitu O ( n 2 ):

  1. Ambil minimum array.
  2. Hapus nilai itu dari array, dan simpan untuk tampilan selanjutnya.
  3. Terapkan prosedur yang sama dengan sisa array, hingga menjadi kosong.
  4. Tampilkan semua angka sesuai urutan perolehannya.

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.

`        % Do...while loop
  t      %   Duplicate. Implicitly take input in the first iteration
  4#X<   %   Compute index of mininum of the array
  2#)    %   Push the minimum, and then the array with remaining entries
  tn     %   Duplicate and push number of elements, to be used as loop condition
         % Implicitly end do...while loop
         % Implicitly display stack contents
Luis Mendo
sumber
3

Pyth - 15 13 11 10 byte

Dua byte disimpan berkat @Jakube.

Bogosort.

f!s>VTtT.p

Cobalah online di sini .

Saya tidak perlu hcuz kami dijamin tidak ada duplikat.

Maltysen
sumber
@ Jakube Saya merasa bodoh, terima kasih.
Maltysen
@Suever seperti yang saya katakan dalam jawaban saya, kami dijamin tidak ada duplikat sesuai OP.
Maltysen
Maaf soal itu! Melewatkan titik itu.
Suever
3

Serius, 6 byte

,;l@╨m

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:

,;l@╨m
,;l@    push len(input), input
    ╨m  minimum permutation

Serius, 25 byte (tidak bersaing)

Ini akan kompetitif jika bukan karena bug dalam perintah shuffle yang baru saja saya perbaiki.

,1WX╚;;pX@dXZ`i@-0<`MπYWX

Cobalah online! Ini mengimplementasikan algoritma penyortiran terbaik yang pernah ada: Bogosort !

Penjelasan:

,1WX╚;;pX@dXZ`i@-0<`MπYWX
,                          get input
 1W                    WX  do-while:
   X                         discard
    ╚                        shuffle
     ;;                      dupe twice
       pX@dX                 remove first element of first dupe and last element of second dupe
            Z                zip
             `i@-0<`MπY      test if all differences are positive (if any are not, the list is not sorted), negate (1 if not sorted else 0)
Mego
sumber
3

MATL, 17 16 byte

Disimpan satu byte dengan membuat null array berkat @LuisMendo

vTbtX<-QI$(f8M+q

Semacam ember. Jangan coba dengan rentang lebih dari 2 31 -1.

Cobalah online!

Penjelasan

v                  % push an empty array
 T                 % push 1
  b                % bubble the input array up to the top of the stack
   t               % duplicate it
    X<             % find the minimum
      -            % subtract min from input array
       Q           % and increment to adjust for 1-based indexing
        I$(        % resulting array used as indices of empty array 
                   % (the [] way up at the top) that are assigned 1 (from T)
           f       % find the nonzero indices
            8M     % magically retrieve the 4th previous function input :/
                     (aka, the min input array value)
              +    % add it to the indices
               q   % and decrement

TIL:

  • Anda dapat menginisialisasi array kosong di MATL menggunakan []dan menumbuhkannya, seperti di MATLAB
  • Cara menggunakan (untuk pengindeksan tugas
  • Cara menggunakan Mclipboard otomatis

Hari baru, TIL baru:

  • vertcat ajaib menciptakan array kosong ketika tidak ada di stack untuk menyatukan
gelas kimia
sumber
Tambahkan ke TIL Anda: inisial [] dapat diganti dengan v. Ini karena jumlah input default vadalah jumlah elemen dalam stack
Luis Mendo
@LuisMendo Sooo ... jika ada satu array di stack ...? Investigasi.
gelas kimia
Maka itu tidak melakukan apa-apa. Anggap sajavertcat(STACK{:})
Luis Mendo
3

R, 68 Bytes

Mengambil input idan output oyang merupakan daftar yang diurutkan.

o<-i
for(j in 1:length(i)){
x<-(i-min(i))==0
o[j]<-i[x]
i<-i[!x]
}
o

Penjelasan:

o<-i                      # Defines output as o
 for(j in 1:length(i)){   # Initializes loop for length of input
  x<-(i-min(i))==0        # Generates logical vector by finding the value 0 
                          # of input less the minimum of input. 
   o[j]<-i[x]             # Puts the smallest value at position j
    i<-i[!x]              # Removes the smallest value from input
      }                   # Ends loop
       o                  # Returns sorted list

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.

Forgottenscience
sumber
3

Java 8, 112 92 byte

Berikut ini jenis seleksi lainnya. Inputnya adalah aList t bilangan bulat dan output yang diurutkan dicetak ke standar keluar.

t->{for(;0<t.size();System.out.println(t.remove(t.indexOf(java.util.Collections.min(t)))));}

Memperbarui

  • -20 [16-08-21] Menggunakan lambda
Buah Nonlinier
sumber
Hai Nonlinear, dan selamat datang di PPCG!
isaacg
Selamat Datang di Programming Puzzles & Code Golf! Tampaknya kode Anda mengasumsikan ada variabel 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!
Alex A.
Terima kasih atas sumber dayanya! Saya mengubah jawaban saya menjadi fungsi dan memasukkan impor.
NonlinearFruit
2

Retina, 95

Jenis gelembung yang dimodifikasi. Saya menduga ada banyak cara yang lebih baik untuk melakukan ini, bahkan tanpa retina sortin.

-\d+
$*n
\d+
$*11
+`(1+) (n+)
$2 $1
+`\b(n+) (\1n+)|(1+)(1+) \3\b
$2$3 $1$3$4
1(1*)
$.1
n+
-$.&
  • Tahap 1 - convert -ve integer menjadi unary dengan nsebagai digit; jatuhkan- tanda tandanya.
  • Tahap 2 - konversi + ve dan nol integer ke unary dengan 1sebagai digit; tambahkan 1masing-masing, sehingga nol diwakili oleh 1.
  • Tahap 3 - Pindahkan semua langkah ke depan.
  • Tahap 4 - Sortir: pindahkan all -ves dengan magnitudo terbesar (mis. Angka terkecil) di depan -ve yang lebih tinggi. Gerakkan + ves lebih kecil dari + ves lebih besar.
  • Tahap 5 - Hapus 1 dari, dan ubah + ve kembali ke desimal.
  • Tahap 6 - konversi -ve unaries kembali ke desimal, termasuk tanda.

Cobalah online.

Trauma Digital
sumber
@ LeakyNun Itu tidak mengurutkan elemen terakhir dalam daftar.
mbomb007
@ mbomb007 benar, sudahlah.
Leaky Nun
2

Ruby, 22 byte

Sebuah cepat permutasi semacam. Berjalan dalam ruang dan waktu O (n!).

->a{a.permutation.min}
MegaTom
sumber
2

Clojure, 73 35 byte

Bogosort :)

#(if(apply < %)%(recur(shuffle %)))

Versi sebelumnya:

#(reduce(fn[r i](let[[a b](split-with(partial > i)r)](concat a[i]b)))[]%)

Mengurangi ke daftar yang diurutkan rdengan membaginya menjadi bagian "lebih kecil dari saya" dan "lebih besar dari saya". Saya kira ini adalah jenis penyisipan .

NikoNyrh
sumber
Bagus! Saya tidak tahu Anda bisa recurmenggunakan fungsi anonim. Juga tidak tahu shuffle.
Matias Bjarland
2

Ruby, 26 24 byte

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

->l{l.map{l-l-=[l.min]}}

contoh:

->l{l.map{l-l-=[l.min]}}[[2,4,3,1]]
=> [[1], [2], [3], [4]]
GB
sumber
2

Java 7, 106 104 byte

void a(int[]a){for(int b=a.length-1,d=0,c=0,e;d<b*b;c=++d%b)if(a[c]>a[c+1]){e=a[c];a[c++]=a[c];a[c]=e;}}

Ini 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!

Menyodok
sumber
2

Ruby, 22 byte

->a{[*a.min..a.max]&a}

Membangun array di luar rentang antara elemen minimum dan maksimum dari array input. Mengembalikan persimpangan antara dua array.

dkudriavtsev
sumber
Saya kira itu semacam en.wikipedia.org/wiki/Counting_sort .
Peter Cordes
@PeterCordes Itulah intinya
dkudriavtsev
Pertanyaannya meminta Anda untuk menggambarkan jenisnya, jadi saya pikir berguna untuk menautkan ke algoritma yang terkenal serta hanya menjelaskan apa yang sebenarnya dilakukan.
Peter Cordes
Benar. Terima kasih @PeterCordes
dkudriavtsev