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

• 学术研究 • 上一篇    下一篇

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

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

  1. 南开大学 信息技术科学学院,天津 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   

  1. 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

摘要: 最少比较排序问题就是要研究在最坏情况下,对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