PDF《(19)的解决 *》

ISSN 1673-

9418 CODEN JKYTA8 Journal of Computer Science and Frontiers 1673- 9418/2007/01( 03) - 0305-

09 E- mail: fcst@public2.

bta.net.cn http: //www.ceaj.org Tel: +86- 10-

51616056 最少比较排序问题中 S (15) 和S(19) 的解决 * 成维一, 刘晓光+ , 王刚, 刘ZCHENG Weiyi,LIU Xiaoguang+ ,WANG Gang,LIU Jing 南开大学 信息技术科学学院, 天津

300071 College of Information Science,Nankai University,Tianjin 300071,China +Corresponding author:E- mail:[email protected] CHENG Weiyi,LIU Xiaoguang,WANG Gang,et al. The results of S( 15)and S( 19)to minimum- comparison sorting problem. Journal of Computer Science and Frontiers,2007, 1( 3) : 305- 313. Abstract:The minimum- comparison sorting is the problem of finding the minimum number of key compar- isons 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. 关键词: 最少比较排序;

最优排序;

线性扩展计数 文献标识码: A 中图分类号: TP301.6 * the Key Project of National Natural Science Foundation of China under Grant No.90612001( 国家自然科学基金重大项目) ;

the Tianjin Science and Technology Development Plan Foundation of China under Grant No.043185111- 14( 天津市科技发展 计划) ;

the Science &

Technology Innovation Fund of Nankai University( 南开大学科技创新基金) . Received 2007- 08, Accepted 2007- 10. Journal of Computer Science and Frontiers 计算机科学与探索 2007, 1( 3)

1 引言 最小比较排序问题是研究在最坏情况下,对n个元素完成排序所需要的最少比较次数.这一问题 是排序算法的一个基础性问题.Steinhaus 在《 Math- ematical Snapshots》 一书中首次提出了最少比较排序 问题[1] , Knuth 在《 The Art of Computer Programming》 第3卷中也专门用一节来讨论这一问题[2] .比较次数 虽然不是衡量排序算法优劣的唯一标准,但研究最 少比较排序问题有助于更好地理解排序过程的本 质, 从而设计出更加高效的排序算法. 现有研究证明最小比较排序问题具有理论下 界: 设S( n) 是将 n 个元素排序所需要的最少比较次 数, 根据信息论, 它具有如下的理论下界: S( n) ≥「 lg n !! =Cn ( 1)

1956 年, Demuth 证明了对

5 个元素的排序最少 需要进行

7 次比较, L.Ford 和S.Johnson 对这一方法 进行了推广, 设计了合并插入排序算法[1, 3] .合并插入 排序是现有的在最坏情况下的比较次数最少的排序 算法.用Fn 表示合并插入算法对 n 个元素进行排序 所需要的最大比较次数.Fn 和Cn 的比较如表 1. 不妨设集合: N1={2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 20, 21}, N2 ={12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24},对 n∈N1 有Fn=Cn, 所以 S( n) =Fn, 即合并插入方法是 最优的. 对 n∈N2 有Fn=Cn+1. 因此, 只要能够证明 S( n) >