Introselect (original) (raw)
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 performan
| Property | Value |
|---|---|
| dbo:abstract | 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 and heapselect, and has a worst-case running time of O(n log n). The C++ draft standard, as of 2022, does not have requirements on the worst-case performance, therefore allowing such choice. (en) |
| dbo:wikiPageExternalLink | http://www.cs.rpi.edu/~musser/gp/introsort.ps%7C |
| dbo:wikiPageID | 11062320 (xsd:integer) |
| dbo:wikiPageLength | 4454 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123343799 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quicksort dbr:C++_Standard_Library dbr:David_Musser dbr:Introsort dbr:Computer_science dbr:Median_of_medians dbr:Heapselect dbr:Quickselect dbr:Floyd–Rivest_algorithm dbr:Heapsort dbr:Hybrid_algorithm dbr:Array_data_structure dbc:Selection_algorithms dbr:Sorting_algorithm dbr:Selection_algorithm dbr:Generic_algorithm |
| dbp:bestTime | O (en) |
| dbp:class | Selection algorithm (en) |
| dbp:data | dbr:Array_data_structure |
| dbp:name | Introselect (en) |
| dbp:time | O (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:Harv dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Infobox_Algorithm |
| dcterms:subject | dbc:Selection_algorithms |
| rdf:type | yago:WikicatSelectionAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | 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 performan (en) |
| rdfs:label | Introselect (en) |
| owl:sameAs | freebase:Introselect yago-res:Introselect wikidata:Introselect dbpedia-fa:Introselect https://global.dbpedia.org/id/fs5J |
| prov:wasDerivedFrom | wikipedia-en:Introselect?oldid=1123343799&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Introselect |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:C++_Standard_Library dbr:David_Musser dbr:Introsort dbr:Median_of_medians dbr:Quickselect dbr:Floyd–Rivest_algorithm dbr:Hybrid_algorithm dbr:Selection_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Introselect |