Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Another count sort that certainly must exist, it do not have any
restrictions upon size of (S number of possibilities)

Replies: 11   Last Post: Jan 8, 2013 1:37 AM

 Messages: [ Previous | Next ]
 JT Posts: 1,434 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 8, 2013 1:37 AM

On 8 Jan, 07:15, Kiru Sengal <kiru.sen...@gmail.com> wrote:
> On Friday, January 4, 2013 9:46:30 AM UTC-5, JT 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.
>
> It's called BST sort.
> Make each node count frequency along with key value of numbers.
> Then at the end do an in order traversal, but print out each key its "frequency" number of times.
>
>
>
>
>
>
>
>
>

> > 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?

Well actually it is not bucketsort or radixsort, because there each
index have an equipped dataset, that need to be sorted after each
occurence have been counted in.
This is a variant with just indexing no aftersort of the dataset, the
math/crypto community come up with names for anything they like to
make their own invention rather then using the one given, but actually
it is just countsort/JTsort.

Date Subject Author
1/4/13 JT
1/4/13 JT
1/4/13 JT
1/4/13 David Bernier
1/4/13 JT
1/4/13 David Bernier
1/4/13 David Bernier
1/4/13 JT
1/4/13 JT
1/4/13 David Bernier
1/8/13 kiru.sengal@gmail.com
1/8/13 JT