Suppose I have a file with a one-liner (joke) on each line. I want to sort the jokes by how funny I find them. My first thought is to implement any sorting algorithm (preferably one that makes as few comparisons as possible) and having the comparison algorithm take my input; I'd just sit there and choose which of each pair of jokes it presented me was funnier.
There's a problem with that. My joke preference is not a total order. It lacks transitivity. For example, I might think that B is funnier than A when presented them, and that C is funnier than B, but when presented A and C somehow I find A to be funnier than C. If “>” means “is funnier than,” this means that C > B and B > A does not imply C > A. All sorting algorithms’ correctness depends on this.
But it still seems that there should be an algorithm that sorts the list of jokes so that the one at the top is most preferred over other jokes, and the one at the bottom is least preferred over other jokes, even if there are individual exceptions.
I don’t know how to Google this. Is there an algorithm for this kind of preference sorting? The answer here is not applicable because it forces the user’s preference to be transitive.
If you represent your decisions as a directed graph, where each joke is a node and each directed edge indicates one joke being better than the other, then you can retrieve an ordering by constructing the path which follows the edges and visits each node exactly once.
This type of graph is called a Tournament, and the path is a Hamiltonian path. I've got good news for you Bub, a Hamiltonian is proven to exist if the graph is strongly connected. Strongly connected just means that every node can be reached from every node, obeying the direction of the edges, so keep adding edges until this is true.
Tournament: https://en.wikipedia.org/wiki/Tournament_(graph_theory)
Hamiltonian Path: https://en.wikipedia.org/wiki/Hamiltonian_path