Hello,
I would like to sort the rotations of a string:
encode.su
ncode.rue
code.ruen
ode.ruenc
de.ruenco
e.ruencod
.ruencode
ruencode.
uencode.rWith some strings the sorting is not so easy because a comparision between 2 rotations never ends:.ruencode
code.ruen
de.ruenco
e.ruencod
encode.su
ncode.rue
ode.ruenc
ruencode.
uencode.r
codecode
odecodec
decodeco
ecodecod
codecode
odecodec
decodeco
ecodecodAs you can see there are rotations which don't distinguish from each other. So if the sorting algorithm compares 2 such rotations to find out which rotation to place above and which below it will compare character for character untill one rotation reaches the end of the input string and then continues at the beginning and goes on like this forever.codecode
codecode
decodeco
decodeco
ecodecod
ecodecod
odecodec
odecodec
The simplest way to fix the problem is to count the amount of compared characters or to check wether we have reached the character again from which we have started. Both ways need 1 comparision extra for each character we compare to distinguish the rotations. I am already using 4 characters each comparision to make better use of a 32 bit processor but there is still the annoying extra comparision.
An other way is to check first wether the input string is one of the problematic ones and if so, then execute special sorting code which has the extra comparison or reduces the input string, sort it and then expand the sorted result afterwards.
Any other suggestions?