0
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ Bonuses in code golf are generally discouraged. I recommend you either remove the bonus entirely or make it part of the requirement. \$\endgroup\$ – Mego Feb 10 '16 at 19:27
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Patrick Roberts Feb 10 '16 at 19:41
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Mego Feb 10 '16 at 19:55
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Patrick Roberts Feb 10 '16 at 19:59
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Mego Feb 10 '16 at 20:01
1
\$\begingroup\$

Pyth, 6 bytes - 20% = 4.8

s.gykQ

This uses radix sort with base 2^64. Since all keys will be non-long positive integers, they are one digit long in base 2^64. We use .g to bucket the numbers, and s to flatten the resulting array. Calls to y are implicitly memoized.

Define the function y with L, which is a lambda b. For example:

Lab5        ## y = lambda b: abs(b-5)
s.gykQ

Less cheaty is this decimal LSB radix sort at 15 bytes - 20% = 12:

us.ge/yk^THGyTQ

Which takes the last twenty decimal digits, plenty for 64-bit numbers.

Try it here.

\$\endgroup\$
  • \$\begingroup\$ Also could you add an example usage and at least two test cases to demonstrate that it is type-agnostic? \$\endgroup\$ – Patrick Roberts Feb 10 '16 at 20:13
  • \$\begingroup\$ @PatrickRoberts Done. \$\endgroup\$ – lirtosiast Feb 10 '16 at 20:57
4
\$\begingroup\$

Haskell, 111 89 bytes * 0.8 = 71.2

f%a=fst<$>iterate(\x->(even#x)++(odd#x))[(x,f x)|x<-a]!!64
f#x=[(i,j`div`2)|(i,j)<-x,f j]

Usage example (sort on the sum of the lists): sum % [[1,2,3,4], [2,3,4,5], [1], [1,4,8], [9], [0]] -> [[0],[1],[9],[1,2,3,4],[1,4,8],[2,3,4,5]].

Assuming the given functions maps to non-negative 64-bit integers.

This implements binary radix sort.

How it works:

           [(x,f x)|x<-a]    -- map each element x of the input list to a pair
                             -- (x,f x), so the given function f is used only once
   iterate (...) (...) !! 64 -- repeatedly apply one step of the radix sort and
                             -- take the 64th iteration
fst<$>                       -- remove the second element of the pair, i.e.
                             -- restore the original element

                             -- one step of the radix sort
\x->(even#x)++(odd#x)        -- partition the list in pairs with even and
                             -- odd second elements and divide the second 
                             -- element of the pairs by 2. Re-concatenate

[(i,j`div`2)|(i,j)<-x,f j]   -- helper function: filter pairs where the second
                             -- element j satisfy predicate f. Adjust j.

Further calling examples:

length % ["Hello","World!","Golf"]
         -> ["Golf","Hello","World!"]

(fromEnum.last) % ["Strings","sorted","on","last","character"]
         -> ["sorted","on","character","Strings","last"]

maximum % [[1,2,3,4], [2,5,4], [5,5], [4], [6,2], [2,3]]
         -> [[2,3],[1,2,3,4],[4],[2,5,4],[5,5],[6,2]]
\$\endgroup\$
  • \$\begingroup\$ is this function type-agnostic? Could I supply an array of strings, or an array of some arbitrary type? \$\endgroup\$ – Patrick Roberts Feb 10 '16 at 19:44
  • 1
    \$\begingroup\$ @PatrickRoberts: yes it is. I've added another example. \$\endgroup\$ – nimi Feb 10 '16 at 19:52
2
\$\begingroup\$

ES6, 113 bytes - 20% = 90.4

(a,g)=>(s=(a,i)=>i?s(a.filter(x=>~x[1]&i).concat(a.filter(x=>x[1]&i)),i<<1):a)(a.map(x=>[x,g(x)]),1).map(x=>x[0])

Uses 2 as the radix. Ungolfed:

function rsort(array, key) {
    array = array.map(value => [value, key(value)]);
    // bit becomes zero when the bit falls off the left end
    for (bit = 1; bit; bit <<= 1) {
        zero = array.filter(pair => !(pair[1] & bit));
        one = array.filter(pair => pair[1] & bit);
        array = zero.concat(one);
    }
    return array.map(value => value[0]);
}

Test cases:

f=(a,g)=>(s=(a,i)=>i?s(a.filter(x=>~x[1]&i).concat(a.filter(x=>x[1]&i)),i<<1):a)(a.map(x=>[x,g(x)]),1).map(x=>x[0]);

/* example key function */
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>${f(data, complexity).map(o=>JSON.stringify(o)).join`\n`}</pre>`);
document.write(`<h2>Sorted by "index"</h2>`);
document.write(`<pre>${f(data, index).map(o=>JSON.stringify(o)).join`\n`}</pre>`);

\$\endgroup\$
  • \$\begingroup\$ There seems to be an issue with your algorithm. I ran your function on my complexity key with the data array from my example, and the output didn't seem to have any distinguishable order (but it is consistently this output): ["{"b":{"c":"a string","d":12},"e":["an","array"]}", ""an"", "true", "null", ""a string"", "12", "["an","array"]", "{}", "{"a":{"b":{"c":"a string","d":12},"e":["an","array"]},"f":true,"g":{"h":null,"i":{},"j":{"k":500}}}", "{"c":"a string","d":12}", ""array"", "{"h":null,"i":{},"j":{"k":500}}", "{"k":500}", "500"] \$\endgroup\$ – Patrick Roberts Feb 10 '16 at 20:56
  • \$\begingroup\$ Fixed, and conveniently saved me 4 (3.2) bytes too! \$\endgroup\$ – Neil Feb 10 '16 at 21:10
  • \$\begingroup\$ Yep, it checks out. Nice job! If you can, please add my two test-cases in a code snippet to your answer. If you're not sure how to, just tell me to edit your answer and I will. \$\endgroup\$ – Patrick Roberts Feb 10 '16 at 21:16
  • \$\begingroup\$ I'm not terribly familiar with JS code snippets (so far I've only used them for HTML/CSS stuff) so feel free to go ahead. \$\endgroup\$ – Neil Feb 10 '16 at 21:28
  • \$\begingroup\$ I added the test cases for you. \$\endgroup\$ – Patrick Roberts Feb 10 '16 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.