《归并排序问题集》由会员分享，可在线阅读，更多相关《归并排序问题集（7页珍藏版）》请在金锄头文库上搜索。
1、归并排序问题描述：假设某一数组的项目未排序，这些项目将被拆分为相同大小的两半， 并 对每一半进行排序，然后将这两半合并成一个有序数组。通过调用归并排序 （Mergesort） 例程，对每一半进行递归排序（该例程会将数组拆分为两半，对每 一半执行排序，然后将这两半合并成一个有序数组）。可以通过使用某些数据结 构（通常为堆栈） 模拟递归调用来编写任何递归算法的迭代版。目标：本次挑战的目标是编写一个归并排序算法的并行（线程化）版。应用程序 将 会读取一个在运行时选定的输入文本文件, 该文件包含的是将要排序的一组 整数。文件的第一行将是将要排序的整数的总数（N）,后面跟有N个整数，每 行一个。文件内的
2、整数数量将小于2辽8 - 1。排序后的结果必须输出到另一个 文本文件（sor ted.ou t）,每行一个整数。限制：不可使用英特尔 线程构建块并行排序算法和其他任何外部排序库函数。 也不可使用其他任何排序算法在归并排序算法的递归过程中制造“短路”。因为 应用程序会在执行过程中的某些时候合并相同大小的列表。有关归并排序问题集的问题摘自Clay于2008年4月的博客，如果想要参与讨论，请点击这里问答一:问题：我有一个问题，是关于“不可使用其他任何排序算法在归并排序算法的递归过程 中制造短路。因为应用程序会在执行过程中的某些时候合并相同大小的列 表。”这一限制的。是否可以将归并排序算法（例如，四个
3、元素组成的数组）展 开成为线性顺序排列的比较交换运算，并对这些运算进行硬编码？回答：不可以，按该问题的描述，禁止这样做。问答二问题：我有一个关于问题描述的问题。可以对算法做一些改进吗？例如，二分归并排序 或多路归并排序。还有，N的个数为多少？回答：嗯，我们还没有考虑到这一点。但只要是归并排序算法，尤其是自身趋于并行时， 就可以对它做一些改进。一定要将您选择的算法以及在源文件中编码的方法记录 下来。N的最大值为（2辽8）-1。但您可以放心的是，这个数据一定适合该测试机的内 存。问答三：问题：由于传统的归并排序会占用数据设定的两倍空间，内存可以存得下所有的数据 吗？回答：可以，内存会为复制的数据备
4、有足够的空间。问答四：问题：Knuth 在 TAOCP 中描述了许多不同的通过合并来排序的方法。例如，在 5.2.4 部分中的算法S,该算法并没有使用问题描述中提到的堆栈。还有Batcher的 通过合并交换排序（5.2.2部分的算法M）。这些合并排序的算法可用吗？如果 可用，可以对它们进行合并吗？回答：我有 TAOCP 第三册的初版（翻箱倒柜才找到），我们认为算法 S（5.2.4） 是传 统的归并排序算法，是可用的。算法 M （5.2.2） 也是可用的。考虑到已知例子的数据的比较和运转，我们可以看到正在合并的排序列表（尽管它们并非在同一物理位置上）。房间分配问题集的评判准则摘自Clay于200
5、7年12月5日的博客，如果想要参与讨论，请点这里让我先来解释一下这个问题集中执行分数与时间分数的计算方法吧。对于运行的每个数据集，每位参赛选手都将获得一个执行时间排名和一个最终TD排名。时间越短，排名越高；TD分数越低，排名也越高。数字越小表示排名 越“高”。TD分数的排名将先乘以三（3）,然后再加到执行时间的排名上。所 有数 据集的排名总合将加在一起，最终生成一个净分数（ Net Score ） 。净分数 最低的参赛者将获得 100 分，净分数第二低的参赛者将获得 99 分，以此类推。（举例如下）我们使用乘数的目的是为了更好地进行分组。此举试图避免程序只是简单地读取 数据、在同组作品的基础上
6、稍做改动，便输出自己的结果。这种程序可能会实 现 最低的执行时间，但是也将有可能得到最差的 TD 最终分数。另一方面，虽然用 完 120 秒的程序可获得最佳的最终 TD 分数，但他将在执行时间中排名最低。如果第三位参赛选手使用了 50秒，并获得了一个TD分数，接近最佳得分（由 另一位用满 2 分钟的选手获得），那么我们认为他更应该获得一个很好的最终 总分。我们采用这种计分方法，是为了让所有参赛选手都能思考一下：花费更多时间以 求提高最终 TD 分数，以及花费较短时间来获得相近得分（通过线程）之间的利 弊权衡。举例:时间排名1TD排名净分数总分数目标平台-Windows摘自Clay于2007年1
7、1月15日的博客，如果想要参与讨论，请点这里为了尽可能多地为那些希望深入了解评价平台的人们提供更多信息，我们在此提 供了一些关于目标处理器及编译器软件的系统和软件信息。遗憾地是，由于恰 巧 赶上系统（这些系统在我开始撰写本消息前，刚刚断电）迁移前的周末，因此目 前我们无法为您提供所有的较小版本号。下面是我们记录的有关系统信息的一个 列表。一旦机器恢复运行，我们将获得更多详情，并在这里发布。（请注意：这些规范会随着硬件或软件的升级而有所更改，届时不会发出警告。） 操作系统（OS）版本：Microsoft Windows Server 2003 64 位企业版 Service Pack 2 Vis
8、ual Studio 2005 （8.0.x） and .NET Framework 2.0.x 英特尔 编译器 10.0.x （包括 64 位和 32 位两种版本） 英特尔 线程构建模块（2.0 版） Sun Java version 6.0处理器应与Linux系统上所用系统相同（2.667 GHz、4GB内存）。如果您对提交信息所用的编译器有任何特殊要求，请务必明确标注在您的构建 说明中。评委将尽全力满足您的要求。目标平台 - Linux摘自Clay于2007年11月15日的博客，如果想要参与讨论，请点这里为了向那些希望深入了解评价平台的人们提供更多信息，我们将在下文中列举一 些常见查询命
9、令中出现的有关目标处理器及编译器软件的具体规范。（请注意： 这些规范会随着硬件或软件的升级而有所更改，届时不会发出警告。）userl7 $ uname - aLinux XXXXX-YY-ZZZZZZ 2.6.9-42.ELsmp #1 SMP Wed Jul 12 23:32:02 EDT 2006 x86_64 x86_64 x86_64 GNU/Linuxuserl7 $ g+ -vReading specs from /usr/lib/gcc/x86_64-redhat-linux/3.4.6/specs Configured with: ./configure -prefix二/us
10、r -mandir二/usr/share/man -infodir二/usr/share/info -enable-shared -enable-threads二posix -disable-checking -with-system-zlib -enable-_cxa_atexit-disable-libunwind-exceptions -enable-java-awt二gtk-host二x86_64-redhat-linuxThread model: posix gcc version 3.4.6 20060404 (Red Hat 3.4.6-3)user17 $ icc - VInt
11、el(R) C Compiler for applications running on Intel(R) 64, Version 10.1 Build 20070913 Package ID: l_cc_p_10.1.008 Copyright (C) 1985-2007 Intel Corporation. All rights reserved.user17 $ tail -n 24 /proc/cpuinfo processor : 7vendor_id : GenuineIntel cpu family : 6model : 15model name : Genuine Intel(
12、R) CPU 2.66GHz stepping : 5cpu MHz : 2666.723cache size : 4096 KBphysical id : 1 siblings : 4 core id : 7 cpu cores : 4 fpu : yesfpu_exception : yescpuid level : 10wp : yesflags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm syscall lm pni monitor ds_cpl est tm2 cx16 xtprbogomips : 5332.64clflush size : 64 cache_alignment : 64 address sizes : 36 bits physical, 48 bits virtualpower management:
