# [issue1771] Remove cmp parameter to list.sort() and builtin.sorted()

Tom Switzer report at bugs.python.org
Sun Dec 6 17:24:43 CET 2009

```Tom Switzer <thomas.switzer at gmail.com> added the comment:

Mark: I think your example actually helps illustrate my point. My point was
that computing the angle directly is less efficient or not as nice
numerically. For instance, if you are sorting points by angle relative to an
extreme point you could do something like this (a first step in the Graham
Scan) - be prepared for non-Python 3.0 code ;)

from functools import partial
from random import random

def turn(p, q, r):
"""Return -1, 0, or 1 if p,q,r forms a right, straight, or left turn
respectively."""
return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)

pts = [(random(), random()) for i in xrange(10)]
i = min(xrange(len(pts)), key=lambda i: pts[i])
p = pts.pop(i)
pts.sort(cmp=partial(turn, p))

Here our comparison function requires only 2 multiplications and 5
additions/subtractions. This function is nice especially if you are using
arbitrary precision or rational numbers as it is exact.

On Sun, Dec 6, 2009 at 6:57 AM, Mark Dickinson <report at bugs.python.org>wrote:

>
> Mark Dickinson <dickinsm at gmail.com> added the comment:
>
> Tom, I think I'm missing your point:  all three of the examples you give
> seem like perfect candidates for a key-based sort rather than a
> comparison-based one.  For the first example, couldn't you do something
> like:
>
> def direction(pt1, pt2):
>    """angle of line segment from point 1 to point 2"""
>    return atan2(pt2.y - pt1.y, pt2.x - pt1.x)
>
> my_points.sort(key=lambda pt: direction(reference_pt, pt))
>
> ? How would having a cmp keyword argument make this any easier or
> simpler?
>
>
> Here's the best example I can think of for which key-based sorting is
> problematic:  imagine that the Decimal type doesn't exist, and that you
> have triples (sign, coefficient_string, exponent) representing
> arbitrary-precision base 10 floating-point numbers.  It's fairly tricky
> to come up with a key function that maps these triples to some existing
> ordered type, so that they can be sorted in natural numerical order.
> The problem lies in the way that the sort order for the coefficient
> string and exponent depends on the value of the sign (one way for
> positive numbers, reversed for negative numbers). But it's not a big
> deal to define a wrapper for cases like this.
>
> ----------
> nosy: +mark.dickinson
>
> _______________________________________
> Python tracker <report at bugs.python.org>
> <http://bugs.python.org/issue1771>
> _______________________________________
>

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue1771>
_______________________________________
-------------- next part --------------
Mark: I think your example actually helps illustrate my point. My point was that computing the angle directly is less efficient or not as nice numerically. For instance, if you are sorting points by angle relative to an extreme point you could do something like this (a first step in the Graham Scan) - be prepared for non-Python 3.0 code ;)<br>
<br>from functools import partial<br>from random import random<br><br>def turn(p, q, r):<br>Â Â Â  &quot;&quot;&quot;Return -1, 0, or 1 if p,q,r forms a right, straight, or left turn respectively.&quot;&quot;&quot;<br>Â Â Â  return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)<br>
<br>pts = [(random(), random()) for i in xrange(10)]<br>i = min(xrange(len(pts)), key=lambda i: pts[i])<br>p = pts.pop(i)<br>pts.sort(cmp=partial(turn, p))<br><br>Here our comparison function requires only 2 multiplications and 5 additions/subtractions. This function is nice especially if you are using arbitrary precision or rational numbers as it is exact.<br>
<br><br><div class="gmail_quote">On Sun, Dec 6, 2009 at 6:57 AM, Mark Dickinson <span dir="ltr">&lt;<a href="mailto:report at bugs.python.org">report at bugs.python.org</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
Mark Dickinson &lt;<a href="mailto:dickinsm at gmail.com">dickinsm at gmail.com</a>&gt; added the comment:<br>
<br>
Tom, I think I&#39;m missing your point: Â all three of the examples you give<br>
seem like perfect candidates for a key-based sort rather than a<br>
comparison-based one. Â For the first example, couldn&#39;t you do something<br>
like:<br>
<br>
def direction(pt1, pt2):<br>
Â  Â &quot;&quot;&quot;angle of line segment from point 1 to point 2&quot;&quot;&quot;<br>
Â  Â return atan2(pt2.y - pt1.y, pt2.x - pt1.x)<br>
<br>
my_points.sort(key=lambda pt: direction(reference_pt, pt))<br>
<br>
? How would having a cmp keyword argument make this any easier or<br>
simpler?<br>
<br>
<br>
Here&#39;s the best example I can think of for which key-based sorting is<br>
problematic: Â imagine that the Decimal type doesn&#39;t exist, and that you<br>
have triples (sign, coefficient_string, exponent) representing<br>
arbitrary-precision base 10 floating-point numbers. Â It&#39;s fairly tricky<br>
to come up with a key function that maps these triples to some existing<br>
ordered type, so that they can be sorted in natural numerical order.<br>
The problem lies in the way that the sort order for the coefficient<br>
string and exponent depends on the value of the sign (one way for<br>
positive numbers, reversed for negative numbers). But it&#39;s not a big<br>
deal to define a wrapper for cases like this.<br>
<br>
----------<br>
nosy: +mark.dickinson<br>
<div><div></div><div class="h5"><br>
_______________________________________<br>
Python tracker &lt;<a href="mailto:report at bugs.python.org">report at bugs.python.org</a>&gt;<br>
&lt;<a href="http://bugs.python.org/issue1771" target="_blank">http://bugs.python.org/issue1771</a>&gt;<br>
_______________________________________<br>
</div></div></blockquote></div><br>
```