from whrandom import randint # the standard random number module from time import clock # for timing different algorithms
def bubble_sort(list): l=list[:] # create a slice-copy of the list for i in range(len(l)): # for every element [i] in the list for j in range(i+1,len(l)): # examine every element [j] after it if l[i]>l[j]: # and if they are "out of order" l[i],l[j]=l[j],l[i] # swap them return l
def selection_sort(list): l=list[:] # create a copy of the list sorted=[] # this new list will hold the results while len(l): # while there are elements to sort... lowest=l[0] # create a variable to identify lowest for x in l: # and check every item in the list... if x<lowest: # to see if it might be lower. lowest=x sorted.append(lowest) # add the lowest one to the new list l.remove(lowest) # and delete it from the old one return sorted
def merge(a,b): # this funtion merges two pre-sorted c=[] # lists into one sorted list while len(a) and len(b): # while there are items in both lists if a[0]<b[0]: # pick whichever "top" item is lower c.append(a[0]) # and add it to the new list del a[0] # then delete it from the original else: c.append(b[0]) del b[0] c=c+a+b # append anything that's left over return c def merge_sort(l): # sort lists by sorting each half, if len(l) > 1: # then merging the halves return merge(merge_sort(l[len(l)/2:]),merge_sort(l[:len(l)/2])) else: return l
def trial(func,list): # time how long it takes start = clock() # get starting time... list1 = func(list) # try the function... end = clock() # get the ending time... print " %6.2f"%(end - start,), # and print the total time it took print " size bubble selection merge" for size in range(50,1001,50): # we go from 50 to 1000 items to test list=[] for i in range(size): list.append(randint(0,size)) # and we fill the list with random #'s print "%5d"%(size,), trial(bubble_sort,list) # then we try each sort() on the list trial(selection_sort,list) trial(merge_sort,list) print
|