Re: need an algo for string sorting

From: William (Reply_at_NewsGroup.Please)
Date: 08/19/04 

Date: Thu, 19 Aug 2004 10:52:18 -0500

"Raghavendra Mahuli" <raghavendra.ma@in.bosch.com> wrote in message
news:cg1ds2$6mq$1@ns1.fe.internet.bosch.com...
> Hi,
> I have many strings. I have to sort them. But sorting is not according to
> ascii but according to a different format (which keeps varying) . So i can
> sort them based on sort-order. It is not much of a problem.
>
> But the complex part is "equivalent-values". it can be defined that "ai"
and
> "ae" are equivalent-values. Then, while sorting two strings, i have to
> consider that "ai" and "ae" are equal......only if they come at same
> position in both the strings....

It really isn't a sorting problem, it's a comparison issue. Write the
correct comparison routine and plug it into the sort routine of your
choice, e.g., quicksort.

At the basic level, you need to step through each string, extracting
"tokens" instead of characters. Your parsing routine has to know
that, for example, "ax" is two tokens, but 'ai' is one token. Parse out
a token from the same character index in each string. If the lengths of
the tokens don't match, you know the strings are unequal. If the
lengths match, then you need to run through some logic that can
determine if the tokens are equivalent. This can be done with
comparisons, table lookups, hashing, regular expressions, or a
combination. The choices depend a lot on the language. Some will
offer "tricks" you can apply such as this piece of bourne shell script:

case "${Token1}$Token2" in
    aiae|aeai|aiai|aeae) echo "equal" ;;
    *) echo "not equal" ;;
esac

In Perl you could create a hash where each of those combinations
returns true when applied as a key. -Wm

Relevant Pages

  • Re: Solution for sorting an array alpha-numerically
    ... strings up into groups and sorting the groups seperately, ... > so that numeric and alphabetic data sort as seperate groups. ... To the same project as the web page, add the class AlphaNumCompare() ...
    (microsoft.public.dotnet.general)
  • Re: list view question
    ... > sort data other than strings and columns other than first column. ... > column to perform sorting on and then to do the sorting on that column ... > Public Sub New(ByVal aColumn As Integer, ByVal order As SortOrder, ...
    (microsoft.public.dotnet.languages.vb.controls)
  • Re: list view question
    ... sorting columns in .net is not as simple as in VB. ... sort data other than strings and columns other than first column. ... exposes compare method to compare two objects. ...
    (microsoft.public.dotnet.languages.vb.controls)
  • string parser
    ... I have to sort them. ... Then, while sorting two strings, i have to ... In str3, ae appears at position 1 and 2 ...
    (comp.lang.cpp)
  • need an algo for string sorting
    ... I have to sort them. ... Then, while sorting two strings, i have to ... In str3, ae appears at position 1 and 2 ...
    (comp.programming)