How to test algorithms implementation?

Question

I'm thinking about testing the implementation of some algorithms

If you think about a TDD/BDD focus... a test would be

 Scenario: doubling search
 Given an ordered array "[2,3,4,5,6,7]"
 When I look for "4" with "doubling search" in it
 Then the result must be "2"

I want to make sure my algorithm is doing well... so, how would you test an algorithm implementation?

Answer 1

You test every implementation of an algorithm the same way: take an input, calculate by hand your expected output, and compare it to the output the algorithm provides you.

If you're doing this in a language with interfaces, you could have a generic test take a parameter of type interface, and have it be called by your actual tests that pass in your implementations. This ensures all algorithms undergo the same test based on their interface.

// double search implemented by using the search and multiplying by 2
algorithm multDoubleSearch
   define input array
   define input search

   for each i in array
      if i = search * 2
           return index of i
   end
   return -1
end.

// double search implemented by dividing the values by 2
algorithm divDoubleSearch
    define input array
   define input search

   for each i in array
      if i / 2 = search
           return index of i
   end
   return -1
end.


test mytest
     define array {2 3 4 5 6 7}
     define search 2

     define resultMult = multDoubleSearch(array,search)
     assert resultMult == 2 // 4 is index 2, assuming 0 indexed

     define resultDiv = divDoubleSearch(array,search)
     assert resultDiv == 2 // 4 is index 2, assuming 0 indexed
end.

Answer 2

Well it depends on WHAT you have at hand.

Apart from the usual tests where you provide the inputs and outputs manually to test corner cases and a handful other inputs (see JUnit or a similar framework in really any popular language), you may also write an inefficient but simple version of your algorithm (or to be exact anything that produces the same results, usually not exactly the same algorithm) and test against that version, either for all possible inputs or if that's not possible using a Fuzztester and some Randomization.

One example for the later would be testing a complex sorting algorithm (let's say heapsort) against SelectionSort. That also works well if you optimize code and already have a tried and tested version at hand (which in itself is kind of a recursive problem).

In your particular case you could just compare your version against a simple binary search - which the standard library most certainly already has - creating arrays of random size with random input shouldn't be a problem either.