代码之家 › 专栏 › 技术社区 › James

与我已经证明的相比,有人能为冒泡排序提供更好的证明和场景吗

induction bubble-sort recursion algorithm

2

James · 技术社区 · 8 年前

初始条件是A=未排序元素列表,p=1,N=总数组大小

Bubble(A,p,N)
 if p>=N return
 for i=p to N-1
  if A[i]>A[i+1]
   swap(A[i],A[i+1])
 Bubble(A,p,N-1)

问题1:通过对N的归纳来证明算法的正确性。

我的问题是:我知道在完成第一个n-1 for排序循环后,数组中最大的整数值将在最后一个位置排序。当调用气泡(A,p,N-1)的递归时,数组大小将为N-1,N-2,…N-N,最后一个最大整数将不再与下一个和即将到来的递归调用进行比较。(这是一个很好的证据吗?如果没有,谁能给我提供更好的证据?)

1 回复 | 直到 8 年前

1

Patrick87 8 年前

问题1:通过对N的归纳来证明算法的正确性。我的问题:如何在气泡(A,p,N-1)上使用k+1?我需要有人给我解释和证明。

基本情况:当N=1时,数组已排序,并且 Bubble if p >= N return .

归纳假设:假设 泡 正确排序大小小于等于的列表 k (强归纳)。

归纳步骤:我们必须展示正确排序大小列表 k+1 , p 小于 N = k+1 我们跳过了算法的第一行。接下来 for 循环可以显示(也可以使用归纳法)具有以下循环不变量:在迭代中 i = m , A[m+1] 将大于或等于 A[1] A[m] 因此,循环以最大的元素结束 A[1], A[2], ..., A[k+1] 在位置 k+1 。然后,它对问题进行递归调用,如果大小 k 泡 保证正确排序。自从 A[k+1] 泡

(另一个的归纳证明留作练习。选择N=2和p=1作为基本情况。然后,假设不变量在 k k+1 通过争论 swap 做然后,根据假设的最后一个值 ,说明阵列的最终状态必须是什么。)

问题2:证明如果一个元素一旦向n移动,对于当前和所有即将进行的递归调用,它永远不会向p移动。(未解决)

i 在调用 交换 s在 对于 循环到位置 j > i 在同一调用中,或 交换 泡 k < j 我们只需要考虑第一次这样的运动,因为如果有,就有第一次。第一次这样的运动是由于 交换 在同一调用或在另一次调用中。分别考虑这些情况。

当前调用中的只能向前移动元素,不能向后移动。由于在此调用期间交换的元素永远不会是任何交换的“下一个”元素,因此它不能向后移动。
其他调用中的可能会移动该元素,因为该元素将是其中一个潜在元素的“下一个”元素 s然而,这永远不会发生,因为这意味着数组中早期有一个更大的元素,在之前调用“bubble”时,该元素会“冒泡”超过所讨论的元素。我们假设我们的元素移到了之前的右侧,这意味着它是迄今为止看到的最大元素。

因为这是元素可以朝着的唯一两种方式这两者都不可能,我们有一个矛盾,这意味着我们假设元素可以朝着 p 是假的。