sortare stringuri

[•mika17]

Ok problema ar suna cam asa
Se dau N siruri de caractere Unicode de lungime maxim M ,  N si M <= 1000000. Sa se sorteze crescator in functie de indicele caracterului
Mie imi vine in cap quicksort in  O (N * M * logN), sau eventual un trie , in O(N*M)
Exista ceva mai rapid ?

[•c_e_manu]

Sa se sorteze fiecare sir sau toate sirurile?
Daca ti se dau N stringuri de lungime maxim M atunci poti sorta cu quicksort si mai rapid cu sort() din STL. Daca trebuie sa sortezi fiecare 1....N string de lungime M, nu am idee mai rapida decat ai spus tu.

[•wefgef]

Pai oricum nu poti mai bine de O(N*M) pentru ca atat iti ia citirea datelor.

[•mika17]

Sa se sorteze fiecare sir sau toate sirurile?
Daca ti se dau N stringuri de lungime maxim M atunci poti sorta cu quicksort si mai rapid cu sort() din STL. Daca trebuie sa sortezi fiecare 1....N string de lungime M, nu am idee mai rapida decat ai spus tu.

Da, toate sirurile. Pai se poate sorta mai repede decat N*M*logN? sort'u din STL scoate mai putin pt stringuri?
Adica .. nu face tot NlogN comparatii ? Si ca sa compari 2 siruri ar lua O(M).

Si m-ar interesa si ceva materiale utile si succinte despre arbori de sufixe, am gasit si eu articole (art lui Ukkonen) dar sunt mult prea mari si greoaie.

[•sima_cotizo]

Pai tu cu un trie ai zis ca scoti O(N*M). Cum si citirea tot O(N*M) este, asta e complexitatea cea mai buna (asta voia Wef sa-ti zica)