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



Re: Just finished the fastest ever, general purpose sorting algorithm.
Posted:
Jan 8, 2013 9:18 PM


On Monday, January 7, 2013 6:39:50 AM UTC5, JT wrote: > 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.
Can you prove that quicksort won't beat your algorithm like a drum on random input instances?
Benchmark it.



