dbo:abstract
|
- Proportion extend sort (abbreviated as PESort) is an in-place, comparison-based sorting algorithm which attempts to improve on the performance, particularly the worst-case performance, of quicksort. The basic partitioning operation in quicksort has a linear access pattern which is extremely efficient on modern memory hierarchies, but the performance of the algorithm is critically dependent on the choice of a pivot value. A good pivot will divide the data to be sorted into nearly-equal halves. A poor choice will result in a grossly lopsided division, leaving one part almost as large as the original problem and causing O(n2) performance. Proportion extend sort begins with a sorted prefix of k elements, then uses the median of that sample to partition the following pk elements. By bounding the size ratio p between the sample and the data being partitioned (i.e. the proportion by which the sorted prefix is extended), the imbalance is limited. In this, it has some similarities to samplesort. (en)
|
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 9351 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
dbp:averageTime
| |
dbp:bestTime
| |
dbp:class
| |
dbp:data
| |
dbp:optimal
| |
dbp:space
| |
dbp:stability
| |
dbp:time
| |
dbp:wikiPageUsesTemplate
| |
dcterms:subject
| |
rdfs:comment
|
- Proportion extend sort (abbreviated as PESort) is an in-place, comparison-based sorting algorithm which attempts to improve on the performance, particularly the worst-case performance, of quicksort. The basic partitioning operation in quicksort has a linear access pattern which is extremely efficient on modern memory hierarchies, but the performance of the algorithm is critically dependent on the choice of a pivot value. A good pivot will divide the data to be sorted into nearly-equal halves. A poor choice will result in a grossly lopsided division, leaving one part almost as large as the original problem and causing O(n2) performance. (en)
|
rdfs:label
|
- Proportion extend sort (en)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is foaf:primaryTopic
of | |