Golf the Pigeonhole sort

Question

Implement the Pigeonhole sort. This is a variant of the Bucket sort, and its logic is very simple: index your items (by a given function) and then return all non-empty indexes' items.

Your program/function should get an array of items in the most comfortable way for your language of choice, (i.e. a parameter, stdin, etc.), and in any format you like (for example: JSON). It should return/output a sorted array.

Do not modify the given array.

The second parameter that will be given to your program/function will be the "sort-by function". For exmaple, in JavaScript it will be something like function(item){return item.id;}.

For simplicity, you can assume this function returns a unique positive Integer for each item in the given array.

Shortest code wins. Only ASCII is allowed.

Answer 1

J (39)

f=:1 :'y{~z i.g#~+/z=/g=.i.>:>./z=.u y'

Explanation:

• z=.u y: apply the function u to the argument y. The function should distribute over the array.
• g=.i.>:>./z: Make the 'holes' (in the range [0..max(u(y))]).
• +/z=/g: for each hole, get how many elements it contains.
• g#~: replicate each hole coordinate by how many elements it contains (so if holes 3 and 5 had 1 element, and hole 8 had 3, we get 3 5 8 8 8).
• z i.: look up the position of each value in z. For example, if u y is 5 for the 3rd element of y, this gives 3 for 5.
• y{~z: look up the matching elements in the starting array

Examples:

   f=:1 :'y{~z i.g#~+/z=/g=.i.>:>./z=.u y'

   NB. functions and data
   ascii=:a.&i.
   text=:'here is some text to sort'
   length=:#&>
   arrays=:1 2;3;4 5 6 7;8 9 10 NB. these will be sorted by length

   NB. show effect of functions
   ascii text
104 101 114 101 32 105 115 32 115 111 109 101 32 116 101 120 116 32 116 111 32 115 111 114 116
   length arrays
2 1 4 3

   NB. sort
   ascii f text
     eeeehimooorrsssttttx
   length f arrays
┌─┬───┬──────┬───────┐
│3│1 2│8 9 10│4 5 6 7│
└─┴───┴──────┴───────┘

Answer 2

Ruby, 43

def s a,*b,&f
a.map{|x|b[f[x]]=x}
b-[p]
end

Calling looks like

p s(["a","ccc","bb","eeeee"],&:length)
  -> ["a", "bb", "ccc", "eeeee"]

Tricks: *b in the arg list creates an empty output array (so long as you don't, y'know, pass any args). &f creates a lambda reference to the passed-in block that can be called via f[] (normal Ruby convention is to use yield). a.map iterates over the input array without modifying it and is one character shorter than a.each. b-[p] strips out the nil values, equivalent to b.compact.

Answer 3

Python 2 - 98 92 bytes

def p(l,f):
 x=[None]*max(map(f,l))
 for e in l:x[f(e)-1]=e
 return[i for i in x if i!=None]

l is the list to sort, f is the sort-by function.

Ungolfed (a bit):

def pigeonhole(list, sort_function):
    max_value = max(map(sort_function, list)) # Find how big the final list has to be
    sorted_list = [None] * max_value # Create a list of that many Nones

    for element in list:
        sorted_list[sort_function(element) - 1] = element # Subtract one because sort_function returns positive ints and lists are 0-indexed

    return [element for element in sorted_list if element is not None] # Filter out Nones and return

def return_same(x):
    return x # This sort function will make the pigeonhole sort ints normally. There's no reason it has to be this function, it just has to return positive ints.

print pigeonhole([8, 4, 5, 9, 11, 3], return_same) # [3, 4, 5, 8, 9, 11]

Answer 4

Groovy - 135 chars

Using Groovy 2.2.1, inspired by undergroundmonorail's answer, though here input data and sort function are specified in files:

e={new GroovyShell().evaluate(new File(args[it]))}
l=e(0)
f=e(1)
s=new Object[l.max{f(it)}]
l.each{s[f(it)-1]=it}
println s.findAll{it}

As an assist to the reader, l = list of items (from file), f = sort function (from file), s = sorted list, and e = simple convenience function to evaluate data as code.

An example command-line looks like:

groovy P.groovy data.txt f.txt

where data.txt is:

[8,4,5,9,11,3]

and f.txt is:

{ x -> x }

Answer 5

JavaScript - 92

I believe this is what is asked for.

function s(a,b){c=[];a.map(function(e){c[b(e)]=e});return c.filter(function(f){return !!f})}

Test:

console.log(s([{id:3},{id:5},{id:7},{id:1}],function(x){return x.id}));

returns:

[1: Object, 3: Object, 5: Object, 7: Object]
1: Object
id: 1
3: Object
id: 3
5: Object
id: 5
7: Object
id: 7

EDIT: fixed as per @Jacob's comments.

Answer 6

C++14, 154 bytes

As unnamed lambda:

#include<map>
#include<vector>
[](auto&v,auto f){std::map<int,int>m;for(int c:v)m[f(c)]=c;std::vector<int>r;for(auto p:m)r.push_back(p.second);return r;}

Assumes v to be a container like vector<int>, could also be int[]

Ungolfed:

auto f =
[](auto&v, auto f){
  std::map<int,int> m;
  for(int c:v)
    m[f(c)]=c;
  std::vector<int> r;
  for(auto p:m)
    r.push_back(p.second);
  return r;
};

Usage:

int main() {
  std::vector<int> v={5,2,1,3,4};
  auto w = f(v, [](int x){return x;});
  for (auto c:w) std::cout << c << ", ";
  std::cout << "\n";
}