WEEK10: sorting (and more analysis of algorithms)
---------------------------------------------------------------
 M: selection sort vs mylist.sort()

SORTING:

 - python has a built-in sort function 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

     * make sure the playing cards are initially face down
     * also, only two operations are allowed:
           compare
           swap

 - here's one idea, called selection sort:

     * assume we have a list called L
     * find the smallest number in the list, swap it with L[0]
     * find the smallest number in the list, except for L[0],
       and swap it with L[1]
     * find the smallest number in the list, except for L[0] 
       and L[1], and swap it with L[2]
     * and so on....

   it's called selection sort because each time you are selecting
   the smallest number from the remaining unsorted elements

I assume you understand the "find smallest number in a list"
part, but here it is:

ismall = 0  # index of first element in list
for i in range(len(L)):
  if L[i] < L[ismall]:
    ismall = i
print "smallest is ", L[ismall]

 - other common sorts are insertion sort and bubble sort (there are
   many other sorts, but selection, insertion, and bubble sort are
   the ones most people think of)

bubble sort algorithm: 
 - for every item in the list, compare to item just to the
   right, swap if needed
 - keep doing the above until you go from one end of the
   list to the other and don't make any swaps!

insertion sort algorithm:
 - assume item at index 0 is already "sorted"
 - starting with item at index 1, check all items
   to the left and swap positions if needed
 - do the same for item at index 2, where now items
   at index 0 and 1 should be in order
 - do the same for item at index 3
 ...and so on


PYTHON:
 
 - this is python's own shorthand notation for swapping 
   two elements in a list:

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

   what it is really doing is something like this:

        tmp = L[i]
        L[i] = L[j]
        L[j] = tmp
 

YOUR TURN:

 - see if you can code up a version of selection sort (or one of
   the others, if you want)
 - put your code in a file called sorts.py, so we can import this
   to use in other codes
 - add some test code to main() to make sure your sort function works



"""
various sort functions

Fall 2013
"""


#------------------------------------------------#

### add your sort here!!!

#------------------------------------------------#

##################################################

if __name__ == "__main__":
  # put some test code here

  from random import *
  from time import *

  # ask user for N, then create data and time the sorts
  N = input("N: ")

  L = []
  for i in range(N):
    L.append(randrange(100))

  # first sort to test...
  COPY = list(L)  # make copy, so each sort acts on same data
  if N<26: print COPY
  t1 = time()

  ## call your sort here !!!

  t2 = time()
  if N<26: print COPY
  print "sort time: ", t2 - t1