Comparison-based algorithms are algorithms that compare elements to determine the order, placement, or other relationship between them.
Some common examples of comparison-based algorithms include:
Sorting algorithms: Algorithms that sort a collection of elements into a specific order, such as increasing or decreasing. Examples include Bubble Sort, Insertion Sort, Quick Sort, and Merge Sort.
Search algorithms: Algorithms that search for an element in a collection, such as a list or an array. Examples include Binary Search and Linear Search.
Selection algorithms: Algorithms that find the kth smallest or largest element in a collection. Examples include QuickSelect and Median of Medians.
Comparison-based Tree algorithms: Algorithms that use comparisons to build and maintain a binary search tree data structure, such as AVL trees, red-black trees, and splay trees.
Comparison-based Graph algorithms: Algorithms that use comparisons to find the shortest path or minimum spanning tree in a graph, such as Dijkstra's algorithm and Prim's algorithm.
Comparison-based algorithms are generally less efficient than non-comparison-based algorithms, such as hash tables or radix sort, because comparisons are often the most time-consuming step in these algorithms.