FEB.
19

the beauty of Ruby's Quick Sort implementation

I have read a blog post about Ruby functional programming, in his example he uses Quick Sort algorithm , after read his post , I found myself really like his final solution, I think it is a good example of Ruby’s beauty, and I tried to refactor it a little bit like this:

def quicksort(items)
  return [] if not items or items == []
  x, *xs = items
  quicksort(xs.select { |i| i <  x }) + [x] + quicksort(xs.select { |i| i >= x })
end

It only contains 3 lines of code and it is even shorter than its pseudocode:

function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Isn’t it beautiful? Do you like this kind of beauty, then start to learn Ruby now!

3 comments. post a comment 我要评论
姚远: hey!!!生日快乐！！！
Nicholas Ren: I never heard that Ruby is a functional language. this version of quicksort implementation is based on the Lamda feature. Am I correct ?? I'll give a scala version implementation later :-)
Nicholas Ren: scala version implementation is here: def quicksort[T](less: (T, T) => Boolean)(xs: List[T]):List[T]= xs match { case List() => List() case y::ys => quicksort(less)(ys.filter( a => less(a, y))) ::: List(y) ::: quicksort(less)(ys.filter( b => !less(b, y))) }