[Edu-sig] Analyzing algorithms...

[Kirby Urner]

>
>I've written the sorts.  Does anyone have any suggestions as to the best
>way to do the empirical analysis?  Is there a better way than just
>creating counters and then littering my code with increment statements?
>
>Please let me know if you have any ideas?

I'd probably make the elements to be sorted instances of some
object, override the comparison operators, and build a counter
into their invocation.

Something similar could be done with assignment, where you
use an object method to store an element, versus a simple =.

E.g.:

 >>> class Element:
         def __init__(self,val):
             self.value = val
             self.comp = 0

         def __repr__(self):
             return str(self.value)

         def __eq__(self,other):
             self.comp += 1
             other.comp += 1
             return self.value==other.value

         def __gt__(self,other):
             self.comp += 1
             other.comp += 1
             return self.value>other.value

         def __lt__(self,other):
             self.comp += 1
             other.comp += 1
             return self.value<other.value

         def __le__(self,other):
             self.comp += 1
             other.comp += 1
             return self.value<=other.value

         def __ge__(self,other):
             self.comp += 1
             other.comp += 1
             return self.value>=other.value


   >>> a = Element(1)
   >>> b = Element(2)
   >>> a<b
   1
   >>> a==b
   0
   >>> a>=b
   0
   >>> a<=b
   1
   >>> a>b
   0
   >>> a.comp  # internal counter knows how many comparisons
   5
   >>> b.comp  # ditto

Kirby