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
|
|
Just finished the fastest ever, general purpose sorting algorithm.
Posted:
Jan 5, 2013 10:22 AM
|
|
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?
|
|
|
|
