```
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

- 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
"""

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

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

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

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

```