[Tutor] methods of sorting

[Danny Yoo]

On Tue, Apr 22, 2014 at 4:18 PM, Patti Scott
<pscott_74 at yahoo.com.dmarc.invalid> wrote:
> I'm practicing with lists.  I was looking for documentation on sorting with
> cmp() because it isn't immediately clear to me how comparing items two at a
> time can sort the entire list.


As you note, comparison itself doesn't sort a list.  Comparing
elements by itself is a query, not an action.

But what it does is give Python enough tools to do the sort for you.
Python uses a "comparison" based sorting routine which works by taking
in a user-defined notion of when two elements are in order or not.
http://en.wikipedia.org/wiki/Comparison_sort

As a handwavy explanation of the idea: imagine a list that hasn't been
sorted.  Python can use the comparison function you give it to
repeatedly compare elements in the list.  Whenever if it sees
disorder, it can swap elements and thereby reduce the disorder in the
list.  Assuming the comparison is a "good" one,  then we can
eventually sort the whole list by repeating this over and over.  Note
that Python will be calling the comparison function on your behalf:
you won't be calling it directly yourself.

(By "good", we mean a "total ordering" in the sense described in:
http://en.wikipedia.org/wiki/Total_order)

This is a handwavy explanation because Python does these comparisons
and swapping in a fairly sophisticated way to avoid a lot of work.
See:  http://en.wikipedia.org/wiki/Timsort



It maybe that you have not seen instances of functions that take
functions as arguments.  If so, consider two functions f and g:

#########
def f(x):
    return x * x

def g(x):
    return 2 * x
#########

Toy functions, of course.  Now they themselves don't do much but
compute the square and the double of a number.  But they can be passed
as arguments to other functions to do something.  For example, if we
have some list of numbers:

#########
numbers = [3, 1, 4, 1, 5, 9, 2, 6]
#########

then we may apply f and g pointwise across those functions, using the
map() function:

#########
print(map(f, numbers))
print(map(g, numbers))
#########

and you'll see that we can compute bulk operations on lists.  Again,
we're leaving the map() function to call 'f' and 'g' for us.  This is
an example of a function that can take in other functions.  The
sorting routine you're looking at is conceptually doing a similar
thing by taking in a comparison function, which it will use during its
own work.


Passing functions as values allows for a notion of "variable" that's
really powerful: what is varying isn't just some static piece of plain
data, but rather a behavior.