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: