CODEWITHSUNDEEP
perlalgorithmsorting
One Handed Pete
One Handed Pete

Reputation: 108

Is there a name for this sort?

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;
}

Upvotes: 3

Views: 296

Answers (4)

Robert P
Robert P

Reputation: 15988

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.

Upvotes: 0

user441425
user441425

Reputation: 153

I think it's nothing but an insertion sort.

Upvotes: -1

Swizec Teller
Swizec Teller

Reputation: 2322

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 :)

Upvotes: 4

Chas. Owens
Chas. Owens

Reputation: 64949

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

Upvotes: 7

Related Questions