Rosetta Code

Sorting algorithms/Tree sort on a linked list: Difference between revisions

Page Discussion

Sorting algorithms/Tree sort on a linked list (view source)

Revision as of 21:44, 5 November 2018

243 bytes removed ,  5 years ago
updated task description
(updated task description)
Line 11:
[[Sorting_algorithms#Sediment sort|Sediment sort]], [[Sorting_algorithms#bubble sort|bubble sort]], [[Sorting_algorithms#selection sort|selection sort]] perform very badly.
 
'''Task:'''<br>
'''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.)
First, construct a doubly linked list (unsorted).<br>
Then construct a tree in situ: use the prev and next of that list as left and right tree pointers.<br>
Then traverse the tree, in order, and recreate a doubly linked list, again in situ, but of course now in sorted order.
 
=={{header|J}}==
Petelomax
7,820

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/245163"