How to test the implementation of algorithms?

Question

I am thinking about testing the implementation of some algorithms.

If you are thinking about the focus of TDD / BDD ... the test will 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 my algorithm to succeed ... so how would you test an implementation of an algorithm?

Answer 1

You test each implementation of the algorithm in the same way: take input, manually calculate the expected result and compare it with the output that the algorithm provides you.

If you do this in an interface language, you can get a general test with an interface parameter of the type and call its actual tests, which are passed in your implementations. This ensures that all algorithms pass 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.

In addition to the usual tests in which you manually enter the inputs and outputs for checking angular affairs and several other inputs (see JUnit or a similar structure of a really popular language), you can also write an ineffective but simple version of your algorithm (or, more precisely, everything that gives the same results, usually not quite the same algorithm) and a test against this version, either for all possible inputs, or if this is not possible using Fuzztester and some randomization.

One example of later testing would be testing a complex sorting algorithm (say heapsort) against SelectionSort. This also works well if you are optimizing the code and already have a tested and verified version (which in itself is a recursive problem).

In your particular case, you can simply compare your version with a simple binary search, which, as a rule, the standard library already has - creating random sized arrays with random input should not be a problem either.

Answer 3

In addition, you need to test it in a variety of conditions and under any circumstances make sure that it is one hundred percent effective.