How to unit test the sorting of a std::vector

Question

I have never used unit testing before, so I'm giving CxxTest a go. I wrote a test to check if a function correctly sorts a std::vector. First I made sure the test failed when the vector wasn't sorted, and then as a sanity check I tested whether std::sort worked (it did, of course). So far, so good.

Then I started writing my own sorting function. However, I made a mistake and the function didn't sort correctly. Since my test didn't output the intermediate states of a vector as it was being sorted, it was difficult to tell where I had gone wrong in my sorting function. I ended up using cout statements (I could have used a debugger) to find my bug, and never used the unit test until after I knew my sort function worked.

Am I doing something wrong here? I thought unit testing was as simple as

1) Write test
2) Write function
3) Test function
4) If test fails, revise function
5) Repeat 3 and 4 until test passes

The process I used was more like

1) Write test
2) Write function
3) Test function
4) If test fails, debug function until it works correctly
5) Repeat 3 (even though function is already known to work)

I feel like my process was not truly TDD, because the design of my sorting function was not driven by the test I wrote. Should I have written more tests, e.g. tests that check the intermediate states of a vector as it's being sorted?

Answer 1

Don't try to test all intermediate states. No one cares how your sort algorithm works, just that it does its job reliably and quickly.

Instead, write your tests to check for sorted-ness for many different data sets. Test all typical problem sets: already sorted data, reverse-sorted data, random data, etc.

If your application requires a stable sort, your checking will have to be more careful. You might add a unique tag to each item being sorted just for testing purposes which the sort's comparison function doesn't test when sorting, but which can be used to ensure that two otherwise-equal values end up in the same relative order in the final output.

A final bit of advice: in testing, do make some effort to think of all possible failure cases up front, but don't expect to succeed. Be prepared to add tests as you discover more edge cases later. Test suites should evolve toward correctness, not be expected to be perfect up front, unless there is a mathematical reason why they should be correct.

Answer 2

I don't see a fundamental difference between the #4s in the sequences above. In TDD, you write unit tests so that, if they pass, you're fairly sure the code works. You work on the code until it passes. If you find a bug, you write another test to find it, and you are through working on the code when the tests pass. (If you're still not confident in it, write more tests.) In your case, you had more difficulty than you expected in getting the code to meet the test.

The advantage is not so much in getting code units to work as in knowing that they still work when you change things, and in having a clear definition of when they do work. (There are other advantages: for example, the tests serve as documentation of what the code is supposed to be doing.)

It may be that you want to write some smaller tests, but I'm not sure what you'd write that would be useful in the middle of a sort function. It seems to me that they'd be heavily dependent on how the function is implemented, and that seems to me against the spirit of TDD.

By the way, why are you writing your own sort function? I hope this is because you wanted to write a sort function (for class, or for fun, or to learn), and not for any production reason. The standard functionality is almost certainly going to be more reliable, easier to understand, and usually faster than anything you're going to write, and you shouldn't replace it with your own code without good reason.

Answer 3

Tests are not supposed to debug your code for you.

I feel like my process was not truly TDD

Your wrote a test. It found a bug. You fixed the bug. Your test passed. The system works!

This is the essence of test-driven development. Your tests tell you when you have a bug, and they tell you when you're done.

Anyway, feeling guilt because you're not achieving pure TDD or pure OOP or whatever is a psychological disorder. Go forth and be productive.

Answer 4

Unit testing focuses on the specific external behaviours of the thing you are writing, it can't really understand the intermediate states of algorithm. A sorting function is a rather special case.

More usually we are dealing with business logic of the kind

"The Order price is the sum of the prices of the order items reduced by a discount of 10% if the total value is greater than £20 and by a further 5% if the customer is a gold member"

We immediately can write tests such as

• No order items
• One order item value £20.00
• One order item value £20.01
• Two order items total value £20.00 gold customer
• ...

and so on - now it should be clear that these tests apply to different branches of the code and do help get it right.

For your sort code it may be helpful to have tests such as

• { 0 }
• { 1, 2 }
• { 2, 1 }
• { 1, 1 }

and so on, but the tests don't really know whether you are doing QuickSort or BubbleSort or whatever.

Answer 5

The TDD process is

1. RED: write a test, verify it fails

2. GREEN write just enough code to make it pass, verify it passes

3. refactor the code - both the test and the production code

If you find yourself having to resort to the debugger at step 2, it could be that you're testing too much at a time. Divide and conquer. Although dividing could not be so easy for a sorting algorithm, did you start with sorting an empty vector, then a vector with a single element, then a vector with two elements already ordered, a vector with two elements in the wrong order ...