WEEK10: sorting (and more analysis of algorithms)
---------------------------------------------------------------
W: selection sort analysis
REVIEW:
- look at http://www.youtube.com/watch?v=INHF_5RIxTE
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?
- copy over timeSorts.py and add your selectionSort
- 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!!
YOUR TURN:
- something proportional to N-squared is called quadratic,
because if you double N, the "something" quadruples!
- run the 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:
