Compare 16 values to each other most efficiently

  • Thread starter Thread starter Roger Twomey
  • Start date Start date
R

Roger Twomey

I have 16 string values that I need to compare to each other. No two are
supposed to hold the same value (if they do something is amiss and I need to
abort the operation).

Short of 'IF Then' comparisons for every possible combination (do-able but
very cludgy) is there not a better way to code this?

Any idea will be considerted.

Thanks.
 
I'd put them in an array and loop through with each value comparing it to
the rest (with logic to only make comparisons that haven't been made yet if
you want the most efficent way).

Matt
 
I'd put them in an array and loop through with each value comparing it to
the rest (with logic to only make comparisons that haven't been made yet if
you want the most efficent way).
Click to expand...

Matt, this approach is not the most efficient one. Consider that you
have n strings you want to compare. In the worst case you'll have to
compare the first string with n-1 other strings, then the second one
with n-2 other strings, then the third with n-3, and so on. The total
number of comparisons you'll have to do will be:

(n-1) + (n-2) + ... + 1

which is, in closed form, (n^2 - n)/2 comparisons.

Now, if you first *sort* the strings using, say, quicksort, this will
take n * log(n) comparisons. Once the strings were sorted, you could
then walk over the string once, seeing if any matched up (by just
comparing one with another). The asymptotic running time of this second
approach would be n * log(n) + n, which beats (n^2 - n)/2 for
sufficiently large n.


--

Scott Mitchell
(e-mail address removed)
http://www.4GuysFromRolla.com
http://www.ASPFAQs.com
http://www.ASPMessageboard.com

* When you think ASP, think 4GuysFromRolla.com!
 
Back
Top