C:排序方法分析

Question

我有很多不同的排序算法,都有以下签名:

void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);

是否有任何用于分类的测试套件,我可以用它来进行实证比较？

Answer 1

这个详细的讨论,以及链接到您可能会发现有用的大量相关网页,还描述了一组用于测试排序算法的有用输入数据(出于原因,请参阅链接页面).总结:

1. 完全随机重组阵列
2. 已排序的数组
3. 已经按逆序排列
4. 电锯阵列
5. 一系列相同的元素
6. 已经排序的阵列有N个排列(N从0.1到10%的大小)
7. 已经对具有N个排列的逆序数组排序了数组
8. 具有重复(或关闭)键的正态分布的数据(仅用于稳定排序)
9. 伪随机数据(S&P500的日常值或十年的其他指数可能是一个很好的测试集;它们可从Yahoo.com获得)

Answer 2

关于分类的最终研究是Bob Sedgewick的博士论文.但是他的算法教科书中有很多好的信息,这些是我要寻找测试套件和方法的前两个地方.如果你有一个最近的课程,你会比我更了解; 上次我有一个课程,最好的方法是使用quicksort向下到大小为12的分区,然后在整个数组上运行插入排序.但答案的变化与硬件一样快.

Jon Bentley的Programming Perls书籍有一些关于排序的其他信息.

您可以快速启动包含的测试套件

• 随机整数

• 整数排序

• 反向排序整数

• 排序整数,略微不安

如果内存服务,这些是排序算法最重要的情况.

如果您要对不适合缓存的数组进行排序,则需要测量缓存效果. valgrind如果缓慢有效.

Answer 3

sortperf.py有一套精心挑选的基准测试用例，用于支持此处找到的文章，并在多年前使用 Python 进行 timsort 排序。请注意，最终，Java 也可能会转向 timsort，这要归功于 Josh Block（请参阅此处），所以我想他们已经编写了自己版本的基准测试用例 - 但是，我无法轻松找到参考到它。（timsort 是一种稳定的、自适应的、迭代的自然合并排序变体，特别适合具有引用对象语义的语言，例如 Python 和 Java，其中“数据移动”相对便宜[[因为所有移动的都是引用，也称为指针，不是无限大小的 blob；-)]]，但是比较的成本可能相对较高 [[因为比较函数的复杂性没有上限——但这适用于任何可以通过自定义排序来自定义排序的语言比较或密钥提取功能]]）。