I should really buy Knuth's books, but worry they'd be beyond my abilities.
I also have Magnus Hetland's book and Zelle's also, and I think they're great, but haven't found the time to be systematic about either of them either. They are for this summer.
Just for fun, here is a modified version of mergesort (from my book).
There are a couple of ideas here. First, suppose we have two lists that are already sorted. It's easy to merge them into one sorted list, by comparing the next elements in each and choosing the correct one. That's what merge does. The second idea is recursion. That's what mergesort does. The code below is set up to read a power of ten from the input.
This is a good challenge for a beginning Python coder.
Here is some timing on mine:
> time python merge.py 3 real 0m0.054s user 0m0.039s sys 0m0.013s > time python merge.py 4 real 0m0.232s user 0m0.216s sys 0m0.014s > time python merge.py 5 real 0m8.201s user 0m8.178s sys 0m0.020s > |
merge.py
import random, sys
def merge(left,right):
rL = list()
while True:
if left and right:
if left[0] < right[0]:
rL.append(left.pop(0))
else:
rL.append(right.pop(0))
continue
if left:
rL.extend(left)
elif right:
rL.extend(right)
return rL
def merge_sort(iL):
if len(iL) == 1:
return iL
n = len(iL)/2
left = merge_sort(iL[:n])
right = merge_sort(iL[n:])
result = merge(left,right)
return result
if __name__ == '__main__':
try:
n = int(sys.argv[1])
except:
n = 4
N = 10**n
L = range(N)
random.shuffle(L)
result = merge_sort(L)
assert result == sorted(L)
|
