Sorting algorithm that can handle some error

Question

Suppose you want to sort your movie collection, from favorite to hated. You apply the rules of some sorting algorithm by asking many questions of the form: "Did I like A or B more?"

It's now sorted, right? Logically, every necessary question was asked to prove that when index(A) < index(B), A > B. But you can show that this is false for at least one pair A and B. Surely, the algorithm should have asked more questions.

Opinion is hard to nail down, and if one comparison is off, the whole sorting operation might result in something way off.

Which sorting algorithm would you pick to ensure the sorted list won't be too impacted by a bad comparison?

Answer 1

The key thing here is to avoid making the same comparison more than once. And there is one sort that really meets that criteria in a way that is doable for a human sorting their movie collection.

Merge sort.

With the merge sort, you recursively break down the size of the set to 2 (or 1). And then you sort each of those. Now, you take two sets of 2 (the actual algorithm takes it down to sets of 1, but we're doing this by hand and so can avoid that level of exactness), and then compare the first element of each, of those. If you have 36 and 24 - you have already compared 3 and 6, you aren't going to compare them again. The resulting set then becomes 2346 and then you continue on merging with the next set of four.

From the wikipedia page:

The key here is that with each comparison, you are not reevaluating the previous comparisons. Thus, if you decide that you like the Yellow Submarine more than the Hard Days Night once, you are not going to re-evaluate that and they aren't going to end up too far from each other in the end.

The problem with many other sorts is that you are either constantly asking "do I like this more than Santa Claus Conquers the Martians" each time with a selection / insert / bubble sort. And other sorts become far too complicated to be able to reason about.

---

A way to test this that would make for some very interesting blog posts is to implement the different sorts yourself and override > or compareTo in your chosen language. In that method, add a slight bit of randomness to it, say, +/- 10% of the value. or +/- 1% of the value.

Then, sort the numbers 1 .. 100 100x and see how far out of whack each sorting method results in.

Answer 2

I made recently some tests to see how sorting algorithms can still work when the comparisons have some probability to be false.

I made my tests on lists of size around 100 elements, and i haven't tested seriously with metrics of how "mixed" is a list, but still, here are my results :

For very small error rates (mabe under 2-3%), gnome sort is able to get very close to a fully sorted list. That is because it is able to correct past errors.

For bigger error rates, the problem is mostly that some algorithms tend to make mistakes that results in having 2 parts of the list that are independently sorted, but that should be merged. For that, merge sort is a bit better, because it does make a "globally sorted" list, but it isn't really satisfying, because it has big errors. I would recommend doing something like merge sorting the list, and then gnome sorting it, so the gnome sort corrects some mistakes. You can get even better results when repeating the sortings multiple times (i found that merge sort twice and then a bunch of gnome sort works very well).

For your specific problem, gnome sort isn't ideal, because it is using a lot of comparisons, so, as mentionned before, merge sort can be very interesting for that particular purpose.

Finally, i must mention that, in the experiments i made, the one that gets the closest to a sorted list is the odd-even sort, that has almost no errors. The only problem is that it tends not to stop, because it always finds that there is still an element to sort (that is caused by previous random mistakes). But a simple iteration-counter that stops the algorithm after a number of iterations (that depends on the list length) does the job (also, changing the halt condition of the odd-even sort may work, but then it wouldn't sort perfectly even with no errors on the comparisons). Special mension for that algorith because it is beautifull when visualised : odd-even sort visualised with bar graph

Just to drop a quick idea, you may create a data-structure to store the comparisons that the user already answered to (it would probably be a graph). To prevent the algorithm from asking hundreds of questions to the used, you may use transitivity of the relation "the film is better". As your question mentions, the transitivity isn't always respected by the user, so i would try to use the transitivity only if it is confirmed multiple times (example: you consider that A is better than B only if there are two other films X and Y that are such that A > X > B, AND A > Y > B, but not if it there is only one other film that respects that property). But that technique requires manipulating paths across a graph or something alike. Maybe you also could use marks given on each film, to confirm a certain comparison, so you could say "i'm shure that A is better than B only if the user already said that A > X and X > B and if the mark given to A is better than the mark given to B). If the mark is the same, or not coherent with the transitivity, you then would ask the user to give the actual comparison.