WEEK09: sorting (and more analysis of algorithms) --------------------------------------------------------------- M: selection sort vs mylist.sort() QUIZ 5 is this Friday... 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 from random import randrange ######################################### def selectionSort(L): """use selection sort alg to sort the given list""" # add your sort here... ######################################### def main(): """test out our sorts""" N = input("size of data, N: ") for i in range(N): L.append(randrange(0,N)) print L selectionSort(L) print L ######################################### if __name__ == "__main__": main()