27
3
Well... there are 59 (now 60) questions tagged sorting, but no simple quicksorts.
That must be fixed.
For those unfamiliar with quicksort, here is a breakdown, courtesy of Wikipedia-
- Pick an element, called a pivot, from the array.
- Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
Rules
The rules are simple:
- Implement a numerical quicksort in the programming language of your choice.
- The pivot should be chosen at random or with median of three (1st, last, and middle element).
- Your program can be a complete program or function.
- You can get the input using STDIN, command line args, or function parameters. If using a string input, the input is space separated.
- The input may contain decimal and negative values. However, there will be no duplicates.
- You may output to STDOUT or by returning from the function.
- No built-in sorting (or sorting related) functions or standard loopholes.
- The list may be an arbitrary length.
Bonus #1: On lists or sub-lists of length <= 5, use insertion sort to speed things up a bit. Reward: -15%.
Bonus #2: If your language supports concurrency, sort the list in parallel. If you are using an insertion sort on sub-lists, the final insertion sort doesn't need to be in parallel. Built in thread pools/ thread scheduling are allowed. Reward: -15%.
Note: Median of three was confusing some people, so here is an explanation, courtesy of (again) Wikipedia:
choosing the median of the first, middle and last element of the partition for the pivot
Scoring
This is code-golf. Base score is in bytes. If you got one bonus, take 15% off that number. If you got both, take 30% off. That really sounds like a sales pitch.
This isn't about finding the shortest answer overall, but rather the shortest in each language.
And now, a shameless copy of the leaderboard snippet.
The Leaderboard
The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.
To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:
## Language Name, N bytes
where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:
## Ruby, <s>104</s> <s>101</s> 96 bytes
If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:
## Perl, 43 + 2 (-p flag) = 45 bytes
You can also make the language name a link which will then show up in the snippet:
## [><>](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>
"No built-ins" - define "built-in" for this purpose, please. As-is, I don't know how one would select a random pivot. – TLW – 2015-11-01T02:49:02.913
Also, how do you choose a pivot at random in a language with no RNG? (E.g. BF) – TLW – 2015-11-01T02:50:28.810
@TLW clarified built-ins; a rng is fine. If there isn't a rng the median of three is fine. Though if someone can golf this to under 700 bytes (with median of three), I'll give them a bounty.
– Daniel M. – 2015-11-01T02:57:56.613Thanks. I was (mainly) joking about BF, though. Among other things, quicksort in BF should really be named "slowsort" (although that's a different sort already), due to the whole NUMA thing (namely, that you can only move one space per step, and can only "carry" a finite amount of information). It's the same problem as with single-tape Turing Machines... I do not believe there is a way to reverse an array in BF (or a single-tape TM) in under O(n^2) time. – TLW – 2015-11-01T03:13:15.677
I'm noticing that quite a few of the codes are working just a little too literally, and it hasn't been clarified, yet - can the lists include repeated entries? That is, can you input
[1,5,3,5,9,2,6]
, and should it output[1,2,3,5,6,9]
or[1,2,3,5,5,6,9]
? A literal reading of the rules makes it the former. – Glen O – 2015-11-01T08:56:42.653@GlenO Made it a bit clearer. The input won't contain duplicates, so this situation shouldn't arise. – Daniel M. – 2015-11-01T12:56:08.580
4"The pivot should be chosen at random or with median of three (1st, last, and middle element)." What does this mean? You previously said only one element is chosen. – msh210 – 2015-11-01T14:51:07.657
In step 3, "concatenate", what order are we supposed to concatenate them in? Wouldn't choosing such an order itself require a sorting function? – msh210 – 2015-11-01T15:11:22.873
@msh210 All it means is to join the sub-lists together. For median of three, take a look at the wikipedia article for quicksort (Algorithm>Implementation issues > Choice of pivot). All it is is a way to choose a pivot so that the algorithm doesn't take quadratic time on sorted lists. I mainly added it so that languages without rng support could participate.
– Daniel M. – 2015-11-01T16:50:48.660@msh210 I updated the post with better definitions – Daniel M. – 2015-11-01T17:01:02.847
The leaderboard snippet doesn't work with decimals. I led me to believe that there was a 3 bytes solution :/ – daniero – 2015-11-01T17:53:26.533
2@daniero Snippet is fixed now – Daniel M. – 2015-11-01T19:15:20.643
@msh210 ...there is a WP link (look near top) – Daniel M. – 2015-11-01T21:49:37.727
1Is the median choice algorithm a hard requirement? It is impractical (as in, it tanks the performance) in languages that use a linked list as their primary array type (Haskell, LISP) and there is already at least one answer that ignores the rule. – John Dvorak – 2015-11-02T08:57:45.880
@JanDvorak "The pivot should be chosen at random or by median of three". The med of three is mostly for langs that don't have a built in rng. I'll clarify that a bit more when I have cpu access – Daniel M. – 2015-11-02T11:58:38.930
2Both random pivot and median of three are problematic in list-based languages. Both require random access into the array and accessing the end of a linked list is O(n). Taking Taking the median of the first three elements doesn't quite do the same kind of job (also because you'll grab the same pivot within three splits anyways) and only complicates the code for no good reason. – John Dvorak – 2015-11-02T12:05:15.273
1Random pivot is problematic in Haskell for another reason, too - once you start rolling dice, you're no longer writing a function. You're defining an I/O action that produces an array. You could define a function that takes a RNG state as an argument, but it isn't too great either. – John Dvorak – 2015-11-02T12:16:26.733