kaist-cp/cs500

How to proof the lemma of odd-even sort

Closed this issue · 7 comments

HaritzPuerto commented

Hello,

Does anyone know how to proof the lemma of odd-even sort? I even don't know how to start...

Thank you!
image

ppnchb commented

Because both A and B are sorted, A_j is not smaller than j-1 elements, from A_1 to A_j-1. (Assuming index starts in wrong way from 1.) Likewise, B_i-j is not smaller than i-j-1 elements.
Assuming A_j >= B_i-j, A_j is not smaller than j-1 elements from A, and at least i-j elements from B. So, A_j is not smaller than at least i-1 elements in C, thus A_j is located at index >= i in C.
Therefore, A_j = max(A_j, B_i-j) >= C_i. Latter inequality also holds when B_i-j >= A_j.

So far, it is sufficient to prove C_i <= min_j (max (A_j, B_i-j) ), but to prove equality the existance of such j is needed.
Though it is obvious that C_i is not smaller than exactly i-1 elements both from A and B. Some elements, let's say k elements, are from A, and i-k-1 elements are from B.
Assuming C_i is from B. Then, C_i = B_i-k, and C_i >= A_k.
Thus, max(A_k, B_i-k) = B_i-k = C_i, which proves that if j = k, the equality holds, and the resulting value is the minimum.
It is also true when C_i is from A, so the equality is always true regardless of the assumption.

  • 👍7
jeehoonkang commented

Thanks for your proof! I'd like to make a few comments that may improve your proof.

  • I belive the first paragraph is proving C_i >= min_j (max(A_j, B_(i-j))), and the second paragraph is proving C_i <= min_j (max(A_j, B_(i-j))). It is the common strategy for proving the equality. I think it's better to point out the treategy upfront.

  • Though it is obvious that C_i is not smaller than exactly i-1 elements ...: not true. First of all, C_i itself is not smaller than itself. So C_i is not smaller than at least i elements. If there are duplicate elements, C_i may be not smaller than more than i elements.

  • 👍3
CauchyComplete commented

@jeehoonkang I think your first comment is wrong. The first paragraph is not proving the opposite side of the inequality. The proof first shows that C_i <= max(A_j, B_(i-j)) and then shows the equality holds. It's not about proving <= and >= to get =.

jeehoonkang commented

Therefore, A_j = max(A_j, B_i-j) >= C_i

@CauchyComplete Since j can be an arbitrary index above, we can easily deduce that min_j(max(A_j, B_(i-j))) >= C_i, which is the inequality I mentioned. Am I misunderstanding something?

CauchyComplete commented

@jeehoonkang Please see your previous comment again then you’ll know. The direction is the opposite.

jeehoonkang commented

@CauchyComplete Ah I see. Thank you for pointing out that!

I still think it's proof strategy is proving <= and >=: the first paragraph is proving C_i <= min_j (max(A_j, B_(i-j))), and the second paragraph is proving C_i >= min_j (max(A_j, B_(i-j))) (the direction is opposite to what I said in the previous comment). And I'm asking @ppnchb to make clear that the second paragraph is doing what I just said.

jeehoonkang commented

At this stage of the semester, I'd like to close tech-related issues.