Ya ... ada 59 (sekarang 60) pertanyaan yang diurutkan , tetapi tidak ada quicksort sederhana.
Itu harus diperbaiki.
Bagi mereka yang tidak terbiasa dengan quicksort , ini adalah rincian, milik Wikipedia-
- Pilih elemen, yang disebut pivot , dari array.
- Susun ulang array sehingga semua elemen dengan nilai lebih kecil dari pivot datang sebelum pivot, sementara semua elemen dengan nilai lebih besar dari pivot datang setelahnya (nilai yang sama dapat terjadi dengan cara lain). Setelah partisi ini, pivot berada di posisi terakhirnya. Ini disebut operasi partisi.
- Secara rekursif menerapkan langkah-langkah di atas untuk sub-array elemen dengan nilai lebih kecil dan secara terpisah ke sub-array elemen dengan nilai lebih besar.
Aturan
Aturannya sederhana:
- Terapkan quicksort numerik dalam bahasa pemrograman pilihan Anda.
- Pivot harus dipilih secara acak atau dengan median tiga (elemen 1, terakhir, dan tengah).
- Program Anda dapat berupa program atau fungsi yang lengkap.
- Anda bisa mendapatkan input menggunakan STDIN, argumen baris perintah, atau parameter fungsi. Jika menggunakan input string, input dipisahkan oleh ruang.
- Input mungkin mengandung nilai desimal dan negatif. Namun, tidak akan ada duplikat.
- Anda dapat output ke STDOUT atau dengan kembali dari fungsi.
- Tidak ada fungsi penyortiran bawaan (atau terkait penyortiran) atau celah standar.
- Daftar mungkin panjangnya sewenang-wenang.
Bonus # 1: Pada daftar atau sub-daftar panjang <= 5, gunakan jenis penyisipan untuk mempercepat sedikit. Hadiah: -15%.
Bonus # 2: Jika bahasa Anda mendukung konkurensi, urutkan daftar secara paralel. Jika Anda menggunakan jenis penyisipan pada sub-daftar, jenis penyisipan akhir tidak harus paralel. Dibangun di thread pool / penjadwalan thread diizinkan. Hadiah: -15%.
Catatan: Median tiga orang membingungkan beberapa orang, jadi inilah penjelasan, milik (lagi) Wikipedia:
memilih median elemen pertama, tengah, dan terakhir dari partisi untuk pivot
Mencetak gol
Ini adalah kode-golf . Skor dasar dalam byte. Jika Anda mendapat satu bonus, ambil diskon 15% dari angka itu. Jika Anda mendapat keduanya, ambil diskon 30%. Itu benar-benar terdengar seperti promosi dagang.
Ini bukan tentang menemukan jawaban terpendek secara keseluruhan, tetapi lebih pendek di setiap bahasa.
Dan sekarang, salinan cuplikan papan peringkat yang tidak tahu malu.
Papan Peringkat
Cuplikan Stack di bagian bawah posting ini menghasilkan katalog dari jawaban a) sebagai daftar solusi terpendek per bahasa dan b) sebagai leaderboard keseluruhan.
Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:
## Language Name, N bytes
di mana N adalah ukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:
## Perl, 43 + 2 (-p flag) = 45 bytes
Anda juga dapat membuat nama bahasa menjadi tautan yang kemudian akan muncul di cuplikan:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes
/* Configuration */
var QUESTION_ID = 62476; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 41505; // This should be the user ID of the challenge author.
/* App */
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;
function answersUrl(index) {
return "http://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function commentUrl(index, answers) {
return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}
function getAnswers() {
jQuery.ajax({
url: answersUrl(answer_page++),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
answers.push.apply(answers, data.items);
answers_hash = [];
answer_ids = [];
data.items.forEach(function(a) {
a.comments = [];
var id = +a.share_link.match(/\d+/);
answer_ids.push(id);
answers_hash[id] = a;
});
if (!data.has_more) more_answers = false;
comment_page = 1;
getComments();
}
});
}
function getComments() {
jQuery.ajax({
url: commentUrl(comment_page++, answer_ids),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
answers_hash[c.post_id].comments.push(c);
});
if (data.has_more) getComments();
else if (more_answers) getAnswers();
else process();
}
});
}
getAnswers();
var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+(?:.\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;
var OVERRIDE_REG = /^Override\s*header:\s*/i;
function getAuthorName(a) {
return a.owner.display_name;
}
function process() {
var valid = [];
answers.forEach(function(a) {
var body = a.body;
a.comments.forEach(function(c) {
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});
var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
link: a.share_link,
});
else console.log(body);
});
valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});
var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;
var answer = jQuery("#answer-template").html();
answer = answer.replace("{{PLACE}}", lastPlace + ".")
.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)
.replace("{{LINK}}", a.link);
answer = jQuery(answer);
jQuery("#answers").append(answer);
var lang = a.language;
lang = jQuery('<a>'+lang+'</a>').text();
languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
});
var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);
langs.sort(function (a, b) {
if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
return 0;
});
for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
.replace("{{LINK}}", lang.link);
language = jQuery(language);
jQuery("#languages").append(language);
}
}
body { text-align: left !important}
#answer-list {
padding: 10px;
width: 290px;
float: left;
}
#language-list {
padding: 10px;
width: 290px;
float: left;
}
table thead {
font-weight: bold;
}
table td {
padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
<h2>Shortest Solution by Language</h2>
<table class="language-list">
<thead>
<tr><td>Language</td><td>User</td><td>Score</td></tr>
</thead>
<tbody id="languages">
</tbody>
</table>
</div>
<div id="answer-list">
<h2>Leaderboard</h2>
<table class="answer-list">
<thead>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
</thead>
<tbody id="answers">
</tbody>
</table>
</div>
<table style="display: none">
<tbody id="answer-template">
<tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
<tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
Jawaban:
C ++,
440.3405388 byte518 byte - 15% bonus untuk jenis penyisipan = 440,3 byte477 byte - bonus 15% untuk jenis penyisipan = 405,45 byte474 byte - 15% bonus untuk jenis penyisipan = 402,9 byteTerima kasih kepada @Luke karena telah menghemat 3 byte (2 sungguh).
Terima kasih kepada @ Dúthomhas karena telah menghemat 18 (15 benar-benar) byte.
Perhatikan bahwa saya baru di sini dan ini adalah posting pertama saya.
Ini adalah file
.h
(header).Kode Terkompresi:
Kode Lengkap:
sumber
#include
.srand(time(NULL));
Anda masih akan mendapatkan nomor pseudo-acakrand()
.APL,
4942 byteIni menciptakan fungsi monadik rekursif tanpa nama yang menerima larik di sebelah kanan. Itu tidak memenuhi syarat untuk bonus.
Penjelasan:
Cobalah online
Memperbaiki masalah (dengan biaya 8 byte) berkat marinus dan menyimpan 7 byte berkat Thomas Kwa!
sumber
C ++ 17,
254199195 byteDengan spasi putih:
sumber
for (y : a)
jika tidak perlufor (auto y : a)
ataufor (int y : a)
. (Sebenarnya,clang++
menyebut ini ekstensi C ++ 1z , tapi sepertinya bukan C ++ 17? Saya tidak tahu dan sudah larut malam untuk mencarinya.)Pyth, 25 byte
Ini mendefinisikan fungsi
y
, yang mengambil daftar angka sebagai input.Cobalah online: Demonstrasi
Penjelasan
Pyth, 21 byte (mungkin tidak valid)
Saya menggunakan metode "grup-oleh", yang secara internal menggunakan semacam. Saya menggunakannya untuk membagi daftar asli menjadi tiga sublists (semua elemen lebih kecil dari pivot, pivot, dan semua elemen lebih besar dari pivot). Tanpa mengurutkan dalam "grup-oleh", itu bisa mengembalikan 3 daftar ini dalam urutan yang berbeda.
Seperti yang dikatakan, ini mungkin tidak valid. Meskipun demikian saya akan menyimpannya di sini, karena ini merupakan solusi yang menarik.
Cobalah online: Demonstrasi
Penjelasan
sumber
> <> (Ikan),
313309 byteSaya butuh waktu lama untuk menulis. Anda dapat mencobanya di sini , cukup masukkan daftar yang harus disortir ke dalam tumpukan awal, dipisahkan dengan koma, sebelum menjalankan program.
Bagaimana itu bekerja
Program ini mengambil elemen pertama, tengah dan terakhir dalam tumpukan awal dan menghitung median dari ketiganya.
Kemudian mengubah tumpukan ke:
[daftar 1] elemen [daftar 2]
di mana semua yang ada di daftar 1 lebih kecil atau sama dengan elemen dan semua yang ada di daftar 2 lebih besar.
Itu secara berulang mengulangi proses ini pada daftar 1 dan daftar 2 sampai seluruh daftar diurutkan.
sumber
CJam, 40 byte
Ini adalah fungsi bernama yang mengharapkan array pada stack dan mendorongnya sebagai balasan.
Cobalah online di juru bahasa CJam .
Kode di atas mengikuti spesifikasi sedekat mungkin. Jika tidak diperlukan, 12 byte dapat disimpan:
sumber
Python 3,
123, 122.Disimpan 1 byte berkat Aaron.
Ini adalah pertama kalinya saya benar-benar repot untuk menulis algoritma penyortiran. Sebenarnya ini sedikit lebih mudah dari yang saya kira.
Tidak Disatukan:
sumber
<=
perbandingan - ini tidak menjamin bahwap
itu di tempat yang tepat, Anda mungkin perlu mengubahnya ke ketidaksetaraan eksklusif, dan menambahkanp
di tengah secara independen (saya belum diuji / dapat dapat menguji kode).[2, 1, 3]
akan mematahkannya 1/3 dari waktu, seperti ketika memilih inden menjadi 2, itu akan memiliki daftar rendah menjadi[2, 1]
- Maaf saya tidak dapat menguji ini sendiri sekarang.Javascript (ES2015), 112
Penjelasan
sumber
Rubi,
8760 byteTidak Disatukan:
Uji:
sumber
Oktaf,
7675 byteVersi multi-baris:
sumber
Julia, 83 byte
Ini menciptakan fungsi rekursif
Q
yang menerima array dan mengembalikan array. Itu tidak kondisional menggunakan penyisipan, jadi tidak ada bonus yang berlaku.Tidak Disatukan:
Memperbaiki masalah dan menyimpan beberapa byte berkat Glen O!
sumber
f
ketika Anda pertama kali menggunakanfilter
, dan menggunakanendof
alih-alihlength
.Q(x)=endof(x)<2?x:(p=rand(x);[Q((f=filter)(i->i<p,x));p;Q(f(i->i>p,x))])
R, 78 byte
Ini menciptakan fungsi rekursif
Q
yang menerima vektor dan mengembalikan vektor. Ini tidak secara kondisional menerapkan penyisipan, jadi tidak ada bonusTidak Disatukan:
Cobalah online
Disimpan 4 byte berkat flodel!
sumber
K, 41 byte
AMBIL ITU, APL !!! Tidak melakukan bonus apa pun.
sumber
Haskell,
137136 byteVersi ungolfed ada di bawah ini, dengan variabel yang diperluas dan nama fungsi dan beberapa hasil antara ditambahkan:
Saya mengambil keuntungan dari kenyataan bahwa tidak ada duplikat untuk menggunakan dua perbandingan ketat. Saya harus memeriksa apakah
Data.List.partition
tidak membuat segalanya lebih pendek, bahkan mengingat saya harus menambahkan pernyataan impor. Saya tidak mengambil bonus jenis penyisipan karena saya anggapData.List.insert
sebagai fungsi terkait penyortiran - dengan demikian dilarang - dan jika tidak menggunakannya, menambahkan jenis penyisipan mendorong kode ke 246 byte, 209.1 dengan bonus, sehingga tidak layak.Sunting: Terima kasih kepada RobAu untuk saran mereka untuk membuat alias untuk digunakan
f=filter
. Ini mungkin menyimpan hanya satu byte tetapi semuanya membantu.sumber
f=filter
mungkin memotong beberapa byte.q$f(>n)l
danq$f(<n)l
panggilan?Tcl, 138 byte
Ini adalah quicksort yang sangat standar.
Pivot hanyalah elemen pertama dari setiap subarray (saya berpendapat bahwa ini adalah angka acak. Https://xkcd.com/221/ )
Ini tidak terlalu efisien dalam hal penggunaan memori, meskipun itu dapat diperbaiki beberapa dengan
tailcall
pada rekursi kedua dan kasus dasar n <1 elemen.Ini versi yang bisa dibaca:
Bekerja pada semua input dan mengizinkan duplikat. Oh, ini juga stabil . Anda dapat mengujinya dengan sesuatu yang sederhana, seperti:
Nikmati! :HAI)
sumber
foreach
olehlmap
JavaScript (ES6), 191
sumber
Ceylon (hanya JVM),
183170Tidak ada bonus yang berlaku.
Tampaknya tidak ada cara lintas platform untuk menghasilkan angka acak di Ceylon, jadi ini hanya JVM. (Pada akhirnya saya memiliki versi non-acak yang juga berfungsi di JS, dan lebih kecil.)
Ini mendefinisikan suatu fungsi yang mengambil versi float, dan mengembalikan versi yang diurutkan.
Jika (terhadap spesifikasi) entri rangkap dilewatkan, mereka akan disaring.
Ini adalah 183 byte:
import ceylon.math.float{r=random}{Float*}q({Float*}l){if(exists p=l.getFromFirst((r()*l.size).integer)){return q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))};}else{return[];}}
Kami dapat meningkatkan sedikit dengan menggunakan
if
ekspresi Ceylon 1.2 yang baru :Ini adalah 170 byte:
import ceylon.math.float{r=random}{Float*}q({Float*}l)=>if(exists p=l.getFromFirst((r()*l.size).integer))then q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))}else[];
Ini adalah versi non-acak:
Tanpa spasi, ini akan menjadi 107 byte:
{Float*}r({Float*}l)=>if(exists p=l.first)then r(l.filter((e)=>e<p)).chain{p,*r(l.filter((e)=>p<e))}else[];
sumber
AutoIt ,
320,45304,3 byteIni sangat cepat (untuk AutoIt). Memenuhi syarat untuk bonus semacam penyisipan. Akan menambahkan penjelasan setelah golf terakhir terjadi.
Masukan adalah
q(Array, StartingElement, EndingElement)
.Input + output uji acak:
sumber
Java, 346 byte
Kode Terkompresi:
Kode Lengkap:
sumber
Mathematica,
9390 byteTidak ada bonus, belum punya cara minimal untuk melakukan penyisipan. Ketika saya sedang belajar C ++ baru-baru ini, saya melakukan perbandingan berbagai algoritma pengurutan di sini .
sumber
Python2, 120 byte
if[]==a[1:]
persis sepanjangif len(a)>2
tetapi terlihat lebih golf.sumber
Lua, 242 Bytes
Tidak Digabungkan & Eksplorasi
sumber
Racket 121 byte
Tidak digabungkan (l = daftar, h = kepala (elemen pertama), t = ekor (elemen lainnya atau sisanya)):
Pengujian:
Keluaran:
sumber
Japt , 23 byte
Setiap bonus harus tiga byte atau kurang untuk melunasi dalam skor total, jadi saya tidak mengambil bonus.
Cobalah online!
sumber