1
$\begingroup$

Can you share examples of comparison-based algorithms used in practice that are not a sort or a search over lists? Heapify is an example of a comparison-based algorithm that is neither a sort nor a search. Heapify is of course part of Heapsort and still operates over lists. Are there other examples of comparison-based algorithms that are not sorts or searches over lists and are used in a different context than sorting or searching or operate over different data structures?

By comparison-based I mean the standard definition: every basic operation (swaps, assignments, ...) need to be carried out on the basis of a series of comparisons only. This includes the transitive closures of the outcomes of comparisons (as in quicksort: a swap can be carried out on elements a and b when a > p and p > b has been determined, where p is the pivot. In this case no direct comparison between a and b was made, but their order is deduced based on the transitive closure of the relations). The elements to be ordered need to satisfy a linear order (total order), i.e. a <= b or a >= b always needs to hold (as for the case of integers, real numbers, words (lexicographical order) etc.) Put another way: these are algorithms for which the computation can be modelled via a decision tree. Their execution is the same on data that share the same relative order. In the case of lists: the execution is the same on the reverse ordered list [4,3,1] as on the reverse ordered list [50,6,5].

I prefer examples for which the comparison-time (worst-case or average-case) has been determined, but I'm open to others examples for which this has not been done.

It seems that the Knuth–Morris–Pratt algorithm and Booth's Algorithm may fall into this category, i.e. string matching algorithms.

Pseudonym suggested priority scheduling below (I did not check this sufficiently yet but it seems a possible fit). Any others?

$\endgroup$
4
  • $\begingroup$ This is going to depend what you mean by "comparison-based". In general, you typically use comparison when you need an ordering, and beyond fundamental data structures like priority queues, it's probably going to matter what you are ordering. For example, there is a whole class of algorithms based around scheduling which involve a notion of priority. $\endgroup$
    – Pseudonym
    Dec 9, 2021 at 23:43
  • $\begingroup$ @Pseudonym I updated it with a description of the type of algorithm I have in mind. $\endgroup$ Dec 9, 2021 at 23:51
  • 1
    $\begingroup$ There are some examples in computational geometry, for example k-d trees. $\endgroup$ Dec 10, 2021 at 11:12
  • $\begingroup$ @YuvalFilmus Thank you! $\endgroup$ Dec 10, 2021 at 11:21

1 Answer 1

2
$\begingroup$

I summarise some comparison-based algorithms found thanks to suggestions here and also in relation to examples I know of or found online. The Huffman algorithm may raise some eyebrows, but it seems to have all the hallmarks of a comparison-based algorithm. Do add any if you know of more examples (or share criticism on the ones listed below if you deem them not to fit). I find the usual presentation of comparison-based computation a little short on examples, so aim to use this list to show their impact beyond sorts and searches. I did not add priority scheduling yet but may add it later pending a closer look at how it goes beyond sorting.

Min-max heap construction. Min-max heaps combine a min-heap and a max-heap. The data structure provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements. It forms a useful data structure to implement a double-ended priority queue.

Beap construction. A compromise between costs of searching and updating is to create a structure with the same father-son relationship as a heap, and with most nodes having two sons. The difference is that in general each node will have two parents--a beap.

String matching. A string-matching algorithm finds the starting index $m$ in string $s$ that matches the search word $w$. The Knuth–Morris–Pratt algorithm.

Lexicographically minimal string rotation Aka least circular substring is the problem of finding the rotation of a string possessing the lowest lexicographical order of all such rotations.

Prefix order construction. The Huffman file encoding algorithm. Huffman code is an optimal prefix code used for lossless data compression.

Balanced k-d-trees construction. Useful for searches involving a multidimensional search key (e.g. range searches and nearest neighbour searches) and creating point clouds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.