tag:blogger.com,1999:blog-2964959029992147971.post8452739576925498460..comments2024-02-12T20:14:00.868+05:30Comments on InstanceOfJava: Quicksort algorithm in java with example programsaideshhttp://www.blogger.com/profile/03671387577197113199noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-2964959029992147971.post-79727971512863395982018-06-21T23:04:12.842+05:302018-06-21T23:04:12.842+05:30I devised a sort to maximize Locality of Reference...I devised a sort to maximize Locality of Reference (cache, RAM hits). One just considers the input a list of N 1 element sorted linked lists, then merge the first two replacing them (2-list) in the list, then the next two replacing them (2-list) in the list, the the first two replacing them (4-list) in the list, etc. The current count of items processed tells you when to merge which, using low order bits (4 has two low zeros, so merge twice). Since the size of the lists being merged grows by a factor of 2, gradually, cache and RAM hits are maximized. When RAM is outstripped, the work in the disk files is mostly sequential, merging two lists, which is efficient in that medium, too.<br /><br />Dropping the items into a tree is also popular, probably O(log(n)).<br /><br />I devised what I call a C-Tree, where the tree has default nodes of 256 pointers or references, with alternative nodes of N bytes must equal (to span invariant prefixes, suffixes, or infixes), short arrays from N for M items (good for numbers or letters of one case), unsorted lists with a key char array (good for positions with a few non-adjacent values in use). This way, there is no overhead to keep the tree balanced, and the char/string flavored instruction set is exploited. There is overhead to convert nodes from must equal to unsorted keyed list to sorted array size M to sorted array 256, as items are added to the tree. All trees worth using have some sort of tree balancing overhead. Here, it is kept small, compared to, for instance, sliding all the elements of half a huge array up to make room for a single item insert.<br /><br />I would love to see some run time comparisons for varying size and disorder lists. Some sorts make superior use of inputs already containing largely or completely sorted data.Anonymoushttps://www.blogger.com/profile/13797335929885750253noreply@blogger.com