Visual Basic Syntax - Sorting array of strings

Author

Sorting array of strings

Bob

2005-03-09, 4:01 am

In VB6, how can we sort an array of strings so that no member of the array is
properly contained in any elements that follow. For example if MyArray(2) =
“ab” then
MyArray(i) can be “ab” for any i > 4 but it should not be “abc” or “xyab”
etc for I > 4.

For example if MyArray is randamly arranged as:
axy,ab,xyab,xyz,abc,adb,abcd
I would like to arrange the elements of MyArray in any of the following two
orders or any order that satisfy the condition described above:

axy,abcd,xyab,abc,ab,xyz,adb
axy,xyab,xyz,abcd,abc,adb,ab

Thank you.

Jim Mack

2005-03-09, 4:01 am

Bob wrote:
> In VB6, how can we sort an array of strings so that no member of the
> array is properly contained in any elements that follow. For example
> if MyArray(2) = "ab" then
> MyArray(i) can be "ab" for any i > 4 but it should not be "abc" or
> "xyab" etc for I > 4.
>
> For example if MyArray is randamly arranged as:
> axy,ab,xyab,xyz,abc,adb,abcd
> I would like to arrange the elements of MyArray in any of the
> following two orders or any order that satisfy the condition
> described above:
>
> axy,abcd,xyab,abc,ab,xyz,adb
> axy,xyab,xyz,abcd,abc,adb,ab
>

Without an extensive anaIysis, I'd say that it's not possible to write
such a thing in the general case. I'm pretty sure that whatever you
devise, I could find a set of strings that break it.

However, if you have certain assurances about the data set, and can
share those with us, I'm sure we can come up with something.

Basically, take any sort algorithm and in the comparison phase, see if
the current test element is contained in the comparand (Instr). If it
is, treat it as though it's "less than" the comparand. If not, apply
the usual sort criteria.

This is similar to Huffman coding and would best be handled with a tree
rather than a sorted array. You can unbalance such a tree, but you
can't break it.

--

Jim Mack
MicroDexterity Inc
www.microdexterity.com

Bob O`Bob

2005-03-09, 4:02 pm

Bob wrote:

> In VB6, how can we sort an array of strings so that no member of the array is
> properly contained in any elements that follow. For example if MyArray(2) =
> “ab” then
> MyArray(i) can be “ab” for any i > 4 but it should not be “abc” or “xyab”
> etc for I > 4.
>
> For example if MyArray is randamly arranged as:
> axy,ab,xyab,xyz,abc,adb,abcd
> I would like to arrange the elements of MyArray in any of the following two
> orders or any order that satisfy the condition described above:
>
> axy,abcd,xyab,abc,ab,xyz,adb
> axy,xyab,xyz,abcd,abc,adb,ab
>
>
> Thank you.

1) eliminate any duplicates

2) sort by decreasing length

Bob O`Bob

2005-03-09, 4:02 pm

Jim Mack wrote:

> Without an extensive anaIysis, I'd say that it's not possible to write
> such a thing in the general case. I'm pretty sure that whatever you
> devise, I could find a set of strings that break it.

That was exactly my first impression, too, even before I read your post.

Bob

Bob

2005-03-10, 4:00 am

Jim, It’s a list of ISO 8859-1 characters such as alpha, beta,
gamma,zeta,eta,…nbsp, brvbar, para,cent,pound,…………….

Thank you,
Bob

"Jim Mack" wrote:

> Bob wrote:
>
> Without an extensive anaIysis, I'd say that it's not possible to write
> such a thing in the general case. I'm pretty sure that whatever you
> devise, I could find a set of strings that break it.
>
> However, if you have certain assurances about the data set, and can
> share those with us, I'm sure we can come up with something.
>
> Basically, take any sort algorithm and in the comparison phase, see if
> the current test element is contained in the comparand (Instr). If it
> is, treat it as though it's "less than" the comparand. If not, apply
> the usual sort criteria.
>
> This is similar to Huffman coding and would best be handled with a tree
> rather than a sorted array. You can unbalance such a tree, but you
> can't break it.
>
> --
>
> Jim Mack
> MicroDexterity Inc
> www.microdexterity.com
>
>
>

Jim Mack

2005-03-10, 8:59 am

Bob wrote:
> Jim, It's a list of ISO 8859-1 characters such as alpha, beta,
> gamma,zeta,eta,.nbsp, brvbar, para,cent,pound,......
>
> Thank you,
> Bob
>

Oh, then not so bad. Either of the two approaches outlined should work.

Bob (O'Bob)'s approach is simpler - since there are by definition no
dupes in the set, just sort on decreasing length. Sort case sensitive,
since you have things like 'THORN' and 'thorn' which are distinct
entities. This would not necessarily preserve alphabetic order, if that
matters.

My approach, restated slightly, would preserve alpha order as well. When
comparing, add the leading criterion that if one element is contained in
another, the containing element is sorted as "less than" the contained
one. Otherwise, sort on alpha as usual.

If you need to see actual code, let us know, but this is simple enough
and any sort algorithm would work.

--
Jim Mack
MicroDexterity Inc
www.microdexterity.com

Bob

2005-03-12, 3:59 pm

For different sorting methods in VB/VBA and their analysis, I found the
following article from Microsoft:

http://www.microsoft.com/officedev/articles/movs102.htm

Bob

"Bob" wrote:

> In VB6, how can we sort an array of strings so that no member of the array is
> properly contained in any elements that follow. For example if MyArray(2) =
> “ab” then
> MyArray(i) can be “ab” for any i > 4 but it should not be “abc” or “xyab”
> etc for I > 4.
>
> For example if MyArray is randamly arranged as:
> axy,ab,xyab,xyz,abc,adb,abcd
> I would like to arrange the elements of MyArray in any of the following two
> orders or any order that satisfy the condition described above:
>
> axy,abcd,xyab,abc,ab,xyz,adb
> axy,xyab,xyz,abcd,abc,adb,ab
>
>
> Thank you.

Jim Mack

2005-03-12, 8:58 pm

Bob wrote:
> For different sorting methods in VB/VBA and their analysis, I found
> the following article from Microsoft:
>
> http://www.microsoft.com/officedev/articles/movs102.htm
>
> Bob

Interesting that the article fails to mention two sorts that are easy to
code and have good performance: shell sort and comb sort. I like them
because they're almost as easy to remember as a bubble sort, and perform
100s of times better with normal data. Also not mentioned is heap sort,
which is harder to decipher (and remember) but performs quite well. The
article also doesn't deal with an important aspect of sorts: stability,
which is the tendency to retain an existing sub-order.

Any of those would be better than anything in that article except
quicksort (or counting sort, for specialized data).

If you care to see a comb sort for strings, let us know.

--
Jim

Sponsored Links