WEEK10: sorting (and more analysis of algorithms) --------------------------------------------------------------- M: selection sort vs mylist.sort() 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 YOUR TURN: - 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 """ various sort functions Fall 2013 """ #------------------------------------------------# ### add your sort here!!! #------------------------------------------------# ################################################## if __name__ == "__main__": # put some test code here from random import * from time import * # ask user for N, then create data and time the sorts N = input("N: ") L = [] for i in range(N): L.append(randrange(100)) # first sort to test... COPY = list(L) # make copy, so each sort acts on same data if N<26: print COPY t1 = time() ## call your sort here !!! t2 = time() if N<26: print COPY print "sort time: ", t2 - t1