```
WEEK09: sorting (and more analysis of algorithms)
---------------------------------------------------------------
W: selection sort analysis

REVIEW:

for a fun review of insertion, selection, and bubble sort
- see http://www.sorting-algorithms.com for another comparison
of the sorts

SORTING:

- see /home/jk/inclass/sorts.examples for a review of the three
sorts we talked about last time (selection sort, insertion sort,
and bubble sort)

- can you write a working selection sort function???

-----------------------------------------------------

find smallest in a list algorithm...

ismall = 0
for i in range(0, len(L)):
if L[i] < L[ismall]:
ismall = i
L[0],L[ismall] = L[ismall],L[0]

- this does the selection sort algorithm for just the first
(0th) element in the list. We need to do the above for all
indecies 0 --> len(L)

-----------------------------------------------------

selection sort algorithm:

- find smallest in list, move to index 0
- find smallest in rest of list, move to index 1
- find smallest in rest of list, move to index 2
...and so on

-----------------------------------------------------

- here's one version of selection sort:

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

def selectionSort(L):
"""
sort list in place using selection sort algorithm
"""
for i in range(len(L)):
ismall = i
# find index of smallest element of rest of list
for j in range(i+1,len(L),1):
if L[j] < L[ismall]:
ismall = j
# swap smallest element with L[i]
L[i],L[ismall] = L[ismall],L[i]

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

- how does selection sort compare to python's built-in sort?

- run timeSorts.py and test your sort with small values of N
- once you know it works, test it with N=1000,2000,4000 to
see how the times change for larger N's

N = 1000  selection sort time: 0.1685
N = 1000   built-in sort time: 0.0003

N = 2000  selection sort time: 0.4269
N = 2000   built-in sort time: 0.0007

N = 4000  selection sort time: 1.6595
N = 4000   built-in sort time: 0.0015

*** clearly L.sort() is faster...why??

- how does selection sort's time depend on the size of the list (N)?

ANALYSIS:

- how many "steps" does selection sort require to sort a list?

for i in range(len(L)):    <--- for loop depends on N
ismall = i
# find index of smallest element of rest of list
for j in range(i+1,len(L),1):   <--- another (nested) for loop
if L[j] < L[ismall]:
ismall = j
# swap smallest element with L[i]
L[i],L[ismall] = L[ismall],L[i]

Here's how selection sort works on a sample list of length 7:

[ 9,    50,    -2,     6,    9,    17,    20]
<-- find smallest num, swap to position 0 -->
[ -2,    50,    9,     6,    9,    17,    20]
<-- find smallest, swap to pos  1 -->
[ -2,     6,    9,    50,    9,    17,    20]
<-- find small,  swap to 2 -->
[ -2,     6,    9,    50,    9,    17,    20]
<-- find/swap  to 3 -->
[ -2,     6,    9,    9,    50,    17,    20]
<-- swap to 4 -->
[ -2,     6,    9,    9,    17,    50,    20]
<--  5 -->
[ -2,     6,    9,    9,    17,    20,    50]
<->
[ -2,     6,    9,    9,    17,    20,    50]

See how that looks like an NxN matrix? Actually, it
looks like 0.5*(NxN), but that's still proportional to N-squared!!

- something proportional to N-squared is called quadratic,
because if you double N, the "something" quadruples!

- run the /home/jk/inclass/pylabLinePlots.py program again to
see the comparison of things proportional to
N (linear) vs NlogN vs N-squared (quad)

MERGE SORT:

- see http://www.sorting-algorithms.com to compare sorts

- do interactive demo with cards and students!

- merge sort uses a divide-and-conquer method to sort a list:

given a list, split it in two (if the size of the list > 1)
sort each of the two halves of the list
merge the two sorted halves back into the original list

- the second step above (sort each of the two halves) can actually
be done by calling a new mergeSort function

Note: this is recursion...a function that calls itself to get
it's work done

```

Here are some interesting merge sort links: