h1. Sorting Big Numbers using Trie-Forest based sort

Sorting Big Numbers using Trie-Forest based search

h2. authors : Serban Lupulescu and Mircea Dima

authors : Serban Lupulescu and Mircea Dima

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,

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. 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].

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. 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^].

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. Instead we can keep an optimal binary search tree, where the keys are the length of the trie, and the additional information is the

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. trie itself.

trie itself.

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

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

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

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

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
 
h3. the binary search tree.

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
the binary search tree.
 

== code(c) |

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

// copyright(c) Serban Lupulescu & Mircea Dima

// copyright   idea :          Serban Lupulescu
//             implementation: 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 create it

            if(T->next[a[i]] == 0)
            //if I don't have an edge, I creat 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 here?

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

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

      read();
      return 0;
}

==

 
 ==