Why does this sorting algorithm properly sort the array?

[TheMathNoob]

Homework Statement

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?

Homework Equations

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.

 

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

 

[TheMathNoob]

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.

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.

 

[andrewkirk]

Sort the final 2/3 of the array

Now the elements in C are sorted relatively to the array

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.

 

[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.)

 

[TheMathNoob]

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.

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?

 

[andrewkirk]

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

 

[Jingfei]

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

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>yIs that correct?

 

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

 

[Jingfei]

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.

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

 

[andrewkirk]

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

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.

 

[Jingfei]

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.

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

 

[andrewkirk]

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)

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:

if there exist y in B(1) and x in C(1) such that x>y, there exists an element z in C(1) such that z is also in C(2)

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

Then for all elements z in S and for all elements i in A(2) z>i

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.