局部优化的Bozosort能提高排序速度吗？

Question

首先，我是认真的:)

您有N个元素的数组，我们可以比较它们(例如，operator >工作)。

让我们尝试使用以下全新的排序算法(不稳定)对其进行排序。

首先，考虑“智能”优化的博佐索 --随机选择2个数组元素，比较它们，只有当第一个元素大于第二个数组元素时，才能进行交换。

标准优化的bozosort实现重复了这一点，直到数组被排序。然而，我们只做特定的次数，例如N/10或N。

在末端，应该对数组进行部分排序。至少在理论上，它将处于一个比之前更好的状态。

然后，我们使用一些其他排序方法，这得益于部分排序数组。假设合并排序(tim排序)或快速排序( quicksort / std:: sort )。

有些算法是不可能的，例如堆排序应该退出，因为它将首先构造堆，而部分排序并不重要。

我可以看到，这对于N^2算法(如插入或shell排序)来说是一个巨大的改进，但我不太确定N个log算法。

对这种分析有什么想法吗？

伪码：

template<typename T>
void sort(T *m, size_t size){
   const auto max = size / 10;
   for(size_t i = 0; i < max; ++i){
      const auto a = random(size);
      const auto b = random(size);
      if (m[a] > m[b]){
         using std::swap;
         swap(m[a], m[b]);
      }
   }

   std::sort(m, m + size);
}

Answer 1

是的，算是吧。

我们有，比如说，bozo +合并排序。

成本为O(N) + O(N log N)，即O(N log N)。

你是希望那个笨蛋能把那个木头N弄掉。

我们赢的唯一方法是如果bozo碰巧幸运的话，因为我们可以在O(N)时间内验证“数组已经排序”。让我们用两种不同的方式来追求它。

基本规则:输入数组应为整数1的随机排列。N，并且禁止鸽子孔/ 板蓝根排序。

1. 给定一个is_sorted()谓词，我们可以计算第二阶段mergesort不需要的概率，然后估计成本之和略小于O(N log )。
2. 给定一个识别(可能是空的)排序前缀的线性时间的find_first_unsorted_index()函数，我们可以计算出未排序后缀大小M上的概率分布。现在有了战斗条件，其中我们可能有O(N) > O(M log M)。

(要明确的是，让bozosort过程有固定的N个条目，比如10%，就把它牢牢地放在O(N)线性功的范畴中。)

这里有一个“排序前缀”的定义，可以在线性时间内运行。

遍历数组，比较成对的元素以验证它们是否被排序。所以请验证a[0] <= a[1]，然后是a[1] <= a[2]等等。

让max_prefix成为第一次违规的指标。例如，在[0, 1, 2, 4, 3]中，它将是3。在[1, 0]中，它是0。它是一个排序数组的N；is_sorted()谓词只输出它是否是N。

如果是正数，我们会记住最后的获胜值，last_value = a[max_prefix - 1]，然后继续扫描到结束。如果遇到任何小于last_value的值，则必须声明排序前缀长度为零，因为我们无法遍历前缀。

在发现第一次违规之前，我们可以在M测井M功小于N功的情况下提前保释。这降低了遇到低于last_value的扰流板值的风险。

改变基本规则会改变概率分布，但还不清楚这是否有用。

对大的、不同的正整数进行排序会使基排序作为一种可能性返回到表中。

对50到50混合布尔人的排序给博佐一个更好的机会获胜，但基数排序琐碎处理它在线性时间。

排序N-1零加上一个零将是最简单的分析情况，除非基数已经告诉我们答案是O(N)。