Sorting observation
Author Message
Sorting observation

C's 'qsort' function and Perl's built-in 'sort' operator require a
three-way comparator function, which compares two items and returns
negative if they are in the right order, positive if they are in the
wrong order, and zero if it doesn't matter.  But this isn't the only
possible interface to a generic sort operator.

Other languages, such as J, SML, and Common Lisp, have sort operators
that use a two-way comparator.  The comparison function simply says
whether one item precedes another.  To give the idea of how this might
work, here's a sample implementation in Perl:

# quicksort

my \$cmp = shift;

else {
local \$b = shift;
my (\$small, \$large);
local \$a;

}

}
}

Then you no longer need Perl's special three-way '<=>' and 'cmp'
operators, because you just use the regular '<' and 'lt' operators

print qsort sub { \$a < \$b },  1,4,2,8,5,7;
# result is 1,2,4,5,7,8

# result is eight,five,four,one,seven,two

Similarly, if you want a reversed sort, you do not need to use the
slightly strange trick of exchanging \$a and \$b.  If you know that
trick, you can still use it, but it's more perspicacious to just use
the opposite comparison operator.  For ascending order, use < so that
each element is < the next one;; for
descending order use > so that each element is > the next one:

print qsort sub { \$a > \$b },  1,4,2,8,5,7;  # 8,7,5,4,2,1

The reason I bring this up is I've just discovered the following trick:

print qsort sub { \$a == \$b },  1,4,2,8,5,4,7,1,4,2,8,5,3,7;

With the qsort implementation above, the output is 11444228855773.
Items in appear in the same order in the input as in the output, (for
example, the first 4 precedes the first 8 in the input, so the 4s
precede the 8s in the output) but with equal items grouped.  There is
no analog of this with three-way comparators.

rd
(\$p{\$_})&6];\$p{\$_}=/ ^\$P/ix?\$P:close\$_}keys%p}p;p;p;p;p;map{\$p{\$_}=~/^[P.]/&&
close\$_}%p;wait until\$?;map{/^r/&&<\$_>}%p;\$_=\$d[\$q];sleep rand(2)if/\S/;print

Tue, 04 May 2004 16:56:33 GMT
Sorting observation

Quote:
> Then you no longer need Perl's special three-way '<=>' and 'cmp'
> operators, because you just use the regular '<' and 'lt' operators

Praise be.  I really, really hate explaining <=> and cmp to students.
So I usually wind up hand-waving until I have to explain how to write
a custom sort.  Then I have to confront the weirdness head on.

A sort-sub that returns true/false would make this so much easier,
I think.

Quote:
> The reason I bring this up is I've just discovered the following trick:

>         print qsort sub { \$a == \$b },  1,4,2,8,5,4,7,1,4,2,8,5,3,7;

> With the qsort implementation above, the output is 11444228855773.
> Items in appear in the same order in the input as in the output, (for
> example, the first 4 precedes the first 8 in the input, so the 4s
> precede the 8s in the output) but with equal items grouped.  There is
> no analog of this with three-way comparators.

Oh my.  I had an application for something like this a few weeks
ago.  I had a series of different XML elements, all children of the
same parent element that I wanted to group together.  However: I
couldn't change the relative order of the like items within its group.
(And a sort wasn't necessary.)

I wound up benching a decorate-sort-undecorate technique (a stable
sort) against just pushing the elements into a hash-of-lists and settled
on the latter.  But that little trick would've been a clever solution.

--
Clinton A. Pierce            Teach Yourself Perl in 24 Hours  *and*

"If you rush a Miracle Man,     for details, see http://geeksalad.org
you get rotten Miracles." --Miracle Max, The Princess Bride

Wed, 05 May 2004 08:46:57 GMT
Sorting observation

Quote:
> Praise be.  I really, really hate explaining <=> and cmp to students.
> So I usually wind up hand-waving until I have to explain how to write
> a custom sort.  Then I have to confront the weirdness head on.

Agreed.  Teaching <=> along with the *binary* operators is confusing.
I wait until custom sorting to bring it up, too.

Quote:
> A sort-sub that returns true/false would make this so much easier,
> I think.

Seems to me that you could call it a needs-swapping (or inversely
order-is-ok) predicate.  A 2-value predicate is sufficient for that.

Obviously, the 3-value spaceship operator was built on top of C's
Laziness (with a capital "L" - the virtuous kind)?

Quote:
> > The reason I bring this up is I've just discovered the following trick:

> >         print qsort sub { \$a == \$b },  1,4,2,8,5,4,7,1,4,2,8,5,3,7;

> > With the qsort implementation above, the output is 11444228855773.
> > Items in appear in the same order in the input as in the output, (for
> > example, the first 4 precedes the first 8 in the input, so the 4s
> > precede the 8s in the output) but with equal items grouped.  There is
> > no analog of this with three-way comparators.

It's hard to tell from your output that the sort is preservative
(i.e. preserves input order for equal values).  Having a preservative
sort was very important to me in shell pipes.

sort by_last_name | sort by_first_name | sort by_age

Without a preservative sort, a single sort must do all the work:

sort by_last_name_by_first_name_by_age

And it's not always up to that.

Analogously in perl

This may have been done as one sort as follows:

[[ Does this code use the package globals \$a and \$b correctly as a
pass-through through the block into the subroutines? ]]

Unfortunately, sort(1) didn't preserve order on all systems.  More
unfortunately, it could have.  Fortunately, that was easily fixed in
the C code (back when it was available) and recompiled.  The sort(1)
executable was built on top of a qsort(3) function call which was
ambiguous on the return value of equal values.  This ambiguity would
probably cause Perl to crash.

Since I don't have perl on my laptop, could you verify the sort is
preservative?  The following (unchecked) code could do that.

print join ", " qsort sub { substr(\$a,1,1) == substr(\$b,1,1) },
qw(
1a
4a
2a
8a
5a
4b
7a
1b
4c
2b
8b
5b
3a
7b
)

It should output the following sequence:

1a, 1b, 4a, 4b, 4c, 2a, 2b, 8a, 8b, 5a, 5b,7a,7b, 3a

--
Michael Running Wolf

Thu, 06 May 2004 08:06:05 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages