Talk:Sorting algorithms/Tree sort on a linked list: Difference between revisions
Content added Content deleted
(→I don't understand this task: comment on linked list sorting and performance reporting) |
|||
| Line 4: | Line 4: | ||
: The Ching-Kuang Shene paper linked to in the task mentions having an existing doubly linked list that is temporarily reused to build up a new tree via insertion sort. Reused in the sense that while building the tree the existing <code>prev</code> and <code>next</code> node pointers are used as if they were <code>left</code> and <code>right</code> node pointers to the sub-trees. Once the tree is assembled it is straight forward to traverse the tree in-order setting the node pointers such that it is once again a doubly linked list but now sorted. |
: The Ching-Kuang Shene paper linked to in the task mentions having an existing doubly linked list that is temporarily reused to build up a new tree via insertion sort. Reused in the sense that while building the tree the existing <code>prev</code> and <code>next</code> node pointers are used as if they were <code>left</code> and <code>right</code> node pointers to the sub-trees. Once the tree is assembled it is straight forward to traverse the tree in-order setting the node pointers such that it is once again a doubly linked list but now sorted. |
||
: —[[User:dchapes|dchapes]] ([[User talk:dchapes|talk]] | [[Special:Contributions/dchapes|contribs]]) 15:26, 12 July 2018 (UTC) |
: —[[User:dchapes|dchapes]] ([[User talk:dchapes|talk]] | [[Special:Contributions/dchapes|contribs]]) 15:26, 12 July 2018 (UTC) |
||
:: Ah, I knew there was a reason this had appeared on my radar (ignore the Phix entry for now, I'll replace it). I propose replacing the "Test case" paragraph with |
|||
Task: |
|||
First, construct a doubly linked list. |
|||
Then construct a tree in situ: use the prev and next of that list as left and right tree pointers. |
|||
Then traverse the tree, in order, and recreate a doubly linked list, again in situ, but of course now in sorted order. |
|||
:: —[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 08:15, 5 November 2018 (UTC) |
|||
The proposed task talks about performance. This is a Bad Idea because it's next to impossible to compare performance between systems (different CPU speeds, different memory bandwidths, different loading patterns, etc.) Talking about performance strongly encourages people to try to “optimise” their implementations, which tends to make them significantly less readable and less idiomatic. Finally, actually measuring performance fairly and accurately is hard; there are lies, damned lies, and benchmarks. –[[User:Dkf|Donal Fellows]] ([[User talk:Dkf|talk]]) 10:49, 11 May 2014 (UTC) |
The proposed task talks about performance. This is a Bad Idea because it's next to impossible to compare performance between systems (different CPU speeds, different memory bandwidths, different loading patterns, etc.) Talking about performance strongly encourages people to try to “optimise” their implementations, which tends to make them significantly less readable and less idiomatic. Finally, actually measuring performance fairly and accurately is hard; there are lies, damned lies, and benchmarks. –[[User:Dkf|Donal Fellows]] ([[User talk:Dkf|talk]]) 10:49, 11 May 2014 (UTC) |
||