On the distribution of comparisons in sorting algorithms (Q1115198): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
 
(One intermediate revision by one other user not shown)
Property / cites work
 
Property / cites work: Sorting in \(c \log n\) parallel steps / rank
 
Normal rank
Property / cites work
 
Property / cites work: An adversary-based lower bound for sorting / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient searching using partial ordering / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Counting Approach to Lower Bounds for Selection Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Poset Measure and Saturated Partitions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5585020 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4057549 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sorting with expensive comparands / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some Examples of Combinatorial Averaging / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/bf01954896 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1969935217 / rank
 
Normal rank

Latest revision as of 10:42, 30 July 2024

scientific article
Language Label Description Also known as
English
On the distribution of comparisons in sorting algorithms
scientific article

    Statements

    On the distribution of comparisons in sorting algorithms (English)
    0 references
    0 references
    0 references
    0 references
    1988
    0 references
    We consider the following natural conjecture: For every sorting algorithm every key will be involved in \(\Omega\) (log n) comparisons for some input. We show that this is true for most of the keys and prove matching upper and lower bounds. Every sorting algorithm for some input will involve \(n-n^{\epsilon}/2+1\) keys in at least \(\epsilon\) \(log_ 2 n\) comparisons, \(\epsilon >0\). Further, there exists a sorting algorithm that will for every input involve at most \(n-n^{\epsilon /c}\) keys in greater than \(\epsilon\) \(log_ 2 n\) comparisons, where c is a constant and \(\epsilon >0\). The conjecture is shown to hold for ``natural'' algorithms from the literature.
    0 references
    adversaries
    0 references
    sorting
    0 references
    lower bounds
    0 references

    Identifiers