当输入大小较小时，为什么插入排序比快速排序快？ [英] Why is Insertion Sort faster than Quick Sort when the input size is small?

问题描述

我想得到理论原因而不是实验结果。
另外，我们如何确定何时将数据大小称为大还是小？

I want to get the theoretic reason not the experimental result. Also how can we determine when the data size is called small or large?

我并没有明确解释，我的意思是输入数据大小较小时，我们通常选择使用插入排序还是不使用快速排序，这是正确的。所以我想知道为什么吗？

I did not explained clearly, I meant when the input data size is small, we usually choose to use Insertion sort or not Quick Sort, that is right. So I want to know why is that?

推荐答案

请记住，在渐近分析中，我们忽略了常量因素。因此Quicksort的O（n log n）复杂度实际上是O（C（n log n）），其中C是一个未知常数。同样，插入排序的O（n ^ 2）实际上是O（C（n ^ 2））。我们将这些常数称为Cq和Ci。

Remember that in asymptotic analysis, we ignore constant factors. So Quicksort's O(n log n) complexity is really O(C(n log n)), where C is some unknown constant. Similarly, Insertion sort's O(n^2) is actually O(C(n^2)). Let's call those constants Cq and Ci.

因此，当（Ci * n ^ 2）<时，插入排序会更快。 （Cq *（n log n））。

So Insertion sort will be faster when (Ci * n^2) < (Cq * (n log n)).

从两种算法来看，Ci< Cq。插入排序非常简单。该算法不过是比较和交换而已，并带有一点循环开销。

It should be obvious from looking at the two algorithms that Ci < Cq. The insertion sort is incredibly simple. The algorithm is nothing but comparison and swap, with a little loop overhead thrown in.

Quicksort有点复杂，每次迭代需要更多的步骤，但迭代次数却更少。

Quicksort is a little bit more complex, requiring more steps per iteration, but fewer iterations.

考虑对五元素数组进行排序。插入排序会在最坏的情况下起作用：

Consider sorting a five element array. Insertion sort will do, at worst:

• 外循环控制变量的5个增量和比较


• 15个增量和内部循环控制变量的比较


• 15个元素比较


• 15个交换

• 5 increments and comparisons of the outer loop control variable
• 15 increments and comparisons of the inner loop control variable
• 15 element comparisons
• 15 swaps

现在查看 Quicksort ，该文件位于一般情况下，必须划分四个子数组。由5个元素组成的数组分为两个由3个元素和2个元素组成的子数组。 3-元素子数组进一步划分为1和2个元素的子数组。然后对两个2元素子数组进行分区。

Now look at Quicksort, which in the average case has to partition four subarrays. The 5-element array gets split into two subarrays of 3 and 2 elements. The 3-element subarray is further partitioned into subarrays of 1 and 2 elements. And then the two 2-element subarrays are partitioned.

所以 partition 方法将被调用四次。除了元素的比较和交换以及其他开销外，每个分区步骤还至少需要进行两次交换。将所有内容相加后，您会发现Quicksort每次迭代都会做更多的工作。当迭代次数较小时，即使插入迭代次数较多，插入排序也不会完成总工作量。

So the partition method will be called four times. Each partition step requires a minimum of two swaps in addition to the comparison and swapping of elements, and other overhead. When you add it all up, you see that Quicksort does more work per iteration. When the number of iterations is small, Insertion sort does less total work even though it does more iterations.

您可以进行分步分析来确定理论值。值小，其中插入排序将比Quicksort快。通常，这是通过计算基本运算来完成的，尽管定义有些灵活。在这种情况下，这很容易：比较，赋值或函数调用是基本操作。

You can do a step-by-step analysis to determine the theoretical value of "small," where Insertion sort will be faster than Quicksort. Typically that's done by counting "basic operations," although the definition is somewhat flexible. In this case it's pretty easy: a comparison, assignment, or function call is a "basic operation."

理论结果与实验得出的结果如何匹配将取决于在特定的计算机硬件上，以及在比较上有多昂贵。如果比较非常昂贵，那么您将需要选择进行最少比较的算法。但是，如果比较比较便宜（例如，比较数字，甚至是字符串，只要它们没有长的公共前缀），那么算法开销就是限制因素，简单的低效率算法就比复杂的高效算法优越。

How the theoretical result matches up with the experimentally derived result will depend on the particular computer hardware and also on how expensive comparisons are. If comparisons are very expensive, then you'll want to select the algorithm that does the fewest number of comparisons. But if comparisons are relatively inexpensive (comparing numbers, for example, or even strings provided that they don't have long common prefixes), then the algorithmic overhead is the limiting factor and the simple inefficient algorithm outperforms the complex efficient algorithm.

这篇关于当输入大小较小时，为什么插入排序比快速排序快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！