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

Ein Hauch von Python

Ich spiele ja in letzter Zeit sehr viel mit Ruby und Python herum. Was mir an Python besonders gefällt sind unter anderem Generatoren. Damit kann man schöne Sachen machen.

def test():
    for i in range(0,3):
        yield i

x = test()

for i in x:
    print i

Einen ähnlichen Effekt kann man unter Ruby mit Enumeratoren hinkriegen

class Test
    def each
        if block_given?
            for i in 0...3
                yield i
            end
        else
            Enumerator.new(self)
        end 
    end 
end

t = Test.new
e = t.each

for i in e
    puts i
end

Ich gebe zu das ich hier ziemlich geschummelt habe und Python Generatoren über das hinausgehen was ich hier in Ruby zeige. Aber es kann hin und wieder mal recht praktisch sein ;)

Quicksort in Ruby

Angestachelt vom Alios' kurzer Illustration von Quicksort in Haskell hab ich mir mal überlegt ob man das gleiche auch in Ruby 1.9 so schreiben kann. Man kann ;)

def qs(a)
    return a if a == []
    (qs a.drop(1).find_all{|x| x < a[0]}) \
    + [a[0]] + \
    (qs a.drop(1).find_all{|x| x >= a[0]})
end

Ich finde das ganze zeigt sehr eindrucksvoll wie mächtig moderne Sprachen sind die OOP und FP vereinen. Prinzipiell kann man das Ding auch twittern :P (darum die kurzen Namen)

UPDATE: Da konnte man noch etwas verkürzen ^^

UPDATE 2: Für alle denen 2 Array Durchläufe mit find_all zuviel sind gibts hier auch noch eine etwas nettere Version ;)

def qs(a)
    return a if a.empty?
    l, g = a.drop(1).partition{|x| x < a[0]}
    (qs l) + [a[0]] + (qs g)
end