Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Just finished the fastest ever, general purpose sorting algorithm.
Replies:
29
Last Post:
Jan 8, 2013 10:21 PM



JT
Posts:
1,448
Registered:
4/7/12


Re: Just finished the fastest ever, general purpose sorting algorithm.
Posted:
Jan 7, 2013 6:39 AM


On 7 Jan, 07:17, forbisga...@gmail.com wrote: > On Sunday, January 6, 2013 7:32:45 PM UTC8, JT wrote: > > No a dynamic alloc memory pointer solution using a binary tree will > > not have any empty indeces. > > Why do you think I pointed you at the page for the binary insertion sort? > How do you pass through the binary tree without comparisons? Even if you > do dynamic leveling it takes time and the results will depend upon the order > in the "unordered" set. > > The old Burroughs DMSII database supported ISAM, Btree, and hash access > methods to retrieve data. Each had their place. Hash was by far the fastest > access as long as one didn't have too many overflow pages but it wasn't very > good for sequential access of the data and the data wasn't ordered other than > by hash algorithm. > > It's interesting that SQLServer seems to handle ordered insertion into > a btree much faster than the Unisys DMSII did. It seems to keep more > information lying around. Maybe it just keeps more of the index in memory. > Back in the day 64K was a lot of memory, now we're thowing 10s of G at > machines. I don't really know and don't care as long as the results > are satisfactorally fast. I can import millions of records in a few > minutes and that's good enough. I can keep several indexes on huge > tables and get the data back out very quickly. That's good enough for > me. I don't care to know the specifics of the system's internals unless > performance is suffering. > > You don't know what you're talking about. You talk like a beginner. > I don't like responding this way to anyone because I don't like being > responded to this way by anyone. Everyone's a beginner at something. > Go read up on sorts then try writing your own. You're not up to speed > on the basics yet. There's nothing worse than a rude beginner. http://en.wikipedia.org/wiki/Sorting_algorithm#Counting_sort Counting sort Main article: Counting sort Counting sort is applicable when each input is known to belong to a particular set, S, of possibilities. The algorithm runs in O(S + n) time and O(S) memory where n is the length of the input. It works by creating an integer array of size S and using the ith bin to count the occurrences of the ith member of S in the input. Each input is then counted by incrementing the value of its corresponding bin. Afterward, the counting array is looped through to arrange all of the inputs in order. This sorting algorithm cannot often be used because S needs to be reasonably small for it to be efficient, but the algorithm is extremely fast and demonstrates great asymptotic behavior as n increases. It also can be modified to provide stable behavior.
***So as you can see the implementation of this algoritm that i showed to numbnuts work in index style, by first counting occurences this means comparissons and have restrictions upon setsize(unique members) due to memory restrictions, and they ***will also have to sort those members after they have been counted in*** to their respective indexes in array. And this is very bad if all values have low number of occurences.
As you can see my pet array algorithm do no such thing because it just use the array index so there will be no sort needed. Now the pet array algorithm of course have it weakness that possibly no more then 2^20 elements can be created in most programming languages, this means without index approach only elements of max 2.5 character could be stored. And that would not be much use for sorting text (unless you chose the index solution).
However a recursive pointer solution with digit branches do not need to allocate slots for null values so would not need to have any restrictions upon size of elements as long there is system memory to store each unique value and the occurences of it, so basicly anything can be indexed without any sort needed.



