implement quicksort

1 files changed, 35 insertions, 0 deletions

diff --git a/libs/sort.neb b/libs/sort.neb
index 9fe20b7..e5a7eb5 100644
--- a/libs/sort.neb
+++ b/libs/sort.neb
@@ -77,3 +77,38 @@
         (redef res (append res (first w2)))
         (redef w2 (rest w2)))
     res)
+
+(func quick (lst)
+    (branch
+        ((eq? 1 (list-length lst)) lst)
+        ((eq? 2 (list-length lst))
+            (if (<= (first lst) (first (rest lst)))
+                lst
+                (list-reverse lst)))
+        (#true
+            (block
+                ; 1. pick the last element as a pivot
+                ; 2. consider all but the pivot
+                ; 3. starting from the first
+                ;   > if the element is less than or equal to the pivot, remove it from consideration and add it to "before"
+                ;   > otherwise, add the element as the first element of "after", and swap the last element of consideration with the (new) first element of consideration
+                ;   > once there's nothing left to consider, run quicksort on the beginning and the end, and put the pivot in the middle
+                (def before (list))
+                (def after (list))
+                (def consider (list-reverse (rest (list-reverse lst))))
+                (def pivot (last lst))
+                (while (not (empty? consider))
+                    (if (<= (first consider) pivot)
+                        (block
+                            (redef before (append before (first consider)))
+                            (redef consider (rest consider)))
+                        (block
+                            (redef after (.prepend after (first consider)))
+                            (if (eq? 1 (list-length consider))
+                                (redef consider (list))
+                            (redef consider
+                                (.prepend (list-reverse (rest (list-reverse (rest consider)))) (last consider))))))
+                    (print (concat "before: " (->string before)))
+                    (print (concat "after: " (->string after)))
+                    (print (concat "consider: " (->string consider))))
+                (extend (append (quick before) pivot) (quick after))))))