[BangPypers] Pythonizing an algorithm
Senthil Kumaran
orsenthil at gmail.com
Thu Dec 4 10:51:50 CET 2008
On Thu, Dec 4, 2008 at 3:07 PM, Shashi <connect2shashi at gmail.com> wrote:
> http://manpages.ubuntu.com/manpages/hardy/man5/deb-version.htm
>
> in the Sorting Algorithm section... I can't
> understand a little bit of it... Please help
Did not look at the code and went to algorithm to see what it is.
It seem fairly straight forward. I shall try to explain step by step
and try it out in code.
Algorithm:
The strings are compared from left to right.
First the initial part of each string consisting entirely of non-digit
characters is determined. These two parts (one of which may be empty)
are compared lexically. If a difference is found it is returned. The
lexical comparison is a comparison of ASCII values modified so that all
the letters sort earlier than all the non-letters and so that a tilde
sorts before anything, even the end of a part. For example, the fol‐
lowing parts are in sorted order: '~~', '~~a', '~', the empty part,
'a'.
Then the initial part of the remainder of each string which consists
entirely of digit characters is determined. The numerical values of
these two parts are compared, and any difference found is returned as
the result of the comparison. For these purposes an empty string
(which can only occur at the end of one or both version strings being
compared) counts as zero.
These two steps (comparing and removing initial non-digit strings and
initial digit strings) are repeated until a difference is found or both
strings are exhausted.
SUGGESTION:
1) use regex to split the strings to non-digits ( not alpha) and digits.
2) get the length of the non-digits obtained and the digits string obtained.
3) as the example says, Before doing a string compare, run through to
compare ~ and empty string. Whichever has more ~ or empty string is
greater.
4) next Do string compare.
5) come to digits portion. Set empty string as Zero and do a numeric
compare and figure out which one is greater.
HTH,
Senthil
More information about the BangPypers
mailing list