“Sorting number”的意思、由来-开放百科全书

词条

Sorting number

释义

Formula and examples
Application to sorting
Other applications
References

In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst case number of comparisons used by binary insertion sort, and the worst-case number of comparisons used by merge sort. However there are other algorithms that use fewer comparisons.

Formula and examples

The th sorting number is given by the formula{{r|fj}}

where

The sequence of numbers given by this formula (starting with ) is

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... {{OEIS|A001855}}.

The same sequence of numbers can also be obtained from the recurrence relation{{r|as}}

It is an example of a 2-regular sequence.{{r|as}}

Asymptotically, the value of the th sorting number fluctuates between

and

depending on the ratio between and the nearest power of two.{{r|as}}

Application to sorting

In 1950, Hugo Steinhaus observed that these numbers count the number of comparisons used by binary insertion sort, and conjectured (incorrectly) that they give the minimum number of comparisons needed to sort items using any comparison sort. The conjecture was disproved in 1959 by L. R. Ford Jr. and Selmer M. Johnson, who found a different sorting algorithm, the Ford–Johnson merge-insert sort, using fewer comparisons.{{r|fj}}

The same sequence of sorting numbers also gives the worst case number of comparisons used by merge sort to sort items.{{r|as}}

Other applications

The sorting numbers (shifted by one position) also give the sizes of the shortest possible superpatterns for the layered permutations.{{r|aepv}}

References

1. ^{{citation | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | doi = 10.1016/0304-3975(92)90001-V | issue = 2 | journal = Theoretical Computer Science | mr = 1166363 | pages = 163–197 | title = The ring of

-regular sequences | volume = 98 | year = 1992}}. See Example 28, p. 192.
2. ^{{citation | last1 = Ford | first1 = Lester R. Jr. | author1-link = L. R. Ford Jr. | last2 = Johnson | first2 = Selmer M. | author2-link = Selmer M. Johnson | doi = 10.2307/2308750 | journal = American Mathematical Monthly | mr = 0103159 | pages = 387–389 | title = A tournament problem | volume = 66 | year = 1959}}

^[1]^[2]
}}

2 : Integer sequences|Comparison sorts

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。