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: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)
Posted:
Jan 4, 2013 10:46 AM
|
|
On 4 Jan, 15:46, JT <jonas.thornv...@gmail.com> wrote:
> I remember doing this in a tentamen during my education in information
> theory beleiving what i did was binary sort but my teacher informed me
> it wasn't so what is it.
> By creating a Pascal 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.
>
> What is this sort called?
> Of course you cannot have more leaves then memory, but this does not
> need to hold memory for slots never used like the array slots, it is
> therefore my beleif that this sort could be useful also for database
> purposes sorting basicly anything. What do you think?
I can see there would be problems reading out the sizes of a binary
tree from smallest to biggest, if you have legs with different
lengths? Is there any algorithmic solution to this problem.
I have kind of a foul play solution, you create a binary tree for
every digit bigger then 2^20 the smaller ones you run with the array
approach. So for 21,22,23... bits and so on each numbers run on their
own computers, with 2048 computers you could sort enormous amount of
data of different size. So basicly the "heaps?" all have legs with
same sizes and is easy to read out in order.
Is this a working idea or just plain silly, maybe it is just easier to
use one computer and read out the values from the heap and sort them
with quicksort after you filled up the tree? (Is it called tree or
heap, what is the difference betwee a heap and a tree?).
So what you think about the mix using this kind of sort for counting
in values, and then quicksort to sort the none null tree nodes by
sizes.
|
|
|
|
