Algoritma pengurutan seperti ini:
Sementara daftar tidak diurutkan, ambil setengah dari semua item (hapus item dari daftar). Lanjutkan sampai daftar diurutkan atau hanya satu item yang tersisa (yang diurutkan secara default). Algoritma pengurutan ini dapat memberikan hasil yang berbeda berdasarkan implementasi.
Prosedur penghapusan item tergantung pada implementasi untuk memutuskan, tetapi daftar tersebut harus setengah dari sebelum setelah satu melewati prosedur penghapusan item. Algoritme Anda dapat memutuskan untuk menghapus bagian pertama atau daftar, bagian terakhir dari daftar, semua item ganjil, semua item genap, satu per satu hingga daftar sepanjang setengah, atau apa pun yang tidak disebutkan.
Daftar input dapat berisi jumlah item yang sewenang-wenang (dengan alasan, katakanlah hingga 1000 item), tidak hanya daftar 2 item yang dapat dibagi dengan sempurna. Anda harus menghapus (n + 1) / 2 atau (n-1) / 2 item jika daftar ini ganjil, baik hardcode atau diputuskan secara acak selama runtime. Putuskan sendiri: apa yang akan dilakukan Thanos jika alam semesta mengandung jumlah aneh makhluk hidup?
Daftar ini diurutkan jika tidak ada item yang lebih kecil dari item sebelumnya. Duplikat dapat terjadi pada input, dan dapat terjadi pada output.
Program Anda harus menggunakan array bilangan bulat (via stdin atau sebagai parameter, item individual atau parameter array), dan mengembalikan array yang diurutkan (atau mencetaknya ke stdout).
Contoh:
// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half
[1, 2, 4, 3, 5]
dapat memberikan hasil yang berbeda:
// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]
atau:
// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed
atau:
// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed
atau:
// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
[9, 1, 1, 1, 1]
. Algoritme saya sendiri gagal pada input iniJawaban:
R , 41 byte
Cobalah online!
sumber
is.unsorted
bukannyaany(...)
41 byte.Python 3 ,
384239 byteCobalah online!
-3 bytes
terima kasih kepada @ JoKing dan @Quuxplusonesumber
!= sorted(t)
harus terjadi> sorted(t)
.Python 2 , 39 byte
Cobalah online!
sumber
Brachylog (v2), 6 byte
Cobalah online!
Ini adalah pengiriman fungsi. Input dari kiri, output ke kanan, seperti biasa. (TIO link menggunakan argumen baris perintah yang secara otomatis membungkus fungsi menjadi program lengkap, sehingga Anda dapat melihatnya beraksi.)
Penjelasan
Putaran bonus
Cobalah online!
Snap itu dimaksudkan untuk menjadi acak, bukan? Berikut adalah versi program yang memilih elemen yang bertahan secara acak (sambil memastikan bahwa setengahnya bertahan di setiap putaran).
Ini akan lebih pendek jika kita dapat menyusun ulang elemen, tetapi mengapa algoritma pengurutan ingin melakukan itu ?
sumber
Perl 6 , 30 byte
Cobalah online!
Fungsi rekursif yang menghapus paruh kedua daftar sampai daftar diurutkan.
Penjelasan:
sumber
C # (Visual C # Interactive Compiler) , 76 byte
Cobalah online!
sumber
Java 10,
10697 byte-9 byte terima kasih kepada @ OlivierGrégoire .
Cobalah online.
Penjelasan:
sumber
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}
lebih pendek menggunakan stream, tapi saya belum bisa menemukan cara untuk menghindarijava.lang.IllegalStateException: stream has already been operated upon or closed
kesalahan setelah mengembalikan aliranreduce
operasi terminal yang menutup aliran. Anda tidak akan pernah bisa meneleponreduce
dua kali pada aliran yang sama. Anda dapat membuat aliran baru.Bahasa Wolfram (Mathematica) , 30 byte
Cobalah online!
@ Doorknob menyimpan 12 byte
sumber
x[[;;;;2]]
).OrderedQ
, tetapi tidak bisa membuatnya bekerjaOrderedQ
pendekatan pertama saya (lihat suntingan)JavaScript (ES6),
4948 byteDisimpan 1 byte berkat @tsh
Menghapus setiap elemen ke-2.
Cobalah online!
sumber
p++&1
->a^=1
Ruby , 37 byte
Cobalah online!
sumber
05AB1E ,
87 byte-1 byte terima kasih kepada @Emigna .
Cobalah secara online atau verifikasi beberapa kasus uji lagi (atau verifikasi kasus uji tersebut dengan langkah-demi-langkah untuk setiap iterasi ).
7 byte alternatif oleh @Grimy :
Menghapus terakhirn2 n - 12
Cobalah secara online atau verifikasi beberapa kasus uji lagi (atau verifikasi kasus uji tersebut dengan langkah-demi-langkah untuk setiap iterasi ).
Penjelasan:
sumber
ι
alih-alih2ä
jika Anda beralih ke strategi elemen lainnya .ΔÐ{Ê>äн
TI-BASIC (TI-84),
47424544 byte-1 byte terima kasih kepada @SolomonUcko!
Daftar input ada di
Ans
.Keluaran dalam
Ans
dan dicetak secara implisit.Penjelasan:
Catatan: TI-BASIC adalah bahasa tokenized. Jumlah karakter tidak sama dengan jumlah byte.
sumber
not(min(L1=Ans
denganmax(L1≠Ans
untuk menyimpan satu byte.Jelly , 7 byte
Cobalah online!
sumber
Haskell ,
5755 byte (hanya berkat ASCII)Cobalah online!
Kode Asli:
Cobalah online!
Tidak Disatukan:
sumber
Oktaf , 49 byte
Cobalah online! Ini adalah perjalanan di mana lebih membosankan lebih baik. Perhatikan dua entri yang jauh lebih menarik di bawah ini:
50 byte
Cobalah online! Alih-alih solusi imperatif yang tidak menarik, kita dapat melakukan solusi rekursif, hanya dengan satu byte tambahan.
53 byte
Cobalah online! Ya. Fungsi anonim rekursif, berkat jawaban brilian @ ceilingcat pada pertanyaan kiat saya . Fungsi anonim yang mengembalikan fungsi anonim rekursif dengan mendefinisikan dirinya dalam daftar argumennya. Saya suka fungsi anonim. Mmmmm
sumber
MATL , 11 byte
Cobalah online!
Ini berfungsi dengan menghapus setiap item kedua.
Penjelasan
sumber
Japt , 10 byte
Cobalah
sumber
Java (JDK) , 102 byte
Sudah ada jawaban C #, jadi saya memutuskan untuk mencoba jawaban Java.
Cobalah online!
sumber
Crystal , 58 byte
Dengan
Array#sort
( 58 byte ):Cobalah online!
Tanpa
Array#sort
( 101 byte ):Cobalah online!
sumber
Sekam ,
65 byte1 byte disimpan berkat Zgarb
Cobalah online!
Penjelasan
sumber
Ċ2
alih-alih(←½
untuk menyimpan byte.Gaia ,
98 byteCobalah online!
Penjelasan:
sumber
Julia 1.0 , 30 byte
Cobalah online!
Mengambil setiap elemen kedua dari array jika tidak diurutkan.
sumber
-
untuk 20 byte. juga kita hampir selalu tidak menghitung karakter: | jadi alangkah baiknya jika itu dihapus dari headerC ++ (gcc) , 103 byte
Saya tidak dapat berkomentar, tetapi saya meningkatkan versi dari movatica dengan mengurangi menyertakan, dan menggunakan otomatis.
-2 Bytes: ceilingcat
-2 Bytes: ASCII-only
Cobalah online!
sumber
l.size()/2
?(n+1)/2
atau(n-1)/2
keduanya valid. hmm ....VDM-SL , 99 byte
Tidak pernah dikirimkan dalam vdm sebelumnya, jadi tidak pasti tentang aturan khusus bahasa. Jadi saya telah mengirimkan definisi fungsi yang mengambil a
seq of int
dan mengembalikan aseq of int
Program lengkap untuk dijalankan mungkin terlihat seperti ini:
sumber
Pyth, 10 byte
Cobalah online di sini . Ini menghapus paruh kedua pada setiap iterasi, membulatkan ke bawah. Untuk mengubahnya untuk menghapus babak pertama, pembulatan ke atas, ubah
h
kee
.sumber
hc
dengan%
. Ini juga memungkinkan Anda menghapus variabel lambda yang tertinggalZ
dan membiarkan Pyth mengisinya secara implisit, untuk total 2 byte yang disimpan.C ++ (gcc) ,
139137116 byte-2 byte byx ke ceilingcat, -21 byte thanx ke PeterZuger
Ubah ukuran vektor ke setengahnya hingga diurutkan.
Cobalah online!
sumber
include
sK (oK) ,
2220 byteLarutan:
Cobalah online!
Iterate atas input sampai diurutkan ... jika tidak diurutkan ambil n / 2 item pertama.
Suntingan:
sumber
(.5*#x)#x
->*2 0N#x
2 0N
tetapi menganggap itu akan lebih lama (tanpa pengujian), terima kasih!Julia 1.0 , 33 byte
Cobalah online!
sumber
Retina , 38 byte
Cobalah online! Membawa angka yang dipisahkan koma. Penjelasan:
Konversikan ke unary.
Ulangi saat daftar tidak diurutkan ...
... hapus setiap elemen genap.
Konversikan ke desimal.
sumber
C (gcc) , 66 byte
Hapus bagian kedua dari daftar setiap iterasi (
n/2+1
elemen jika panjangnya aneh).Cobalah online!
Mengambil input sebagai pointer ke awal array
int
diikuti oleh panjangnya. Output dengan mengembalikan panjang array yang baru (sortir di tempat).Versi tidak disatukan:
sumber
~i+n
alih-alihi<n-1