Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-01-12 22:21:07.
Revizia anterioară Revizia următoare
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 lenght 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 stringh, 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
// implementation: 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 creat 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?
{
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;
}