diff options
| -rw-r--r-- | libs/sort.neb | 35 |
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)))))) |