blob: 081a678ebd3f602e2522e3d351fd38ee6c331efe (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
; sort.neb
; an exploration of sorting algorithms in neb
(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 insertion-reduce (lst)
(reduce insert lst (list)))
(func extend-reduce (lst1 lst2)
(reduce append lst2 lst1))
(func extend (lst1 lst2)
(def ret lst1)
(for-each lst2
(redef ret (append ret _item_)))
ret)
(func .insert-num (lst item)
(extend-reduce
(append (take-while lst (<= _item_ item)) item)
(drop-while lst (<= _item_ item))))
(func .insert-string (lst item)
(extend-reduce
(append (take-while lst (strcmp _item_ item)) item)
(drop-while lst (strcmp _item_ item))))
;(func insertion-reduce (lst)
; (reduce insert lst (list)))
(func insertion-strings (lst)
(reduce .insert-string lst (list)))
(func insertion-nums (lst)
(reduce .insert-num lst (list)))
(func insertion-iter (lst)
(def ret (list))
(for-each lst
(redef ret (.insert-num 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)
(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))))))
(func strcmp (left :string right :string)
(branch
((or
(eq? 0 (length left))
(eq? 0 (length right)))
(<= (length left) (length right)))
((eq? (first-char left) (first-char right))
(strcmp (rest-char left) (rest-char right)))
(#true
(<= (ord (first-char left)) (ord (first-char right))))))
|
