Sorting algorithms/Tree sort on a linked list: Difference between revisions
Content added Content deleted
m (fix gramma) |
No edit summary |
||
| Line 9: | Line 9: | ||
'''Test case:''' Create a linked list of all the sentences of all the episodes of [http://www.telelib.com/authors/J/JoyceJames/prose/finneganswake Finnegans Wake by James Joyce]. Load them into a local memory based linked list, then tree sort them inplace and print the number of node swaps and seconds of [[wp:BogoMips|BogoMips]] are necessary to perform the sort. (The book is to be stored locally (whole ''or'' in individual episodes) in a test text file on disk before loading by the specimin code into a linked list for sorting.) |
'''Test case:''' Create a linked list of all the sentences of all the episodes of [http://www.telelib.com/authors/J/JoyceJames/prose/finneganswake Finnegans Wake by James Joyce]. Load them into a local memory based linked list, then tree sort them inplace and print the number of node swaps and seconds of [[wp:BogoMips|BogoMips]] are necessary to perform the sort. (The book is to be stored locally (whole ''or'' in individual episodes) in a test text file on disk before loading by the specimin code into a linked list for sorting.) |
||
=={{header|Scheme}}== |
|||
The following implements a sorting algorithm that takes a linked list, puts each key into an unbalanced binary tree and returns an in-order traversal of the tree. |
|||
{{libheader|Matchable}} |
|||
{{works with|Chicken Scheme}} |
|||
<lang Scheme>(use matchable) |
|||
(define insert |
|||
;; (insert key tree) |
|||
(match-lambda* |
|||
[(x ()) `(() ,x ()) ] |
|||
[(x (() () ())) `(() ,x ()) ] |
|||
[(x (l k r)) |
|||
(=> continue) |
|||
(if (<= x k) |
|||
`(,(insert x l) ,k ,r) |
|||
(continue)) ] |
|||
[(x (l k r)) `(,l ,k ,(insert x r)) ] |
|||
[_ "incorrect arguments or broken tree" ])) |
|||
(define in-order |
|||
;; (in-order tree) |
|||
(match-lambda |
|||
[(() x ()) `(,x)] |
|||
[(l x ()) (append (in-order l) `(,x))] |
|||
[(() x r) (append `(,x) (in-order r))] |
|||
[(l x r) (append (in-order l) `(,x) (in-order r))] |
|||
[_ "incorrect arguments or broken tree" ])) |
|||
(define (tree-sort lst) |
|||
(define tree-sort-itr |
|||
(match-lambda* |
|||
[(x ()) (in-order x)] |
|||
[(x (a . b)) (tree-sort-itr (insert a x) b)] |
|||
[_ "incorrect arguments or broken tree" ])) |
|||
(tree-sort-itr '(() () ()) lst))</lang> |
|||
Usage: <lang Scheme> #;2> (tree-sort '(5 3 7 9 1)) |
|||
(1 3 5 7 9)</lang> |
|||