通过使用最小交换交换相邻元素来对序列进行排序

Question

我们有一个未分类的N个数字序列(1,2,3,4,... N).我们可以通过按特定顺序交换相邻元素来对整个序列进行排序.给定序列,如何计算对序列进行排序所需的最小可能交换.

例如,考虑序列{4,2,5,3,1}.

对此进行排序的最佳方法是按以下顺序使用7次交换

1. 交换3,1:{4,2,5,1,3}
2. 交换5,1:{4,2,1,5,3}
3. 交换4,2:{2,4,1,5,3}
4. 交换4,1:{2,1,4,5,3}
5. 交换2,1:{1,2,4,5,3}
6. 交换5,3:{1,2,4,3,5}
7. 交换3,4:{1,2,3,4,5}

一个贪婪的算法并没有证明是富有成效的.一个反例很容易构建.接近解决方案的下一个明显选择是动态编程.

假设我们有一个未排序的序列:{A1,A2,... Ai,A(i + 1),...,An}.我们知道对序列{Ai,A(i + 1),...,An}进行排序所需的最小交换次数是Min [Ai,A(i + 1),...,An}.问题是找到Min [A(i-1),Ai,...,An].

好吧,我想到的第一个想法就是添加将A(i-1)放在已经排序的序列{Ai,...,An}中的正确位置所需的步骤数.这是有效的:问题中给出的例子已经使用完全相同的方法解决了.

但我无法证明这个解决方案的有效性.这种情况经常发生在我身上.当我认为我已经解决了问题时,我能做的最好的就是获得一个"直观"的证据.我在高中并且没有正确的算法训练.我纯粹出于兴趣而这样做.

是否有严格的数学符号表明这个问题可以转化为正式的证明？这种符号可以扩展到其他问题吗？怎么样？如果能够以高中生可以理解的形式呈现,我将不胜感激.

Answer 1

这是一个经典的算法问题.如果交换的最小数量等于数组中的反转数.如果我们有索引i和索引j使得a _i > a _j且i <j则这称为反转.让我们证明这个说法!我在途中需要一些引理:

引理1:如果没有两个相邻元素的反转,则对数组进行排序.
证明:假设没有两个相邻元素形成反转.这意味着对于区间[0,n-1]中的所有i,_i <= a _{i + 1}.由于<=是传递性的,这意味着数组已经排序.

引理2:两个相邻元素的单个交换将使阵列中的反转总数减少至多1.
证明:当我们交换两个相邻元素a _i和a _{i + 1时}它们相对于所有其他元素的相对位置在数组中将保持不变.对于在_{i + 1}之后的所有元素,它们仍将在_{i + 1之后,}并且对于_i之前的所有元素,它们仍将在a _i之前.这也意味着如果_i或_{i + 1}与元素a _j形成反转,那么在交换之后它们仍然会与它形成反转.因此,如果我们交换_i和_{i + 1,}我们将只影响这两个元素用于形成的反转.由于两个元素可能只参与一个反转,我们也证明了这个引理.

引理3:我们需要至少执行相邻元素的NI交换,以便对数组进行排序,其中NI是数组中的反转数.
证明:在排序数组中没有反转.同样根据引理2,单个交换可以将反转次数减少至多一次.因此,我们需要执行至少与反转次数一样多的交换.

引理4:我们总是可以对执行相邻元素的NI交换的数组进行排序,其中就像NI一样,数组中的反转次数也是如此.
证明:如果我们假设在我们的数组中没有两个相邻元素的反转,那么根据引理1,数组将被排序并且我们完成了.
否则,至少有一对相邻元素形成反转.我们可以交换它们,从而减少反转总数一次.我们可以完全按照NI时间继续执行此操作.

现在我从答案开始就证明了我的陈述.

剩下的唯一问题是如何计算给定数组中的反转次数.您可以使用稍微修改合并排序来执行此操作,您可以在合并阶段累积反转.您可以查看此答案,了解有关如何实现该问题的详细信息.算法的总体复杂性是O(n*log(n)).