Sorting algorithms/Tree sort on a linked list: Difference between revisions
Content added Content deleted
m (J: might be worth doing this one right? the binary tree pointers are the temporary data structure being sorted here, cost is higher sorting all at once because many need multiple updates, but this is a way to cut down accumulated costs of successive sorts) |
(J: cave and do a "legit" [in-?] efficient binary search tree) |
||
| Line 49: | Line 49: | ||
(Processing time here is negligible - other than the time needed to fetch a copy of the book and render it as plain text ascii - but if we were careful to implement the efficiency recommendations of this task more in the spirit of whatever the task is presumably implying, we could probably increase the processing time by several orders of magnitude.) |
(Processing time here is negligible - other than the time needed to fetch a copy of the book and render it as plain text ascii - but if we were careful to implement the efficiency recommendations of this task more in the spirit of whatever the task is presumably implying, we could probably increase the processing time by several orders of magnitude.) |
||
So... ok... let's do this "right" (which is to say according to the current task specification, as opposed to the task specification that was present for the early drafts - though, perhaps, using Finnegan's Wake as a data set encourages a certain degree of ... informality?). |
|||
Anyways, here we go: |
|||
<lang J>left=: i.0 |
|||
right=: i.0 |
|||
data=: i.0 |
|||
insert=:3 :0"0 |
|||
k=. 0 |
|||
assert. (left =&# right) * (left =&# data) |
|||
if. 0<#data do. |
|||
while. k<#data do. |
|||
if. y=k{data do.return.end. |
|||
n=. k |
|||
if. y<k{data do. |
|||
k=. k{".p=.'left' |
|||
else. |
|||
k=. k{".p=.'right' |
|||
end. |
|||
end. |
|||
(p)=:(#data) n} ".p |
|||
end. |
|||
left=:left, _ |
|||
right=:right, _ |
|||
data=:data,y |
|||
i.0 0 |
|||
) |
|||
flatten=:3 :0 |
|||
extract 0 |
|||
) |
|||
extract=:3 :0 |
|||
if. y>:#data do.'' return. end. |
|||
(extract y{left),(y{data),extract y{right |
|||
)</lang> |
|||
This could be wrapped differently, but it's adequate for this task. |
|||
Example use would be something like: |
|||
<lang j> insert sentences |
|||
extract''</lang> |
|||
But the current url no longer points at flat text for finnegan's wake and constructing such a thing would be a different task... |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||