WEEK09: 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 /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:

• merge sort animation
• merge sort diagram