sorting.quick: adding a Quicksort implementation.

diff --git a/extra/sorting/quick/authors.txt b/extra/sorting/quick/authors.txt
new file mode 100644 (file)
index 0000000..e091bb8
--- /dev/null
+++ b/extra/sorting/quick/authors.txt
@@ -0,0 +1 @@
+John Benediktsson

diff --git a/extra/sorting/quick/quick-tests.factor b/extra/sorting/quick/quick-tests.factor
new file mode 100644 (file)
index 0000000..1afb80c
--- /dev/null
+++ b/extra/sorting/quick/quick-tests.factor
@@ -0,0 +1,6 @@
+USING: kernel tools.test ;
+IN: sorting.quick
+
+{ { } } [ { } dup quicksort ] unit-test
+{ { 1 } } [ { 1 } dup quicksort ] unit-test
+{ { 1 2 3 4 5 } } [ { 1 4 2 5 3 } dup quicksort ] unit-test

diff --git a/extra/sorting/quick/quick.factor b/extra/sorting/quick/quick.factor
new file mode 100644 (file)
index 0000000..df8d935
--- /dev/null
+++ b/extra/sorting/quick/quick.factor
@@ -0,0 +1,37 @@
+! Copyright (C) 2014 John Benediktsson
+! See http://factorcode.org/license.txt for BSD license
+
+USING: combinators kernel locals math math.order sequences
+sequences.private ;
+
+IN: sorting.quick
+
+<PRIVATE
+
+:: (quicksort) ( seq from to -- )
+    from to < [
+        from to + 2/ :> p
+        from :> l!
+        to :> r!
+
+        p seq nth-unsafe :> p-nth
+
+        [ l r <= ] [
+            [ l seq nth-unsafe p-nth before? ] [ l 1 + l! ] while
+            [ r seq nth-unsafe p-nth after? ] [ r 1 - r! ] while
+            l r <= [
+                l r seq exchange-unsafe
+                l 1 + l!
+                r 1 - r!
+            ] when
+        ] while
+
+        seq from r (quicksort)
+        seq l to (quicksort)
+
+    ] when ; inline recursive
+
+PRIVATE>
+
+: quicksort ( seq -- )
+    0 over length 1 - (quicksort) ;

diff --git a/extra/sorting/quick/summary.txt b/extra/sorting/quick/summary.txt
new file mode 100644 (file)
index 0000000..e245fd3
--- /dev/null
+++ b/extra/sorting/quick/summary.txt
@@ -0,0 +1 @@
+Quicksort