diff options
author | Jakob Kaivo <jkk@ung.org> | 2022-03-04 12:32:20 -0500 |
---|---|---|
committer | Jakob Kaivo <jkk@ung.org> | 2022-03-04 12:32:20 -0500 |
commit | 55f277e77428d7423ae906a8e1f1324d35b07a7d (patch) | |
tree | 5c1c04703dff89c46b349025d2d3ec88ea9b3819 /miralib/ex/treesort.m |
import Miranda 2.066 from upstream
Diffstat (limited to 'miralib/ex/treesort.m')
-rw-r--r-- | miralib/ex/treesort.m | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/miralib/ex/treesort.m b/miralib/ex/treesort.m new file mode 100644 index 0000000..e5b946b --- /dev/null +++ b/miralib/ex/treesort.m @@ -0,0 +1,20 @@ +|| Here is another sorting algorithm, this time treesort. +|| to try it out, say: treesort testdata + +tree * ::= NILT | NODE * (tree *) (tree *) + +treesort = flatten.build + +build::[*]->tree * +build = foldr insert NILT + +insert b NILT = NODE b NILT NILT +insert b (NODE a x y) = NODE a (insert b x) y, if b<=a + = NODE a x (insert b y), if b>a + +flatten::tree *->[*] +flatten NILT = [] +flatten (NODE a x y) = flatten x ++ [a] ++ flatten y + +testdata = [1..5]++[20,19..16]++[6..10]++[15,14..11] + |