Skip to content

Instantly share code, notes, and snippets.

@duarten
Created June 19, 2011 22:03
Show Gist options
  • Save duarten/1034830 to your computer and use it in GitHub Desktop.
Save duarten/1034830 to your computer and use it in GitHub Desktop.
A lazy quick sort
(ns sort
(:use clojure.test))
(defn qsort [xs]
"Sorts the specified sequence using the quick sort algorithm"
(if-let [[pivot & rest] (seq xs)]
(let [smaller? #(< % pivot)]
(lazy-cat (qsort (filter smaller? rest))
[pivot]
(qsort (remove smaller? rest))))))
(testing "qsort"
(testing "with empty sequence"
(is (= (qsort []) (seq []))))
(testing "with unsorted sequence"
(is (= (qsort [3, 2, 1, 4, 2]) [1, 2, 2, 3, 4]))))
public static IEnumerable<T> LazyQsort<T>(IEnumerable<T> seq, Func<T, T, bool> comp)
{
if (seq.Any() == false)
{
return new T[0];
}
var pivot = seq.First();
var xs = seq.Skip(1);
return LazyQsort(xs.Where(x => comp (x, pivot)), comp)
.Union(new[] { pivot })
.Union(LazyQsort(xs.Where(x => !comp (x, pivot)), comp));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment