Montag, 4. Januar 2010

Quicksort in Python

Und einfach nochmal weils so schön ist:

def partition(f, a):
l = []
r = []
for i in a:
if f(i):
l.append(i)
else:
r.append(i)
return l,r

def qs(a):
if a == []:
return a
return qs([x for x in a[1:] if x < a[0]]) \
+ [a[0]] + \
qs([x for x in a[1:] if x >= a[0]])

def qs2(a):
if a == []:
return a
l,g = partition(lambda x: x < a[0], a[1:])
return qs2(l) + [a[0]] + qs2(g)

a = [4,6,3,5,1,2,7,0,9,8]

print qs(a)
print qs2(a)

Und die Ersties bei mir an der Uni beschweren sich darüber das sie funktionale Programmierung lernen müssen -_-

UPDATE: Das ganze geht noch schöner mit Python List Comprehensions

Keine Kommentare: