# Week 9, Monday: Sorting (and more analysis of algorithms)

• Quiz 4 this Friday
• lab 7 full program due this Saturday
• will send out current grades this week

### sorting

python has a built-in sort method for lists:

``````>>> L = range(10)
>>> print L
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> from random import *
>>> shuffle(L)
>>> print L
[3, 1, 7, 4, 5, 9, 0, 6, 2, 8]
>>> L.sort()
>>> print L
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
``````

How does `L.sort()` work, and is it a good sort to use?

How would you sort numbers in a list? If you had to write a function to sort a given list, how would you do it? Try it out using some playing cards -- see if you can come up with a sorting algorithm. Once you have an idea, demo it for me or a ninja. Make sure your function:

• works with the playing cards initially face down
• only uses compare and swap

Once you have shown us a working sort algorithm, see if you can code it up in a file called `sorts.py`. There are many different ways to sort a list. We will add 3 or 4 different sorting functions to this file. Then we can just add `from sorts import *` in our other programs that need a sorting function.

### testing

Make sure you add a testing section to `sorts.py`. Here is a small example (assuming you called your sort function `mysort()`:

``````if __name__ == "__main__":

from random import shuffle

N = 100
L = range(N)
shuffle(L)
mysort(L)
assert L == range(N)
``````

### swapping two items in a list

In most languages, to swap two items in a list, you would do this (assuming `i` and `j` are valid indecies):

``````tmp = L[i]     # save ith value to temporary location
L[i] = L[j]    # copy jth value to ith position
L[j] = tmp     # copy from tmp to jth position
``````

Since this is a common operation, python provides a shortcut:

``````L[j],L[i] = L[i],L[j]
``````