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

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]