Search code examples
algorithmrecursionbubble-sortinduction

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

Give a list of unsorted elements. Initial condition is A=list of unsorted elements, p=1, N=total array size 

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)

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.

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)

My problem: I know that after complete the first n-1 for loop of sorting, the largest integer value in the array will sort at the last position. when the recursion of Bubble(A,p,N-1) is call, array size will be n-1,n-2,...n-n and the largest integer at the last will not compare anymore for next and forthcoming recursion call.(Is this a good proof?If no can anyone provide me a better proof?)

Question 3:Give a scenario that after an element moves towards p, it can move towards n.(unsolved)

My problem: I know that for the current for loop of 1 to n-1, if the A[i]>A[i+1] then it will swap where A[i+1] will be largest and A[i] will be smallest. Then when Bubble(A,p,N-1) is call, the integer value of array size of n-1 will be compare again. If A[i]>A[i+1] then swap. The elements will be compare and swap for n-1,n-2,...,n-n.(Is this a good scenario?If no can anyone provide me a better scenario?)

Solution

  • 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.

    The proof is by induction on N.

    Base case: When N = 1, the array is already sorted, and Bubble correctly does nothing and terminates immediately by if p >= N return.

    Induction hypothesis: assume Bubble correctly sorts lists of size up to and including k (strong induction).

    Inductive step: we must show Bubble correctly sorts lists of size k+1. On the initial invocation of Bubble, p is less than N = k+1 and so we skip over the first line of the algorithm. Next, the for loop can be shown (also using induction) to possess the following loop invariant: on the iteration i = m, A[m+1] will be greater than or equal to A[1] through A[m]. The loop, therefore, finishes with the greatest element in A[1], A[2], ..., A[k+1] at position k+1. It then makes the recursive call on a problem if size k which, by the induction hypothesis, Bubble is guaranteed to sort correctly. Since A[k+1] is the greatest element and is at the end, and since all earlier elements are sorted correctly by the recursive call to Bubble, the sorting is proven correct.

    (The inductive proof of the other one is left as an exercise. Choose as your base case N=2 and p=1. Then, hypothesize that the invariant is true up to k. Show it for k+1 by arguing about what the swap does. Then, based on the last value assumed by p, say what the final state of the array must be.)

    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)

    The proof is by contradiction. Consider an element at position i at the beginning of some invocation of Bubble is moved by the swaps in the for loop to position j > i. Assume that further swaps in the same invocation, or swaps in another invocation of Bubble, cause the position of that element to becme k with k < j. We need only consider the first such movement since if there is any there is a first. The first such movement is due either to a swap in the same invocation or a swap in another invocation. Consider these cases separately.

    1. swaps in the current invocation can only move elements forward, not backward. Since an element that was swapped during this invocation can never be the "next" element for any swap, it cannot move backward.

    2. swaps in other invocations of Bubble could potentially move the element, since the element will be the "next" element for one of the potential swaps; however, this will never happen since it would imply that there is a larger element earlier in the array, which would have been "bubbled" past the element in question on a previous invocation of "bubble". We assumed our element moved to the right before which means it was the largest one seen so far.

    Since these are the only two ways the element could move towards p and neither of these is possible, we have a contradiction, meaning our assumption that the element could move towards p is false.

    Edit: for question 3, consider the case of an array [3, 2, 1]. The first swap exchanges 3 and 2, moving 2 towards p. The second swap exchanges 3 and 1, moving 1 towards p. The first swap of the recursive invocation of Bubble exchanges 1 and 2, moving 2 back toward n. Generally, you'll get the described behavior a lot of you start with an array in reverse sorted order.