h1. Sorting Big Numbers using Trie-Forest based sort

Sorting Big Numbers using Trie-Forest based search
 
authors : Serban Lupulescu and Mircea Dima

h2. authors : Serban Lupulescu and Mircea Dima

The first idea is that if you have a string of length h, you can insert it in a trie of height h. We could maintain a list of tries,

h3. The first idea is that if you have a string of length h, you can insert it in a trie of height h. We could maintain a list of tries,

trie H[N], where H[i] is a trie with height i so when we insert a string with lenght i, we insert it in H[i].

h3. trie H[N], where H[i] is a trie with height i so when we insert a string with length i, we insert it in H[i].

But what happens when we have, say 2 strings, one of length 3, and one with length 10^20? We can't declare H[10^20].

h3. But what happens when we have, say 2 strings, one of length 3, and one with length 10^20^? We can't declare H[10^20^].

Instead we can keep an optimal binary search tree, where the keys are the length of the trie, and the additional information is the

h3. Instead we can keep an optimal binary search tree, where the keys are the length of the trie, and the additional information is the

trie itself.

h3. trie itself.

Now if we have a string with length h we have 2 possibilities:

h3. Now if we have a string with length h we have 2 possibilities:

1) if there is a trie with height h in the binary search tree, we insert the string in that trie

h3. 1) if there is a trie with height h in the binary search tree, we insert the string in that trie

2) if there isn't a trie with height h in the binary search tree, we create it, we insert the string, and then we insert the trie in

h3. 2) if there isn't a trie with height h in the binary search tree, we create it, we insert the string in an empty trie, and then we insert the trie in

the binary search tree.

h3. the binary search tree.
 
 
== code(c) |

 
==code(c) |

// Sorting Big Numbers using Trie-Forest based sort indexed in a STL set (Red-Black Tree)

// copyright   idea :          Serban Lupulescu
//             implementation: Mircea Dima

// copyright(c) Serban Lupulescu & Mircea Dima

// Time Complexity: O(n*max_len)
// Faculty of Mathematics and Computer Science, University of Bucharest
// :D

#include <string>
#include <set>
#include <vector>

#define maxh 666013

#define N 10024
using namespace std;

      return n;
}

struct nod { int nr; nod *next[10];};
typedef nod* trie;

{
      for(int i=0; i < n; ++i)
      {

            if(T->next[a[i]] == 0)
            //if I don't have an edge, I creat it

            if(T->next[a[i]] == 0) //if I don't have an edge, I create it

            {
                  T->next[a[i]]=new nod;
                  T->next[a[i]]->nr=0;

            {
                  sol[n]=i;

                  if(T->next[i]->nr)//has a number ended?

                  if(T->next[i]->nr)//has a number ended here?

                  {
                        for(int j=1; j <= T->next[i]->nr; ++j)
                        {

      read();
      return 0;
}

 
 ==

==