From the sample implementation of quicksort below,take a look at the partition m

Question

From the sample implementation of quicksort below,take a look at the partition method and identify an appropriate invariant for the while loop, and prove that it is indeed an invariant. Then prove that the partition method is correct,that is, prove that the postcondition is always true when the method returns.

Code:
quicksort(item_type s[], int 1, int h)
{
int p; // index of partition

if((h-1)>0){
p = partition(s,1,h);
quicksort(s,1,p-1);
quicksort(s,p+1,h);
}
}

Explanation / Answer

In order to prove that an algorithm is correct, it is necessary to know what the problem to be solved is. There must be a specification for the problem. This is usually written in a formal specification language such as Z or VDM. Discovering if an algorithm is correct from its specification is a non-computable problem. It is up to the programmer to prove correctness. One way of doing this is to use assertions. An assertion is a statement about the state of the machine during execution of the program. There are three types - preconditions, postconditions and loop invariants. The precondition is a true statement about the state of the machine before an operation begins. The postcondition is a statement about the state of the machine after the operation has terminated. The operation here could be a C statement, a block of C statements or an algorithm. A loop invariant is a statement about the state of the machine during execution of a loop. If it can be shown that the postcondition will be true if the algorithm terminates then the program is said to be partially correct. If the program is partially correct and it can be proved to always terminate then it is called totally correct. To prove total correctness, it is necessary to prove that some value increases or decreases every time the loop executes until the loop condition is satisfied. Example: prove the correctness of a factorial algorithm. f=1; n=1; /* precondition {f=n!,n=1} */ do { n=n+1; /* {f=(n-1)!,n>1} */ f=f*n; /* {f=n*(n-1)!,n>1} */ /* loop invariant {f=n!,n>1} */ } while(n!=10); /* postcondition {f=n!,n=10 } */ This algorithm is totally correct because the loop invariant will always be true since n! is defined as n*(n-1)!. It will always terminate because n starts at 1 and increases by one each time round the loop, n must therefore reach 10. Quicksort again uses the technique of divide-and-conquer. We proceed as follows: 1. Pick an arbitrary element of the array (the pivot). 2. Divide the array into two subarrays, those that are smaller and those that are greater (the partition phase). 3. Recursively sort the subarrays. 4. Put the pivot in the middle, between the two sorted subarrays to obtain the ?nal sorted array. void qsort(int[] A, int lower, int upper) //@requires 0

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.