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

Question

给出一个未排序元素的列表。初始条件是 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)

问题一：通过对N的归纳证明算法的正确性。我的 Problem:How 我可以在 Bubble(A,p,N-1) 上使用 k+1 吗？我需要有人为我解释和证明。

问题2:Prove如果一个元素一旦向 n 移动，它就永远不会向 p 移动当前和所有即将到来的递归调用。（未解决）

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

问题3:Give一个元素向p移动后，可以向n移动的场景。（未解决）

我的问题：我知道对于当前的 1 到 n-1 循环，如果 A[i]>A[i+1] 那么它将交换 A[i+1] 最大的位置A[i] 将是最小的。然后调用Bubble(A,p,N-1)时，会再次比较n-1数组大小的整数值。如果 A[i]>A[i+1] 则交换。元素将被比较和交换为 n-1,n-2,...,n-n。（这是一个好的场景吗？如果没有，谁能给我一个更好的场景？）

Answer 1

Question 1: Prove the correctness of the algorithm by induction on N. My Problem:How can i use k+1 on Bubble(A,p,N-1)?I need someone explain and proof for me.

证明是对 N 的归纳

基本情况：当 N = 1 时，数组已经排序，并且 Bubble 正确地什么都不做并立即终止 if p >= N return。

归纳假设：假设 Bubble 正确排序大小不超过 k 的列表（强归纳）。

归纳步骤：我们必须证明 Bubble 正确排序大小为 k+1 的列表。在 Bubble 的初始调用中，p 小于 N = k+1，因此我们跳过算法的第一行。接下来，可以证明 for 循环（也使用归纳法）具有以下循环不变量：在迭代 i = m 上，A[m+1] 将大于或等于 A[1]通过 A[m]。因此，循环以 A[1], A[2], ..., A[k+1] 中位置 k+1 中的最大元素结束。然后它对一个问题进行递归调用 if size k 根据归纳假设，Bubble 可以保证正确排序。由于 A[k+1] 是最大的元素并且在末尾，并且由于所有较早的元素都通过对 Bubble 的递归调用正确排序，因此排序被证明是正确的。

(另一个的归纳证明留作练习。选择 N=2 和 p=1 作为你的基本情况。然后，假设不变量在 k 之前为真。显示它对于 k+1，通过争论 swap 的作用。然后，根据 p 假定的最后一个值，说出数组的最终状态必须是什么。）

Question 2:Prove that if an element once moves towards n, it will never move towards p for current and all forthcoming recursive calls.(unsolved)

反证法。考虑在 Bubble 的某些调用开始时位置 i 处的元素被 for 循环中的 swap 移动到位置 j > i。假设在同一个调用中进一步 swaps，或在另一个 Bubble 调用中 swaps，导致该元素的位置变为 k 和 k < j .我们只需要考虑第一个这样的运动，因为如果有任何运动，那就是第一个。第一个这样的移动是由于同一调用中的 swap 或另一调用中的 swap。分别考虑这些情况。

swaps只能向前移动元素，不能向后移动。由于在此调用期间交换的元素永远不可能是任何交换的 "next" 元素，因此它不能向后移动。
swaps 在 Bubble 的其他调用中可能会移动该元素，因为该元素将成为潜在 [= 之一的 "next" 元素32=]秒；然而，这永远不会发生，因为这意味着数组中较早的元素有一个更大的元素，在先前调用 "bubble" 时，它会 "bubbled" 超过相关元素。我们假设我们的元素之前向右移动，这意味着它是迄今为止看到的最大的一个。

由于这是元素可以向 p 移动的唯一两种方式，而这两种方式都不可能，所以我们有一个矛盾，这意味着我们关于元素可以向 p 移动的假设是错误的.

编辑：对于问题 3，考虑数组 [3, 2, 1] 的情况。第一次交换交换 3 和 2，将 2 移向 p。第二次交换交换 3 和 1，将 1 移向 p。 Bubble 递归调用的第一次交换交换 1 和 2，将 2 移回 n。通常，您会在很多情况下从反向排序的数组开始得到所描述的行为。

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

Can someone provide me a better proof and scenario for bubble sort compare to what i have proved

algorithm

recursion

bubble-sort

induction