Buat fungsi atau program yang mengambil dua input:
- Daftar bilangan bulat yang harus diurutkan (kurang dari 20 elemen)
- Bilangan bulat positif
N
,, mengatakan berapa banyak perbandingan yang harus Anda ambil
Fungsi harus berhenti, dan mengeluarkan daftar bilangan bulat setelah N
perbandingan. Jika daftar sepenuhnya diurutkan sebelum N
perbandingan dibuat, maka daftar yang diurutkan harus dikeluarkan.
The Bubble sort algoritma terkenal, dan saya kira kebanyakan orang tahu itu. Kode Pseudo dan animasi berikut (keduanya dari artikel Wikipedia yang terhubung) harus memberikan perincian yang diperlukan:
procedure bubbleSort( A : list of sortable items )
n = length(A)
repeat
swapped = false
for i = 1 to n-1 inclusive do
/* if this pair is out of order */
if A[i-1] > A[i] then
/* swap them and remember something changed */
swap( A[i-1], A[i] )
swapped = true
end if
end for
until not swapped
end procedure
Animasi di bawah ini menunjukkan progres:
Contoh (diambil langsung dari artikel Wikipedia yang terhubung) menunjukkan langkah-langkah saat mengurutkan daftar ( 5 1 4 2 8 )
::
Pass Pertama
1: ( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ) // Here, algorithm compares the first two elements,
// and swaps since 5 > 1.
2: ( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ) // Swap since 5 > 4
3: ( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ) // Swap since 5 > 2
4: ( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ) // Now, since these elements are already in order
// (8 > 5), algorithm does not swap them.
Pass Kedua
5: ( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )
6: ( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ) // Swap since 4 > 2
7: ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
8: ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
Sekarang, array sudah diurutkan, tetapi algoritma tidak tahu apakah sudah selesai. Algoritme membutuhkan satu pass penuh tanpa swap apa pun untuk mengetahuinya.
Lulus Ketiga
9: ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
10:( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
11:( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
12:( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
Kasus uji:
Format: Number of comparisons (N): List after N comparisons
Input list:
5 1 4 2 8
Test cases:
1: 1 5 4 2 8
2: 1 4 5 2 8
3: 1 4 2 5 8
4: 1 4 2 5 8
5: 1 4 2 5 8
6: 1 2 4 5 8
10: 1 2 4 5 8
14: 1 2 4 5 8
Input list:
0: 15 18 -6 18 9 -7 -1 7 19 19 -5 20 19 5 15 -5 3 18 14 19
Test cases:
1: 15 18 -6 18 9 -7 -1 7 19 19 -5 20 19 5 15 -5 3 18 14 19
21: -6 15 18 9 -7 -1 7 18 19 -5 19 19 5 15 -5 3 18 14 19 20
41: -6 9 -7 15 -1 7 18 18 -5 19 19 5 15 -5 3 18 14 19 19 20
60: -6 -7 -1 9 7 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20
61: -6 -7 -1 7 9 15 18 -5 18 19 5 15 -5 3 18 14 19 19 19 20
81: -7 -6 -1 7 9 15 -5 18 18 5 15 -5 3 18 14 19 19 19 19 20
119: -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20
120: -7 -6 -1 -5 7 9 15 5 15 -5 3 18 14 18 18 19 19 19 19 20
121: -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20
122: -7 -6 -1 -5 7 9 5 15 15 -5 3 18 14 18 18 19 19 19 19 20
123: -7 -6 -1 -5 7 9 5 15 -5 15 3 18 14 18 18 19 19 19 19 20
201: -7 -6 -5 -1 -5 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20
221: -7 -6 -5 -5 -1 3 5 7 9 14 15 15 18 18 18 19 19 19 19 20
- Ya, algoritme semacam gelembung bawaan diizinkan.
- Tidak, Anda tidak dapat mengasumsikan hanya bilangan bulat positif, atau bilangan bulat unik.
- Penyortiran harus dalam urutan yang dijelaskan di atas. Anda tidak dapat memulai di akhir daftar
Jawaban:
Jelly , 25 byte
Berdasarkan jawaban saya di J.
Cobalah online!
Verifikasi jumlah perbandingan.
Penjelasan
Tautan pembantu mengubah daftar pada indeks
[i-1, i]
dengan mengurutkannya yang menghasilkan hasil yang sama dengan perbandingan jenis gelembung.sumber
JavaScript (ES6),
10282808680 bytePerbaikan bug dan 1 byte disimpan berkat @ edc65
Rekursi
mungkin tidakpasti bukanmungkin merupakan pendekatan terbaik, tapi saya bertahan dengan sebuah loop untuk saat ini.Cobalah:
Tampilkan cuplikan kode
sumber
f=(a,m,n=0,_,b=a[n+1])=>b+.5?m?f(a,m-1,n+1,a[n]>b?a[a[n+1]=a[n],n]=b:0):a:f(a,m,0)
.,0
1/b
alih-alihb+.5
memeriksaundefined
Haskell,
838281 byteContoh penggunaan:
[5,1,4,2,8] ! 5
->[1,4,2,5,8]
.Berfungsi
%
y
melacak elemen yang dikunjungi sejauh ini saat pass,x
adalah yang belum diperiksa.a
danb
adalah dua berikutnya, yaitu kandidat untuk bertukar. Jika kita mencapai akhir dari daftar, kita mulai dari awal:y%x = []%(y++x)
. Semua langkah disimpan dalam daftar di mana fungsi utama mengambiln
elemen th.Sunting: versi sebelumnya tidak berfungsi untuk daftar elemen tunggal, untungnya versi baru bahkan lebih pendek.
sumber
f=
sebelum baris kedua dari jawaban, kemudian tambahkan baris ketiga ke program yang berisimain=print(f [5,1,4,2,8] 5)
. Itu harus membuatnya runnable.Python 3,
7774 byte-3 byte terima kasih kepada @Maltysen (init
j
dalam deklarasi)Uji kasus di ideone
Menggunakan
sorted
untuk melakukan masing-masing operasi perbandingan dan swap, tetapi melakukan semacam gelembung.Set
j=0
(indeks kiri), kemudian melakukann
bandingkan dan bertukar item daftar yang berdekatan, ulangj
ke0
setiap kali jendela ini keluar dari batas.The
j*=j<len(l)-1
akan berkembang biakj
denganFalse
(yaitu0
) pada saat itu, sedangkan setiap kali lain itu akan kalikanj
denganTrue
(yaitu1
).(Ini juga akan berfungsi untuk daftar kosong.)
sumber
j
, Anda dapat menggunakan%
eval
di MATLAB karena tugas inline.PowerShell v2 +,
135129 byteBegitu. Banyak. Dolar
( Disimpan enam byte dengan menyadari bahwa tantangan ini tidak termasuk "gratis" optimasi melewatkan elemen terakhir (s) pada setiap lulus karena yang ini dijamin diurutkan, dan sebaliknya berjalan melalui lulus penuh setiap kali. Ini pindah
$a.count
kefor
lingkaran dan menghilangkan$z
variabel. )Jenis gelembung lurus, dengan satu tempat bagus, melakukan pertukaran dalam satu langkah -
$a[$_],$a[$_+1]=$a[$_+1],$a[$_]
Logika keluar ditangani melalui
if(!--$n){$a;exit}
Uji Kasus
(Array ditampilkan sebagai ruang-dipisahkan di sini karena Pemisah Bidang Output default untuk merangkaikan array adalah spasi. Stringisasi terjadi karena kita sedang menyatu dengan label
"$_ -> "
.)sumber
R,
132131112136 byteProgram menerima input sebagai berikut: pertama
N
, kemudian vektor itu sendiri. Misalnya, jika Anda mauv = [5 1 4 2 8]
dann = 1
, input yang masuk kescan
is1 5 1 4 2 8
. Jadi untuk menjalankan program ini, Anda menjalankan baris pertama , beri makan angka satu per satu di konsol , dan kemudian jalankan sisanya (ini adalah jawaban REPL).Kemudian kode berikut melakukan trik:
Uji:
Pembaruan: golf 1 byte karena Vlo .
sumber
Pyth,
3432 BytesTerjemahan dari jawaban Python Jonathan Allan's.
Coba di sini!
sumber
JavaScript (ES6),
828079 byteBerdasarkan jawaban asli @ ETHproduction. Sunting: Disimpan 2 byte berkat @JonathanAllan. Disimpan 1 byte berkat @ edc65.
sumber
J ,
6260 byteIni adalah kata kerja yang mengambil dua argumen: jumlah perbandingan pada LHS dan daftar bilangan bulat pada RHS. Pertama, periksa apakah panjang daftar jika lebih dari satu. Jika tidak, ia mengembalikan daftar yang tidak dimodifikasi, jika tidak beroperasi dengan melakukan perbandingan jumlah yang ditentukan sebelum mengembalikan hasilnya.
Pemakaian
Untuk kasus uji pertama, perintah ekstra digunakan untuk memformat beberapa input / output. Kasing uji kedua ditampilkan sebagai input / output tunggal.
Penjelasan
Sulit untuk menulis kode singkat dalam J yang menggunakan mutability, jadi alih-alih saya mengubah masalah menjadi mengurangi daftar pada serangkaian indeks. Saya pikir kode ini berantakan sehingga saya akan melakukan pekerjaan dari setiap frase, bukan masing-masing primitif. Bagian pertama meraih panjang daftar dan menghasilkan kisaran. Kemudian, operasikan pada setiap infiks ukuran 2 untuk meniru satu lintasan perbandingan.
Ini adalah indeks awal dari setiap perbandingan. Jika 7 perbandingan dilakukan, bentuk ulang untuk mendapatkan jumlah yang diinginkan. J mem-parsing kanan ke kiri, sehingga mengurangi kanan ke kiri, seperti flip-kanan. Tambahkan daftar awal dan balikkan.
Atau, kisaran [0, 7) dapat dibuat dan setiap nilai diambil modulo panjang daftar minus 1 untuk membuat rentang yang sama.
Bagian terakhir adalah kata kerja yang mengambil daftar pada RHS dan indeks pada LHS yang menandai indeks awal perbandingan. Pilih dua elemen mulai dari indeks itu, urutkan, dan pasang kembali ke dalam daftar dan kembalikan.
sumber
Matlab,
9391 byteMenghemat 11 byte dengan menghilangkan
if l(i)>l(i+1);l(i:i+1)=l([i+1,i])
, dan alih-alih hanya mengurutkan kedua elemen setiap kali. Berfungsi untuk daftar panjang 1. Bisa menghemat satu atau dua byte menggunakanm--
operator Oktaf , tapi itu tidak banyak.Menghemat dua byte lebih banyak dengan mengatur
n=numel(l)-1;
, karena dengan begitu saya bisa melakukanwhile n
alih - alihwhile n>1
, dani=mod(i,n)+1
bukannyai=mod(i,n-1)+1
.Sebagai catatan, jawaban ini ditulis berjam-jam setelah tantangan dibuat.
sumber
Groovy (101 Bytes)
SUNTING: Saya tidak perlu menulis penutupan swap saya sendiri, asyik ini sudah terpasang.
Coba di sini: https://groovyconsole.appspot.com/script/5104724189642752
Contoh Jejak Keluaran:
Implementasi Lama (122 Bytes)
Cobalah di sini: https://groovyconsole.appspot.com/script/6316871066320896
sumber
php,
148145 byteSaya tidak terlalu senang dengan struktur loop tetapi saya suka saklar daftar dan itu berfungsi jadi saya tetap mempostingnya. php7.1 akan memungkinkan saya untuk menyimpan setidaknya 4 byte.
Dengan pemformatan yang lebih bagus:
Sunting: Jörg Hülsermann mengingatkan saya untuk bergabung, bukannya meledak.
catatan: harus dalam file dengan nama file karakter tunggal.
sumber
Ruby,
5250 byteTunggu ... tidak ada Ruby?
sumber