最少比较排序问题中S（15）和S（19）的解决

计算机科学与探索 ›› 2007, Vol. 1 ›› Issue (3): 305-313.

最少比较排序问题中S（15）和S（19）的解决

成维一,刘晓光+,王刚,刘璟

南开大学信息技术科学学院,天津 300071

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-10-20 发布日期:2007-10-20
通讯作者: 成维一

The results of S（15） and S（19） to minimum-comparison sorting problem

CHENG Weiyi,LIU Xiaoguang+,WANG Gang,LIU Jing

College of Information Science,Nankai University,Tianjin 300071,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-10-20 Published:2007-10-20
Contact: CHENG Weiyi

摘要/Abstract

摘要： 最少比较排序问题就是要研究在最坏情况下,对n个元素完成排序所需要的最少比较次数S（n）。1965年M.Wells用穷举法证明了S（12）＝30。2002年和2004年,M.Peczarski通过计算先后得到S（13）＝34,S（14）＝38,S（22）＝71。文章在Wells算法和Peczarski算法基础上,设计了一个新的PS算法,并改进了线性扩展计数算法,在并行机“南开之星”上计算得到S（15）=42,S（19）=58。

关键词: 最少比较排序, 最优排序, 线性扩展计数

Abstract: The minimum-comparison sorting is the problem of finding the minimum number of key comparisons needed to sort n elements in the worst case. Let S（n） be the minimum number of comparisons that will suffice to sort n elements. M.Wells found that S（12）=30 by an exhaustive search in 1965. With the help of parallel computer,M.Peczarski improved Wells algorithm and proved that S（13）=34,S（14）=38 and S（22）=71 in 2002 and 2004 respectively. The authors extend both Wells algorithm and Peczarski algorithm. Some new results that S（15）=42 and S（19）=58 are first proved on a parallel computer named NKStars.

Key words: minimum-comparison sorting, optimal sorting, linear extensions counting

成维一,刘晓光+,王刚,刘璟. 最少比较排序问题中S（15）和S（19）的解决[J]. 计算机科学与探索, 2007, 1(3): 305-313.

CHENG Weiyi,LIU Xiaoguang+,WANG Gang,LIU Jing . The results of S（15） and S（19） to minimum-comparison sorting problem[J]. Journal of Frontiers of Computer Science and Technology, 2007, 1(3): 305-313.