1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sorting algorithm proof

  1. Apr 8, 2016 #1
    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. jcsd
  3. Apr 9, 2016 #2

    Tom.G

    User Avatar
    Science Advisor

    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.
     
  4. Apr 9, 2016 #3
    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.
     
  5. Apr 9, 2016 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  6. Apr 9, 2016 #5

    Tom.G

    User Avatar
    Science Advisor

    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.)
     
  7. Apr 9, 2016 #6
    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?
     
  8. Apr 9, 2016 #7

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    OK, and what if y is in A(2)?
     
  9. Apr 9, 2016 #8
    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?
     
  10. Apr 9, 2016 #9

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  11. Apr 9, 2016 #10
    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
     
  12. Apr 9, 2016 #11

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  13. Apr 9, 2016 #12
    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
  14. Apr 10, 2016 #13

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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



Similar Discussions: Sorting algorithm proof
  1. CG algorithm (Replies: 1)

  2. Algorithm Time (Replies: 4)

  3. Division Algorithm (Replies: 3)

Loading...