# Assessing the quality of a heuristic sorting system

I have a program that uses a heuristic approach to sort elements into several buckets.

I have another program that does the same thing but computes exactly where each element should go.

When I compare the two results I see that some elements are in the right place and some are not. If I were to estimate the quality of the heuristic approach, how would I do it ?

Should I just divide the number of correctly placed elements using the heuristic approach with the total number of elements or is there a better way?? How would you do it?

-
This sounds like an interview question or a test question. – user246 Feb 13 '14 at 3:27
@user246 - agreed - I'd like to see some more context around this before attempting to provide an answer. Is this something the OP is evaluating as a workplace solution, for instance? – Kate Paulk Feb 14 '14 at 13:17
Well, it depends on the customer requirements. How accurate is the heuristic expected to be? 100% accurate? Or is it OK for it to be 80% accurate as long as it's fast? – vincebowdren Jul 25 '14 at 12:07

It's not any different than grading a test. If you know the max "score" for each bucket then you should be able to find your "grade" when you compare to actual "score".

-

What dimensions are most important to your customer?

You can grade accuracy by dividing the number of correctly placed elements by the number of total elements. If that's the sole concern, it's really that simple.

You can grade speed by timing how long it takes the algorithm to complete. You may want to run it a number of times and take an average, since wall-clock runtime varies from run to run. If your customer is solely concerned with speed, this will be the measure you'll want.

If your customer is concerned about both speed and accuracy, you'll need to weight the scores. How important is speed compared to accuracy? If it's 50/50, you can give the faster algorithm one point and the more accurate algorithm one point and see if one is clearly better or if they are tied. If one factor is more important than the other, you'll want to weight the scores appropriately, maybe two points for accuracy and one for speed.

If you're concerned with another metric, like CPU usage or file size or memory usage, you'll need to measure that, and consider it in your final weighted algorithm. You may want to create a scoring algorithm, such as `accuracy + (speed in seconds)/2 + filesize*10` and then rank the two approaches by final score. Again, it depends heavily on how important each factor is in the overall quality assessment.

-