3

What is the name for the sort used in this answer? I Googled for "perfect insertion sort" but didn't find anything. Here is the code from that answer:

#this is O(n) instead of O(n log n) or worse
sub perfect_insert_sort {
    my $h = shift;
    my @k;
    for my $k (keys %$h) {
        $k[$h->{$k}{order}] = $k;
    }
    return @k;
}
Community
  • 1
  • 1
One Handed Pete
  • 108
  • 4
  • 1
    How is this a sort? This is simply a "reordering". Real sort happens when "order" field is filled. –  Sep 07 '10 at 12:50
  • 1
    @Arkadiy It is a sort because the order the result of a monotonic function. You might as well say you can't sort the set of positive integers (which is what it is doing). It is just a special case of the bucket sort (due to how that data was created we know that it is sequential, starting at 0, with no duplicates or skips, hence the perfect prefix). – Chas. Owens Sep 07 '10 at 13:00
  • Please clarify your answer by showing the contents of `$h`. Otherwise this is the more general case of applying a certain permutation to an array. – MAK Sep 08 '10 at 19:48
  • @MAK the full code is in the answer in the link. It is sorting by the order the keys were insert into the hash. – Chas. Owens Sep 08 '10 at 20:01

4 Answers4

7

I think I probably should have named that perfect_bucket_sort instead of perfect_insertion_sort.

Chas. Owens
  • 64,182
  • 22
  • 135
  • 226
  • It still doesn't perform any sorting. See [my updated answer](http://stackoverflow.com/questions/3658761/is-there-a-name-for-this-sort/3661108#3661108) for why. Sorting implies a determination of order. This is not determining order, merely reconstituting it. – Robert P Sep 08 '10 at 19:11
  • @Robert P `perl -MList::Util=shuffle -le '$a[$_] = $_ for shuffle 0 .. 9; print for @a'` is just as much a sort as `perl -MList::Util=shuffle -le 'print for sort { $a <=> $b } shuffle 0 .. 9'` The first is just significantly faster (because we know stuff about the value we are sorting on and can cheat). Go back and reread that wikipedia page. – Chas. Owens Sep 08 '10 at 20:43
4

This isn't insertion sort, in fact it's not even a comparison sort because the theoretical lowest bound for those is O(nlogn).

So it's probably bucket sort; also notice there are no comparisons made :)

Swizec Teller
  • 2,322
  • 1
  • 19
  • 24
0

It's not really a sort at all. it is, in fact, primarily a map or a transformation. This is an example of the data structure they have:

my $hash = {
   foo => { order => 3 },
   bar => { order => 20 },
   baz => { order => 66 }, 
};

It's simply a translation of 'order' to elements in an array. For example, if you pass in this $hash to perfect_insert_sort, it will return a 67 element array, with three items (one at index 3, one at 20, and one at 66) and the rest being undef, and entirely in an unsorted order.

Nothing about that function does any sorting of any kind. If there is any sorting going on in that other answer, it's happening before the function is called.

@downvoter:

And looking at the other answer, the sorting happens at insertion time. THAT component might be considered a sort. This subroutine, however, does not create that order - it merely reconstitutes it.

Take a look at the classical definition for a sort:

  1. The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order)
  2. The output is a permutation, or reordering, of the input.

Part 2 is certainly being satisfied: there is a transformation of the hash structure to a list going on. However, part 1 is not satisfied. There is no determining of order going on. The order has been predetermined during insertion. If this were a 'sort', then the following would also be a sort:

my @data = ... ;
my $index = -1;
my %stored = map { ++$index; $_ => { order => $index } } @data;
my @remade_data;
@remade_data[(map { $stored{$_}{order} } keys %stored)] = keys %stored;

As you can see, there is no sorting going on in that chunk of code, merely transformation.

Robert P
  • 15,707
  • 10
  • 68
  • 112
  • 1
    Then what do you call the radix sort, counting sort, and bucket sort? They are all named sorts on that page (and the algorithm is either a bucket sort or a counting sort depending on how you look at). You are indeed sorting the keys **by when they were inserted into the hash**, not by their values. If you go read the [code in question](http://stackoverflow.com/questions/3638690/iterating-hash-based-on-the-insertion-order/3638696#3638696) you will see that the sort is on insert order, not value of the keys. In terms of Perl 5's sort it would be `sort { $h{$a}{order} <=> $h{$b}{order} }`. – Chas. Owens Sep 08 '10 at 19:47
-1

I think it's nothing but an insertion sort.

Telemachus
  • 19,459
  • 7
  • 57
  • 79
user441425
  • 153
  • 1
  • 7
  • No, an [`insertion sort`](http://en.wikipedia.org/wiki/Insertion_sort) is different (see the link and the one in my answer). I was just too lazy to go look up the right name, so I threw perfect on the start and called it done. – Chas. Owens Sep 07 '10 at 12:52