|
Introselect
In computer science, introselect (short for "introspective selection") is a selection algorithm that is a hybrid of quickselect and median of medians which has fast average performance and optimal worst-case performance. Introselect is related to the introsort sorting algorithm: these are analogous refinements of the basic quickselect and quicksort algorithms, in that they both start with the quick algorithm, which has good average performance and low overhead, but fall back to an optimal worst-case algorithm (with higher overhead) if the quick algorithm does not progress rapidly enough. Both algorithms were introduced by David Musser in , with the purpose of providing generic algorithms for the C++ Standard Library that have both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened. However, in most C++ Standard Library implementations, a different "introselect" algorithm is used, which combines quickselect ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Floyd–Rivest Algorithm
In computer science, the Floyd-Rivest algorithm is a selection algorithm developed by Robert W. Floyd and Ronald L. Rivest that has an optimal expected number of comparisons within lower-order terms. It is functionally equivalent to quickselect, but runs faster in practice on average. It has an expected running time of and an expected number of comparisons of . The algorithm was originally presented in a Stanford University technical report containing two papers, where it was referred to as SELECT and paired with PICK, or median of medians. It was subsequently published in Communications of the ACM, Volume 18: Issue 3. Algorithm The Floyd-Rivest algorithm is a divide and conquer algorithm, sharing many similarities with quickselect. It uses sampling to help partition the list into three sets. It then recursively selects the ''k''th smallest element from the appropriate set. The general steps are: # Select a small random sample ''S'' from the list ''L''. # From ''S'', recur ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quickselect
In computer science, quickselect is a selection algorithm to find the ''k''th smallest element in an unordered list, also known as the ''k''th order statistic. Like the related quicksort sorting algorithm, it was developed by Tony Hoare, and thus is also known as Hoare's selection algorithm. Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance. Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations. Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for. This reduces the average complexity from O(n\log n) to O(n), with a worst case of O(n^2). As with quicksort, quic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Array Data Structure
In computer science, an array is a data structure consisting of a collection of ''elements'' (value (computer science), values or variable (programming), variables), of same memory size, each identified by at least one ''array index'' or ''key'', a collection of which may be a tuple, known as an index tuple. An array is stored such that the position (memory address) of each element can be computed from its index tuple by a mathematical formula. The simplest type of data structure is a linear array, also called a one-dimensional array. For example, an array of ten 32-bit (4-byte) integer variables, with indices 0 through 9, may be stored as ten Word (data type), words at memory addresses 2000, 2004, 2008, ..., 2036, (in hexadecimal: 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4) so that the element with index ''i'' has the address 2000 + (''i'' × 4). The memory address of the first element of an array is called first address, foundation address, or base address. Because the mathematical conc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, applied disciplines (including the design and implementation of Computer architecture, hardware and Software engineering, software). Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of computational problem, problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and preventing security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Programming language theory considers different ways to describe computational processes, and database theory concerns the management of re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Selection Algorithm
In computer science, a selection algorithm is an algorithm for finding the kth smallest value in a collection of ordered values, such as numbers. The value that it finds is called the order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of n values, these algorithms take linear time, O(n) as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted array takes Problem statement An algorithm for the selection problem takes as input a collection of values, and a It outputs the smallest of these values, or, in some versions of the problem, a collection of the k smallest values. For this to be well-defined, it should be possible to sort the values into an order from smallest to largest; ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hybrid Algorithm
{{Unreferenced, date=May 2014 A hybrid algorithm is an algorithm that combines two or more other algorithms that solve the same problem, either choosing one based on some characteristic of the data, or switching between them over the course of the algorithm. This is generally done to combine desired features of each, so that the overall algorithm is better than the individual components. "Hybrid algorithm" does not refer to simply combining multiple algorithms to solve a different problem – many algorithms can be considered as combinations of simpler pieces – but only to combining algorithms that solve the same problem, but differ in other characteristics, notably performance. Examples In computer science, hybrid algorithms are very common in optimized real-world implementations of recursive algorithms, particularly implementations of divide-and-conquer or decrease-and-conquer algorithms, where the size of the data decreases as one moves deeper in the recursion. In this cas ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Median Of Medians
In computer science, the median of medians is an approximate median selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, most commonly quickselect, that selects the ''k''th smallest element of an initially unsorted array. Median of medians finds an approximate median in linear time. Using this approximate median as an improved pivot, the worst-case complexity of quickselect reduces from quadratic to ''linear'', which is also the asymptotically optimal worst-case complexity of any selection algorithm. In other words, the median of medians is an approximate median-selection algorithm that helps building an asymptotically optimal, exact general selection algorithm (especially in the sense of worst-case complexity), by producing good pivot elements. Median of medians can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity O(n\log n). Although this approach optimizes the asymptotic worst-cas ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Introsort
Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort, it switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted and it switches to insertion sort when the number of elements is below some threshold. This combines the good parts of the three algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(''n'' log ''n'') runtime due to the heap sort. Since the three algorithms it uses are comparison sorts, it is also a comparison sort. Introsort was invented by David Musser in , in which he also introduced introselect, a hybrid selection algorithm based on quickselect (a variant of quicksort), which falls back to median of medians and thus provides worst-case linear complexity, which is optimal. Both algorithms were introduced with the pur ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sorting Algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the Algorithmic efficiency, efficiency of other algorithms (such as search algorithm, search and merge algorithm, merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for Canonicalization, canonicalizing data and for producing human-readable output. Formally, the output of any sorting algorithm must satisfy two conditions: # The output is in monotonic order (each element is no smaller/larger than the previous element, according to the required order). # The output is a permutation (a reordering, yet retaining all of the original elements) of the input. Although some algorithms are designed for sequential access, the highest-performing algorithms assum ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quicksort
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions. Quicksort is a divide-and-conquer algorithm. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting. Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. It is a comparison-based sort since elements ''a'' and ''b'' are only swapped in ca ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
David Musser
David "Dave" Musser is a professor emeritus of computer science at the Rensselaer Polytechnic Institute in Troy, New York, United States. He is known for his work in generic programming, particularly as applied to C++, and his collaboration with Alexander Stepanov. Their work together includes coining the term "generic programming" in , and led to the creation of the C++ Standard Template Library (STL). In , he developed the sorting algorithm called introsort (also known as introspective sort), and the related selection algorithm called introselect In computer science, introselect (short for "introspective selection") is a selection algorithm that is a hybrid of quickselect and median of medians which has fast average performance and optimal worst-case performance. Introselect is related ..., to provide algorithms that are both efficient and have optimal worst-case performance, for use in the STL. [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Generic Algorithm
Generic programming is a style of computer programming in which algorithms are written in terms of data types ''to-be-specified-later'' that are then ''instantiated'' when needed for specific types provided as parameters. This approach, pioneered in the programming language ML in 1973, permits writing common functions or data types that differ only in the set of types on which they operate when used, thus reducing duplicate code. Generic programming was introduced to the mainstream with Ada in 1977. With templates in C++, generic programming became part of the repertoire of professional library design. The techniques were further improved and ''parameterized types'' were introduced in the influential 1994 book ''Design Patterns''. New techniques were introduced by Andrei Alexandrescu in his 2001 book ''Modern C++ Design: Generic Programming and Design Patterns Applied''. Subsequently, D (programming language), D implemented the same ideas. Such software entities are kno ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
