5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ To implement pigeonhole sort you need to know the range of your sort-by function. \$\endgroup\$ – Keith Randall May 12 '14 at 2:55
  • \$\begingroup\$ Fair enough. Range is 1 to INT_MAX. (This is why I added the assumption). \$\endgroup\$ – Jacob May 12 '14 at 2:58
  • \$\begingroup\$ Can we assume the function returns a unique integer for each item, or only for each unique item? (say if the array is [1,1,1] will the function return three different values?) \$\endgroup\$ – marinus May 12 '14 at 4:53
  • \$\begingroup\$ As I said, the sort-by function will return a unique ID per each item in the given array. This imply that the input array has no repetitions. If this is not understood, you can simply assume all items in the input array are unique (i.e. [1,1,1] is not a valid input for this challenge. \$\endgroup\$ – Jacob May 12 '14 at 6:54
1
\$\begingroup\$

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│
└─┴───┴──────┴───────┘
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Excellent example of Ruby golf tricks. If the sort can be an anonymous lambda, one can write it in 37 characters as ->(f,a,*b){a.map{|x|b[f[x]]=x} newline nb-[p]}, but then the call would look like ->(f,a...b-[p]}[proc(&:length),["a","ccc","bb","eeeee"]]. \$\endgroup\$ – kernigh May 13 '14 at 20:16
1
\$\begingroup\$

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]
\$\endgroup\$
0
\$\begingroup\$

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 }
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Does not meet requirement of "all non-empty indexes' items". Your output is sparse array, while the expected output array length has to be the same as the input's length. Consider this input for example: s([{id:7,n:'T'},{id:34,n:'R'},{id:2,n:'Q'}],function(i){return i.id}), your output is [undefined × 2, Object, undefined × 4, Object, undefined × 26, Object] (length is 35), while the expected length is 3. \$\endgroup\$ – Jacob May 13 '14 at 13:00
  • \$\begingroup\$ Haha, if you wrap that in console.log it outputs nicely. Will fix up. Thanks. \$\endgroup\$ – Matt May 13 '14 at 13:21
0
\$\begingroup\$

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";
}
\$\endgroup\$

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.