Math Forum Discussions

JT

Posts: 436
Registered: 4/7/12

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

Plain Text

On 7 Jan, 07:17, forbisga...@gmail.com wrote:
> On Sunday, January 6, 2013 7:32:45 PM UTC-8, 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, B-tree, 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 b-tree 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.