ref: 3abec38baad46bc1317fc8a8b9c1fdd38494aef4
parent: 64e3b36c8a1cc2c10248a4761e092234b8eccfe2
author: Ori Bernstein <[email protected]>
date: Mon Dec 30 18:04:29 EST 2013
Implement heapsort and add to libstd.
--- a/libstd/Makefile
+++ b/libstd/Makefile
@@ -25,6 +25,7 @@
sljoin.myr \
slpush.myr \
slurp.myr \
+ sort.myr \
strfind.myr \
strjoin.myr \
strsplit.myr \
--- /dev/null
+++ b/libstd/sort.myr
@@ -1,0 +1,63 @@
+pkg std =
+ type order = union
+ `Before
+ `Equal
+ `After
+ ;;
+ generic sort : (sl:@a[:], cmp:(a:@a, b:@a -> order) -> @a[:])
+;;
+
+generic sort = {sl, cmp+ var end
+
+ heapify(sl, cmp)
+ end = sl.len - 1
+ while end > 0
+ swap(sl, end, 0)
+ end--
+ siftdown(sl[:end], 0, cmp)
+ ;;
+ -> sl
+}
+
+generic heapify = {sl, cmp+ var start
+
+ start = sl.len/2 - 1
+ while start >= 0
+ siftdown(sl, start, cmp)
+ start--
+ ;;
+}
+
+generic siftdown = {sl, start, cmp+ var r, c, s
+
+ r = start
+ while 2*r + 1 <= sl.len
+ c = r*2 + 1
+ s = r
+ match cmp(sl[s], sl[c])
+ | `Before: s = c
+ ;;
+ if c + 1 < sl.len
+ match cmp(sl[s], sl[c + 1])
+ | `Before: s = c + 1
+ ;;
+ ;;
+ if s != r
+ swap(sl, r, s)
+ r = s
+ else
+ ->
+ ;;
+ ;;
+}
+
+generic swap = {sl, i, j+ var tmp
+ tmp = sl[i]
+ sl[i] = sl[j]
+ sl[j] = tmp
+}
+
--- /dev/null
+++ b/test/data/stdsort-expected
@@ -1,0 +1,10 @@
+0
+2
+1
+3
+4
+5
+6
+7
+8
+9
--- /dev/null
+++ b/test/stdsort.myr
@@ -1,0 +1,24 @@
+use std
+
+const main = {+ var a = [
+ 3, 5, 4, 9, 7, 2, 6, 0, 1, 8,
+ ]
+
+ std.sort(a[:], intcmp)
+ for i in a
+ std.put("%i\n", i)+ ;;
+}
+
+const intcmp = {a, b+ if a < b
+ -> `std.Before
+ elif a == b
+ -> `std.Equal
+ else
+ -> `std.After
+ ;;
+}
+
+
--- a/test/tests
+++ b/test/tests
@@ -108,6 +108,7 @@
B encodechar P 1世界äa
B strtab C
B catfile C
+B stdsort C
B strstrip C
B strsplit C
B strfind C