Menu
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.
764
Definition of Bogosort. The universally-acclaimed worst sorting algorithm is Bogosort, sometimes called Monkey Sort or Random Sort, for reasons we'll see shortly. Bogosort develops from the idea that, in probability theory, if a certain phenomenon is possible, then it will eventually happen.
Some adaptive sorting algorithms are : Bubble Sort, Insertion Sort and Quick Sort.
Such examples include Bubble Sort, Insertion Sort, Mergesort, Heapsort, Timsort, and Intro Sort. Non-comparison based sorting algorithms, on the other hand, are sorting algorithms which are not comparison based. Examples include Counting Sort and Radix Sort.
When the array is almost sorted, insertion sort can be preferred. When order of input is not known, merge sort is preferred as it has worst case time complexity of nlogn and it is stable as well. When the array is sorted, insertion and bubble sort gives complexity of n but quick sort gives complexity of n^2.
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
162
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
