Sorting algorithm proof

1. Apr 8, 2016

TheMathNoob

1. The problem statement, all variables and given/known data
Consider the following sorting algorithm for an array of numbers (Assume the size n of the array is divisible by 3):
• Sort the initial 2/3 of the array.
• Sort the final 2/3 and then again the initial 2/3.
Reason that this algorithm properly sorts the array. What is its running time?

2. Relevant equations

3. The attempt at a solution
I was just thinking if I can prove this by using element-wise proof. The array is divided into 3 sub arrays, call it A,B and C. As long as I am applying the algorithm on the array, I pick an element in each sub-array and show why it's not sorted by explaining why this element can be in an another sub-array. At the end I show why it's sorted.

Proof

Sort the initial 2/3 of the array
In B, we have the largest elements of the first 2/3 of the array sorted. The array is not sorted because some element in B may be greater than some element in C and some element in C may be less than some element in A.

Sort the final 2/3 of the array

Now the elements in C are sorted relatively to the array hence its elements which are the remaining elements of the array were sorted with the largest values of the first 2/3 of the array. A and B are not sorted relatively to the array because there could an element in C placed now in B less than some element in A.

Sort initial 2/3 of the array
Now A and B are sorted relatively to the array because A was sorted with the elements in C that could be less than the elements in A.

So A, B and C are sorted relatively to the array which implies the array is sorted.

Last edited: Apr 8, 2016
2. Apr 9, 2016

Tom.G

The proof looks correct.

Mostly, I'll leave the running time calc to those that are better qualified here. I will suggest that you look at how many sorts are done on what size array.

3. Apr 9, 2016

TheMathNoob

I don't quite understand how to analyze the sorting part hence we can use different sorts such as the quick sort or the merge sort.

4. Apr 9, 2016

andrewkirk

By this, I presume you mean that $\forall x\in C(2)\forall y\in B(2)\cup A(2): x>y$, where $C(n),B(n),A(n)$ indicate the sets of numbers in those thirds after $n$ sorts have been performed.

The claim needs to be proven, not just asserted. I needed the examination of two cases to prove this, based on whether $y$ is in $B(2)$ or in $A(2)$. The claim is easy to prove for the former case. For the latter, not quite so easy. An argument is needed.

5. Apr 9, 2016

Tom.G

Use the general equation for running time that is applicable to whatever sort you pick. Then insert appropriate factors into that general equation to match the way the problem is structured.
As long as you state in your answer which sort method the equation applies to, you should be OK.

P.S. Just as an extra learning oppotunity, compare the relative running times of sorting the array as the problem states, versus sorting it as one large array.

(Past my bedtime, will be back late tomorrow.)

6. Apr 9, 2016

TheMathNoob

If y is in B(2) then x>y because previously every element in C was sorted with every element in B. Is this what you are looking for?

7. Apr 9, 2016

andrewkirk

OK, and what if y is in A(2)?

8. Apr 9, 2016

Jingfei

For all x in B(1) and for all y in A(1) : x>y
For all z in C(2) and for all x in B(2) : z>x
A(1)=A(2) hence A is not manipulated in A(2).
Therefore For all y in A(2) and For all z in C(2) : z>y

Is that correct?

9. Apr 9, 2016

andrewkirk

Alas, no. There is no justification for the last line 'Therefore For all y in A(2) and For all z in C(2) : z>y', because B(1) is not the same as B(2).

You're getting closer though.

10. Apr 9, 2016

Jingfei

For all x in B(1) and for all y in A(1) : x>y
For all x in B(1) and for all i in B(2) : i<=x
For all z in C(2) and for all i in B(2) : z>i
A(1)=A(2) hence A is not manipulated in A(2).
Therefore For all y in A(2) and For all z in C(2) : z>y

11. Apr 9, 2016

andrewkirk

The conclusion doesn't follow from the premises. For it to follow we would need line 2 to have $i\geq x$, which would then give us $z>i\geq x>y$, but we don't have that, we only have $x\geq i$.

Here's a hint. I don't think I can go any further than that without giving too much away. Think about the position, after the second sort, of the element that was the smallest element of B after the first sort.

12. Apr 9, 2016

Jingfei

First case
if there exist y in B(1) and x in C(1) such that x>y, there exist an element x in C(1) such that x is in C(2)
Call this set of x's S. Then for all elements z in S and for all elements i in A(2) z>i

Second case
if there exist y in B(1) and x in C(1) such that x< y, there exist an element y in B(1) such that y is in C(2)
Call this set of y's M. Then for all elements z in M and for all elements i in A(2) z>i

so S union M = C(2)
therefore For all w elements in C and all q elements in A(2), w>q

Last edited: Apr 9, 2016
13. Apr 10, 2016

andrewkirk

Unfortunately this sentence does not have a meaning. If we have written $\exists x\in C(1)$ once, we cannot write it again because if we do, from that point onwards the variable symbol $x$ is ambiguous.
You can make it meaningful by replacing the second x by z, as follows:
Now the statement is meaningful. It also happens to be true. But its truth is not obvious, so a proof of its truth is required.

The next statement
is meaningful, and true, but not obvious. Hence again, the proof that it is true needs to be written down.

Similar comments apply to the second case.

If you make the corrections and fill in the missing steps, you will end up with a valid proof. It will be longer than one that uses the above hint, but that doesn't matter. It will be original, and that's good.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted