CODEWITHSUNDEEP
algorithmsortingoptimizationcomparison
ThatOneGuyInXNA
ThatOneGuyInXNA

Reputation: 111

Sort elements with the fewest comparisons possible

I have a folder full of images. There are too many to just 'rank'. I made a program that shows two at a time and let's the user pick which one of the two is better. At the end I would like all of the photos to be ordered from best to worst.

I am purely trying to optimize for the fewest amount of comparisons possible. I don't care if the program runs in n cubed time. I've read the other questions here with similar questions but I'm looking for something more advanced.

I'm thinking maybe some sort of algorithm that based on what comparisons you've already made, the program chooses two images to compare that will offer the most information. Maybe even an algorithm that makes complex connections to help determine the orders and potential orders.

Like I said I don't care if it is slow just purely trying to minimize comparisons

Upvotes: 1

Views: 887

Answers (2)

DanielHsH
DanielHsH

Reputation: 4453

If total order exists, you need at least nlog2(n) comparisons. It can be easily proved mathematically. No way around. So regular sorting algorithms in nlog(n) will do the job.

What you are trying to do is called 'topological sort'. Google it and read about it in wikipedia. You can achieve partial sorts in less comparisons. Its kind of a graduate sort. The more comparisons you get, the better the result will be.

However, what do you do if no total order exists? Humans are not able to generate a total order for subjective tasks. For example picture 1 is better than 2, 2 is better than 3 but 3 is better than 1. In this case no sorting algorithm can produce a permutation which will match all the decisions. During topological sort, you can detect those inconsitent decisions and get rid of them.

Upvotes: 3

Peter Schneider
Peter Schneider

Reputation: 1701

You are looking for a sorting algorithm - pick one. Most algorithms just need a comparison function (a < b?). This is when you show the user two pictures and he has to choose the better one.

You might wan't to read trough some of the algorithms and choose the best one for you. E.g. on quicksort, you would pick a random picture and the user have to compare this picture against all other pictures in the first round - might be too boring from the end user perspective.

Upvotes: 1

Related Questions