Daniel's Blog

List quicksort := method(
    (self isEmpty) ifTrue(return List clone) ifFalse(
        first := self first
        rest := self slice(1)

        below := Quicksort quicksort(rest select(i, i < first))
        above := Quicksort quicksort(rest select(i, i >= first))
        return below appendSeq(list(first) appendSeq(above))    
    )
)

def quicksort(l):
    if l == []:
        return []
    else:
        x, xs = l[0], l[1:]
        return quicksort([ i for i in xs if i < x ]) + \
               [x] + quicksort([ i for i in xs if i >= x ])

def quicksort(l)
  if l == [] then 
    []
  else
    x, *xs = l

    quicksort(xs.select { |i| i <  x }) + [x] + 
      quicksort(xs.select { |i| i >= x })
  end
end

module Quicksort where

quicksort (x:xs) = quicksort [ i | i <- xs, i < x ] 
                   ++ [x] ++
                   quicksort [ i | i <- xs, i >= x ]
quicksort [] = []

-module(quicksort).
-export([quicksort/1]).

quicksort([H|T]) ->
    quicksort([ X || X <- T, X < H ])
    ++ [H] ++
    quicksort([ X || X <- T, X >= H ]);
quicksort([]) -> [].

let rec quicksort = function
  | (x::xs) -> 
      (quicksort (List.filter (fun i -> i < x) xs))
      @ [x] @ 
      (quicksort (List.filter (fun i -> i >= x) xs))
  | [] -> []
;;

(defun quicksort (l)
  (cond
    ((null l) nil)
    (t (let ((x (car l))
         (xs (cdr l)))
     (concatenate 'list
              (quicksort (remove-if #'(lambda (i) (< x i)) xs))
              (cons x nil)
              (quicksort (remove-if #'(lambda (i) (> x i)) xs)))))))

(defun quicksort (l)
  (cond
    ((null l) nil)
    (t (concatenate 'list
            (quicksort (remove-if #'(lambda (i) (< (car l) i)) (cdr l)))
            (cons (car l) nil)
            (quicksort (remove-if #'(lambda (i) (> (car l) i)) (cdr l)))))))

Tags erlang, haskell, io, languages, lisp, ocaml, programming, python, ruby | 14 comments

Comments

Leave a response

1. nukeedit
   Bill Weiss said 5 days later:
   

   Ok, no one else is going to put out, I guess I will.

   Your Python and Ruby implementations aren’t very idiomatic. That’s probably because you are in functional mode. There are better ways to implement it in these, as I’ll cover later.

   These are great pedagogical implementations, but they’re inefficient. They all scan through the list twice (once to find the elements less than the pivot, once to find the elements greater). This looks like the best way to do it in a functional language, but in python/ruby it could be better.

   I suspect that the in-place, efficient implementations would be rather ugly in the functional languages. In ruby/python they aren’t much longer. Is there a clean way of doing sub-lists in your functional programming language of choice (YFPLOC)?

   Erlang is pretty neat looking, and Haskell is as well (since they look so similar). OCaml has more yad around it, but that’s not a huge surprise. Lisp is, as always, paren heavy. The little bit of IO syntax I see here doesn’t do it for me at all, but you probably expected that.

2. nukeedit
   Mike H said 6 days later:
   

   Ruby:

   class Array
     def qsort
       return self if empty?
       select { |x| x < first }.qsort + [first] + select { |x| x > first }.qsort
     end
   end
   

3. nukeedit
   Jules said about 1 month later:
   

   You can also use filter in Haskell:

   quicksort (x:xs) = quicksort (filter (< x) xs) 
                      ++ [x] ++ 
                      quicksort (filter (>= x) xs)
   

4. nukeedit
   killme2008@gmail.com said 7 months later:
   

   Ruby: def qsort(arr) if arr==[] [] else x=arr.shift smaller,bigger=arr.partition{|e| e<=x} qsort(smaller)+[x]+qsort(bigger) end end

   Erlang:

   sort([]) -> []; sort([Pivot|Rest]) -> {Smaller, Bigger} = lists:partition(fun(E)->E<Pivot end, Rest), lists:append(sort(Smaller), [Pivot|sort(Bigger)]).

5. nukeedit
   Will said 8 months later:
   

   Unfortunately, the Lisp one doesn’t work. Try it: => (quicksort ‘(2 3 59 12 2 13 2 34 7 9)) (2 2 2 2 2 2 2 3 7 9 12 13 34 59) I started with three twos, and ended up with 7.

6. nukeedit
   www.samsaffron.com/blog said 8 months later:
   

   This is quick sort in linq … still pretty ugly, but better than c# 2.0

   Func< IEnumerable < int>, IEnumerable< int>> sort = null;
   sort = list =>
       {
           if (list == null) return null; 
           if (list.Count() < 2) return list;
           var l1 =
               sort(from x in list.Skip(1) where x < list.First() select x).Concat(new int[] { list.First() }).Concat
               (sort(from x in list.Skip(1) where x >= list.First() select x));
           return l1;
       };

7. nukeedit
   JasonCornez said 9 months later:
   

   Here’s a common lisp version that both works, and is much prettier.

   (defun quicksort (l)
     (when l
       (destructuring-bind (x . xs) l
         (append (quicksort (remove x xs :test #'<=))
                 (list x)
                 (quicksort (remove x xs :test #'>))))))
   

8. nukeedit
   JoshAnderson said 9 months later:
   

   That lisp version is beautiful, but I want to rewrite it so that it only scans the list once for each call to (quicksort).

9. nukeedit
   noob said 9 months later:
   I’ve just started learning ocaml. This one should be a bit shorter (no need to filter twice).

   let rec quicksort = function
     | (x::xs) -> 
         let (lower,higher) = List.partition (fun i -> i < x) xs in
         quicksort1 lower  @ [x] @ quicksort1 higher
     | [] -> []
   ;;
   

   I hope it’s correct.
10. nukeedit
    sizur said about 1 year later:
    

    noob, how is the partition function implemented? i bet with two filters.

11. nukeedit
    camlrider said about 1 year later:
    

    sizur: nope

    let partition p l =
      let rec part yes no = function
      | [] -> (rev yes, rev no)
      | x :: l -> if p x then part (x :: yes) no l else part yes (x :: no) l in
      part [] [] l

12. nukeedit
    Jason said about 1 year later:
    

    ocaml seems to have list comprehensions now. I ran across this blog post trying to find more information

    #load "camlp4oof";;
    
    let rec quicksort = function
      | x :: xs -> 
          (quicksort [ i | i <- xs; i < x ]) 
          @ [x] @ 
          (quicksort [i | i <- xs; i >= x ])
      | [] -> []
    
    

13. nukeedit
    Daniel said about 1 year later:
    

    Quick sort in Python: http://dahoiv.net/programmering/uncategorized/quick-sort

14. nukeedit
    Kr said about 1 year later:
    

    (define (quicksort ls) (list-p (ls x xs ‘[]) (++ (quicksort [-> ls a (< a x)]) x (quicksort [-> ls a (>= a x)]))))

RSS feed for this post

Your name	(leave url/email »)
Your blog
Your email
Your message
Comment Markup Help Preview comment

Live Search:

About Me

Links

Syndicate

• Articles
• Comments