initial commit of sort.neb

1 files changed, 79 insertions, 0 deletions

diff --git a/libs/sort.neb b/libs/sort.neb
new file mode 100644
index 0000000..9fe20b7
--- /dev/null
+++ b/libs/sort.neb
@@ -0,0 +1,79 @@
+; sort.neb
+; an exploration of sorting algorithms in neb
+
+(func .prepend (lst item)
+    (list-reverse (append (list-reverse lst) item)))
+
+(func bubble (lst)
+    (def orig lst)
+    (def working (list))
+    (def swp #false)
+    (for-count (list-length lst)
+        (branch
+            ((eq? 0 (list-length (rest orig)))
+                (redef working (append working (first orig))))
+            ((> (first orig) (first (rest orig)))
+                (block
+                    (redef swp #true)
+                    (redef working (append working (first (rest orig))))
+                    (redef orig (.prepend (rest (rest orig)) (first orig)))))
+            (#true
+                (block
+                    (redef working (append working (first orig)))
+                    (redef orig (rest orig))))))
+
+    (print (->string working))
+    (if swp
+        (bubble working)
+        working))
+
+(func extend (lst1 lst2)
+    (def ret lst1)
+    (for-each lst2
+        (redef ret (append ret _item_)))
+    ret)
+
+(func insert (lst item)
+    (extend
+        (append (take-while lst (< _item_ item)) item)
+        (drop-while lst (< _item_ item))))
+
+(func insertion (lst)
+    (def ret (list))
+    (for-each lst
+        (redef ret (insert ret _item_))
+        (print (->string ret)))
+    ret)
+
+(func merge (lst)
+    (print (concat "sorting: " (->string lst)))
+    (if (eq? 1 (list-length lst))
+        lst
+        (block
+            (def half (floor (/ (list-length lst) 2)))
+            (def left (merge (slice lst 1 half)))
+            (def right (merge (slice lst (+ 1 half))))
+            (.merge left right))))
+
+(func .merge (lst1 lst2)
+    (print (concat "lst1: " (->string lst1)))
+    (print (concat "lst2: " (->string lst2)))
+    (def res (list))
+    (def w1 lst1)
+    (def w2 lst2)
+    (while (and (not (empty? w1)) (not (empty? w2)))
+        (if (< (first w1) (first w2))
+            (block
+                (redef res (append res (first w1)))
+                (redef w1 (rest w1)))
+            (block
+                (redef res (append res (first w2)))
+                (redef w2 (rest w2)))))
+    (while (not (empty? w1))
+        (redef res (append res (first w1)))
+        (redef w1 (rest w1)))
+
+    (while (not (empty? w2))
+        (redef res (append res (first w2)))
+        (redef w2 (rest w2)))
+    res)