2. (24 points) Consider the following version of Partition for the quicksort alg

Question

2. (24 points) Consider the following version of Partition for the quicksort algorithm. Partition (A, p, r) x = A[p] i=r+1 for (j = r; j p; j-) i=i-1 exchange A[i] and ALj] exchange A[i-1] with A[p] return i-1 Consider the following array A = (8 3 10 11 4 2 9) (The index of A start with 0). Suppose we call Partition(A, 0, 6). Show the content of i, j and A every time the condition (j >p) is checked. You should write your answer in a table form like below: a. 6 7 83 1041129 Come up with a loop invariant for the for loop Prove that your loop invariant is correct using the following step b. c.

Explanation / Answer

quick sort program

#include <iostream>

using namespace std;

void quick_sort(int[],int,int);

int partition(int[],int,int);

int main()

{

    int a[50],n,i;

    cout<<"How many elements?";

    cin>>n;

    cout<<" Enter array elements:";

    

    for(i=0;i<n;i++)

        cin>>a[i];

        

    quick_sort(a,0,n-1);

    cout<<" Array after sorting:";

    

    for(i=0;i<n;i++)

        cout<<a[i]<<" ";

    

    return 0;        

}

void quick_sort(int a[],int l,int u)

{

    int j;

    if(l<u)

    {

        j=partition(a,l,u);

        quick_sort(a,l,j-1);

        quick_sort(a,j+1,u);

    }

}

int partition(int a[],int l,int u)

{

    int v,i,j,temp;

    v=a[l];

    i=l;

    j=u+1;

    

    do

    {

        do

            i++;

            

        while(a[i]<v&&i<=u);

        

        do

            j--;

        while(v<a[j]);

        

        if(i<j)

        {

            temp=a[i];

            a[i]=a[j];

            a[j]=temp;

        }

    }while(i<j);

    

    a[l]=a[j];

    a[j]=v;

    

    return(j);

}

d. a loop invariant is some predicate (condition) that holds for every iteration of the loop.

By itself, a loop invariant doesn't do much. However, given an appropriate invariant, it can be used to help prove the correctness of an algorithm. The simple example in CLRS probably has to do with sorting. For example, let your loop invariant be something like, at the start of the loop, the first ientries of this array are sorted. If you can prove that this is indeed a loop invariant (i.e. that it holds before and after every loop iteration), you can use this to prove the correctness of a sorting algorithm: at the termination of the loop, the loop invariant is still satisfied, and the counter i is the length of the array. Therefore, the first i entries are sorted means the entire array is sorted.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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