Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: Just finished the fastest ever, general purpose sorting algorithm.
Posted:
Jan 8, 2013 10:21 PM
|
|
On Tuesday, January 8, 2013 6:18:30 PM UTC-8, Kiru Sengal wrote:
> On Monday, January 7, 2013 6:39:50 AM UTC-5, JT wrote:
>
> > 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.
>
>
>
> Can you prove that quicksort won't beat your algorithm like a drum on random input instances?
>
>
>
> Benchmark it.
On the dataset he gave in another post it will beat quicksort.
Or so I believe. "Cherry picked" comes to mind. There is a
narrow band of datasets where his algorithm will beat quicksort.
|
|
|
|
