0
Goal
As the title suggests, write a radix sort function (either MSB or LSB is fine) that accepts two parameters:
- an array of values of any type (you can assume that they are all of the same type / class, etc.)
- a function (or function pointer, depending on your language) that takes a single parameter of the same type as the objects given in the array and returns the coerced integer key of the object.
Implementation may mutate the array or operate out-of-place, but must return the sorted array.
Tips
- If array indexing in your language is affected by the byte-size of each index, you can assume that the objects referenced in the array are pointers rather than values.
- If the size of an array pointed to in a function parameter cannot be determined in your language, then add another parameter to your radix sort signature, passing the size in bytes of your array, or number of elements in your array, whichever you prefer:
void *rsort(void *arr, size_t length, int(*key)(const void *));
Bonus
A bonus reduction of 20% to your score will be given if your implementation memoizes the keys of the objects in the array so that the function provided only needs to be called once for each object in the array.
Example Usage (and test-case)
Assuming an answer was provided in JavaScript, a test-case might look something like this:
/* note that this implementation will not be acceptable as a submission -
* it is NOT a true radix sort
*/
function myFakeRadixSort(array, key) {
return array.sort(function(a, b) {
return key(a) - key(b);
});
}
/* this will be used as an example key function -
* you will not need to implement this
*/
function complexity(obj) {
return JSON.stringify(obj).length;
}
var tree = {
a: {
b: {
c: "a string",
d: 12
},
e: ["an", "array"]
},
f: true,
g: {
h: null,
i: {},
j: {
k: 500
}
}
};
/* another example key function
*/
function index(obj) {
return JSON.stringify(tree).indexOf(JSON.stringify(obj));
}
var data = [];
/* this is a hack to traverse the object */
JSON.stringify(tree, function(key, value) {
data.push(value);
return value;
});
document.write(`<h2>Sorted by "complexity"</h2>`);
document.write(`<pre>${myFakeRadixSort(data, complexity).map(o=>JSON.stringify(o)).join`\n`}</pre>`);
document.write(`<h2>Sorted by "index"</h2>`);
document.write(`<pre>${myFakeRadixSort(data, index).map(o=>JSON.stringify(o)).join`\n`}</pre>`);
tl;dr
Write a radix sort with this signature, or as close as possible to this signature:
void *rsort(void *arr, int(*key)(const void *));
Leaderboards
var QUESTION_ID=71693,OVERRIDE_USER=42091;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+|\d*\.\d+|\d+\.\d*)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}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="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><div id="language-list"> <h2>Winners 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><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>
Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.
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 leaderboard snippet:
# [><>](http://esolangs.org/wiki/Fish), 121 bytes
Shortest code in bytes wins!
Is a decimal radix sort okay, or does it need to be binary? – lirtosiast – 2016-02-10T19:26:32.667
2Bonuses in code golf are generally discouraged. I recommend you either remove the bonus entirely or make it part of the requirement. – Mego – 2016-02-10T19:27:07.813
@ThomasKwa any radix you choose will be acceptable, just make sure to specify that when you explain your implementation in your answer. – Patrick Roberts – 2016-02-10T19:35:14.270
Is there an upper bound on the keys? Will they always be positive? – lirtosiast – 2016-02-10T19:36:00.923
@ThomasKwa, the keys can be assumed to be non-negative.
0
is a possible key, and the upper bound will be whatever your language's default integer maximum is. – Patrick Roberts – 2016-02-10T19:38:17.6332@Mego
Bonuses are only interesting when they pose a trade-off that could go either way.
I chose 20%, as that seemed like a fairly reasonable trade-off that would allow viable answers with or without the bonus. – Patrick Roberts – 2016-02-10T19:41:15.693What builtins are allowed? Pyth has
.g
, which groups values in an array by the output of some function. – lirtosiast – 2016-02-10T19:48:16.847@ThomasKwa This may sound hard to interpret, but any language builtins and standard libraries are fine, as long as you implement the radix sort. For example, if you use
.g
in your implementation to group values by one digit at a time, I would accept that. If you use some builtin to just sort the array for you (like in my example code), that would not be acceptable. – Patrick Roberts – 2016-02-10T19:53:56.8872@PatrickRoberts
When the bonuses are well-balanced, you can have the opposite problem that a golfer needs to write a bunch of different variants of the program to see what's worth in, which becomes exponentially more cumbersome with more and more bonuses.
. Having to solve the problem twice to determine the best score is annoying and detracts from the challenge. – Mego – 2016-02-10T19:55:07.7671@Mego That sounds like a personal opinion, and I personally disagree. I provided that bonus with the intention of getting a little more variation in the supplied answers. Besides, it's only one bonus, which nullifies your "exponentially more cumbersome" argument. There's only two variations per hypothetical answer, and that's easy enough to test. I'd even go as far as to say it makes the challenge more interesting. – Patrick Roberts – 2016-02-10T19:59:25.590
1@PatrickRoberts It's the personal opinion of at least 27 users of the site (given the score of +26/-0 on the meta post). Bonuses typically detract from the core challenge. This is not an exception. – Mego – 2016-02-10T20:01:31.117
@Mego there are many other users that did not care to vote (maybe a silent majority). Now there is at least 1 vote against that topic anyway – edc65 – 2016-02-10T20:29:56.330