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

QUIZ 5 is this Friday...

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

from random import randrange

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

def selectionSort(L):
"""use selection sort alg to sort the given list"""

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

def main():
"""test out our sorts"""

N = input("size of data, N: ")
for i in range(N):
L.append(randrange(0,N))

print L
selectionSort(L)
print L

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

if __name__ == "__main__": main()

```