Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
JT
Posts:
436
Registered:
4/7/12
|
|
Re: Just finished the fastest ever, general purpose sorting algorithm.
Posted:
Jan 5, 2013 5:32 PM
|
|
YOn 5 Jan, 18:27, David Bernier <david...@videotron.ca> wrote:
> On 01/05/2013 10:22 AM, JT wrote:
>
>
>
>
>
>
>
>
>
> > I do intend to implement this one, i think it will beat any other
> > algorithm for any amount of elements *and element size* when sorting
> > above 2000-3000 elements. I can not guarantee it will not be faster at
> > smaller amount of data too...
>
> > By creating a pointer binary tree with each leaf holding a
> > integer, you move the binary numbers to the tree from least digit to
> > highest using left legs for 0's and right for 1's. (Basicly creating
> > leaves for new numbers, and at last digit you add 1 to the leaf
> > slot.
> > So after you moved all values into the tree and created all the
> > nodes,
> > you simply read out all the none zero values holded into the slot
> > of
> > the leaves within the binary tree.
>
> > Now to the problem and solution, using a tree reading in the values,
> > they will not be read in from lowest to highest because the legs will
> > differ in length and they will be unordered in the tree. The solution
> > to the problem we create a single leg (heap) ***for each digit***, so
> > numbers with digit 9,10,11.... digits and so on run in their own legs.
> > Our binary tree will be sorted as we read in the values and we just
> > need to read it out from left to right. This is probably within the
> > first courses of information theory, so the question is why have this
> > not been applied to sorting problems before?
>
> > Can anyone estimate the time complexity of this algorithm, and it seem
> > to be a general purpose algorithm, the biggest challenge will be to
> > find a programming language that have dynamic memory for data
> > structures of binary tree type.
>
> > Is this also a radix type of sorting?
>
> Hi,
>
> I don't fully understand your problem statement. The legs are probably
> what in English are called branches of the tree.
>
> In a course on file system structures, we studied AVL trees,
> which I think are useful in huge databases, for faster access
> by "key number", for example social security number, employee number,
> membership number, etc.
>
> On Wikipedia, AVL trees (& References at the end of the article).
>
> <http://en.wikipedia.org/wiki/AVL_tree> .
>
> David Bernier
Yes every/each digit sized number/element run in its own branch of
tree thereforr the tree is already sorted when you have read in all
values. All you have to do is to read out the trees from left to
right. Not a single comparisson needed, and unlike the array variant
of count sort i created, this will only need space as you allocate a
new element in tree. One leaf is holding the reocurresense of a value
by just adding occurences.
As i said i do not know the time complexity of the algorithm but it
is so much faster then any other sorting algorithm "other then my
countsort" that it probably will yield other sorting algorithms
obsolete for other then teaching purposes.
|
|
|
|
