Printable View
Hi.
I have created a program which uses the bubble sort to generate random numbers and sort them using a bubble sort. I then created two functions which would count the number of compares and swaps, Te problem is I have absolutely no idea on how to test if the number of compares and swaps are correct. How would i go about testing for this?
Make sure the program prints out the original data, run through the algorithm yourself, and see how many compares and swaps are actually needed.
yes, but what if you want to test for say 100 numbers, and you want to know if the number of compares and swaps are correct. we know that trying to do this by hand is quite long, how can the program be tested fairly if we dont want to do it by hand?
You don't do 100. You do 6. And then if it works for 6, presumably it works for 100 as well.
Alternatively, I suppose, you can find someone else in the class, make sure you are using the same data, and compare answers (you could still both be wrong, I suppose, but it's less likely).
Also, you would expect, as the size of the list to be sorted grows, that your numbers would roughly obey O(n^2) -- so if you double the size of the list, you should do four times as much work.
Why would you not trust your code to tell you the correct swap and compare counts? You can either increment counters right before the comparisons and swaps, or you can do it the way I do it, by putting the counter increments into the less-than and assignment operators of the class.
It will give you the right answer, as long as you remember to set it to zero initially.
(Divide by 3 if you put a counter in the assignment operator of course)