Montag, 4. Januar 2010

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

Kommentare:

lava.nova hat gesagt…

Яuby is interpreted so this can be slow.
Zehr gut!

xRaich[o]²x hat gesagt…

Yes, i know. Haskell performs a lot faster here. Even though, this was meant as a demonstration.
On the other hand, there is a Ruby implementation on top of LLVM for the Mac called macruby . Never benchmarked it since it's still in its beta phase, but i assume that it performs pretty well.

Regards,
raichoo