Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-01-28 16:27:51.
Revizia anterioară   Revizia următoare  

Sorting Big Numbers using Trie-Forest based sort

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,

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 1020? We can't declare H[1020].

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.

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

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.

// Sorting Big Numbers using Trie-Forest based sort indexed in a STL set (Red-Black Tree)
// copyright(c)   idea :          Serban Lupulescu
 & Mircea Dima
// Time Complexity: O(n*max_len)
// Faculty of Mathematics and Computer Science, University of Bucharest
// :D
#include <cstdio>
#include <string>
#include <set>
#include <vector>
#define N 10024

using namespace std;

inline int length(char a[])
{
      int n=0;
      while(a[n] >= '0' && a[n] <= '9') ++n;
      return n;
}

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

typedef nod* trie;

inline void init(trie &n)
{
      n=new nod;
      n->nr=0;
      memset(n->next, 0, sizeof(n->next));
}

struct cmp{
      bool operator()(const pair<int, trie> &a, const pair<int, trie> &b)const
      {
            if(a.first < b.first) return 1;
            return 0;
      }
};

typedef set<pair<int, trie> , cmp > Tree;
typedef set<pair<int, trie> , cmp >:: iterator Tree_it;

 

Tree R; // Red-Black binary search tree with key values = pointers

inline trie find(int len) // find a trie in RBTREE
{
      Tree_it i= R.find(make_pair(len, (trie)0));
      if(i == R.end()) return (trie) 0;
      return i->second;
}

inline void insert(trie t, int len)
{
      R.insert(make_pair(len, t));
}

inline void erase(trie t, int len)
{
      R.erase(make_pair(len, t));
}

inline void insert(trie T,char a[], int n)
{
      for(int i=0; i < n; ++i)
      {
            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;
                  memset(T->next[a[i]]->next, 0, sizeof(T->next));
            }
            T=T->next[a[i]]; // go down the edge
      }          
      ++T->nr;
}

char sol[N];

inline void afis(trie T, int n)
{
      for(int i=0; i < 10; ++i)
            if(T->next[i])
            {
                  sol[n]=i;
                 
                  if(T->next[i]->nr)//has a number ended here?
                  {
                        for(int j=1; j <= T->next[i]->nr; ++j)
                        {
                              int k;
                              for(k=0; k <= n && sol[k] == 0; ++k);
                             
                              for(; k <= n; ++k) printf("%d", sol[k]);
                              printf("\n");
                        }
                  }    
                  afis(T->next[i], n+1);
            }
}

void read()
{
      freopen("sort.in","r",stdin);
      freopen("sort.out","w",stdout);
      while(!feof(stdin))
      {
            char a[N];
            memset(a, 0, sizeof(a));
            gets(a);
            int n=length(a);
            for(int i=0; i < n; ++i) a[i]-='0';
            trie t=find(n);
           
            if(t == 0)
            {
                  t= new nod;
                  init(t);
                  insert(t, n);
            }
           
            insert(t, a, n);
      }
     
      for(Tree_it i = R.begin(); i != R.end(); ++i) afis(i->second, 0);
           
}

int main()
{
      read();    
      return 0;
}