Journal of Frontiers of Computer Science and Technology ›› 2007, Vol. 1 ›› Issue (3): 305-313.
• 学术研究 • Previous Articles Next Articles
CHENG Weiyi,LIU Xiaoguang+,WANG Gang,LIU Jing
Received:
Revised:
Online:
Published:
Contact:
成维一,刘晓光+,王 刚,刘 璟
通讯作者:
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
摘要: 最少比较排序问题就是要研究在最坏情况下,对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。
关键词: 最少比较排序, 最优排序, 线性扩展计数
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.
成维一,刘晓光+,王 刚,刘 璟. 最少比较排序问题中S(15)和S(19)的解决[J]. 计算机科学与探索, 2007, 1(3): 305-313.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://fcst.ceaj.org/EN/
http://fcst.ceaj.org/EN/Y2007/V1/I3/305
/D:/magtech/JO/Jwk3_kxyts/WEB-INF/classes/