| 最少比较排序问题中S(15)和S(19)的解决 |
| |
| 引用本文： | 成维一,刘晓光,王刚,刘璟.最少比较排序问题中S(15)和S(19)的解决[J].计算机科学与探索,2007,1(3):305-313. |
| |
| 作者姓名： | 成维一 刘晓光 王刚 刘璟 |
| |
| 作者单位： | 南开大学,信息技术科学学院,天津,300071;南开大学,信息技术科学学院,天津,300071;南开大学,信息技术科学学院,天津,300071;南开大学,信息技术科学学院,天津,300071 |
| |
| 基金项目： | 国家自然科学基金
,
天津市科技发展基金
,
南开大学校科研和教改项目 |
| |
| 摘 要： | 最少比较排序问题就是要研究在最坏情况下,对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。
|
| 关 键 词： | 最少比较排序 最优排序 线性扩展计数 |
| 修稿时间： | |
The results of S(15) and S(19) to minimum-comparison sorting problem |
| |
| CHENG Weiyi,LIU Xiaoguang,WANG Gang,LIU Jing.The results of S(15) and S(19) to minimum-comparison sorting problem[J].Journal of Frontier of Computer Science and Technology,2007,1(3):305-313. |
| |
| Authors: | CHENG Weiyi LIU Xiaoguang WANG Gang LIU Jing |
| |
| Affiliation: | College of Information Science,Nankai University,Tianjin 300071,China |
| |
| 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. |
| |
| Keywords: | minimum-comparison sorting optimal sorting linear extensions counting |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机科学与探索》浏览原始摘要信息 |
|
点击此处可从《计算机科学与探索》下载全文 |
|
