GATE CSE 2017 Set 2 | Question: 43

Question

Consider the following snippet of a C program. Assume that swap $(\&x, \&y)$ exchanges the content of $x$ and $y$:

int main () {
    int array[] = {3, 5, 1, 4, 6, 2};
    int done =0;
    int i;
    while (done==0) {
        done =1;
        for (i=0; i<=4; i++) {
            if (array[i] < array[i+1]) {
                swap(&array[i], &array[i+1]);
                done=0;
            }
        }
        for (i=5; i>=1; i--) {
            if (array[i] > array[i-1]) {
                swap(&array[i], &array[i-1]);
                done =0;
            }
        }
    }
    printf(“%d”, array[3]);
}

The output of the program is _______

Comments

value of done variable is crux of the problem. Continue looping until “done” equals 1 and comes out of the loop.

---

I forgeted to again execute while loop and gets answer 4.but now realized my mistake

---

commited the same mistake :(

Answer 1

Well, the above program is sorting the array in descending order.

Initially, while loop starts execution by evaluating the iniatial condition

while(done==0)
 

For the first time the first for loop will be executed completey, the content of array will be as follows :

$5,3,4,6,2,1$

After the second for executed completey the content of array will be as follows:

$6,5,3,4,2,1$

But the value variable done is still $0$ so while loop will execute again,so now the content of array after executing the first for loop will be $6,5,4,3,2,1$ and no change in second for loop but still the done variable is $0$.

So, while loop execute again,now done variable is modified to $1$ and there will be no change in done variable because inside first and second for loop no if condition will satisfied .

Finally, the while condition is evaluted false and value of $array[3]$ will be printed which is $3$. 

Comments

nice explanation @manojk and thanks for your help

---

1 correction needed

swap(&array[i],& array[i-1])

---

I did a very little mistake and get an answer $4$.Because I run while loop only once.

Actually, while loop run $3$ times($1$st for loop $+ 2$nd for loop), $4$th time when done$=1$,condition false.

---

Other way to look at this problem

variable done is set to 0 initially and once we enter into while loop it is 1. Now While loop will be executing till done is 0. Snippet responsible for making our done =1 to 0 are two if conditions i.e when they are always false done will never become 0 and both the conditions are violated simultaneously when array is in descending order.

Answer 2

when first for is executed then, array will be - 5,3,4,6,2,1

and when the second for loop is executed then, array will be - 6,5,3,4 2,1

but the execution of while loop is not terminated here, because the value of variable done is 0.

so the first for  loop is second time executed then the array will be - 6,5,4,3,2,1  . Till here the whole array is sorted in descending order so when the second for loop is second time executed then there will be no change in the array .

but the value of variable done is 0 now , so the while loop condition is true and while loop executes again but this time no any for loop condition will be true so the value of the variable done will be 1. The execution of while loop is termintes. 

so, array[3]= 3

Answer 3

Here's the code with a full explanation.

int main () {
    int array[] = {3, 5, 1, 4, 6, 2}; /*any array starts with 0 index*/
    int done =0;
    int i;
    /*
    This program actually sorted the array in descending order.
    */
    while (done==0) {
        done =1; /* It will break the while loop
                   if the value of done is unchanged  */

        /*
        This for loop below actually sorts the array from
        the index 0 to 4 in descending order.
        */
        for (i=0; i<=4; i++) {
            if (array[i] < array[i+1]) { 

            /*If the array becomes sorted in descending order,
              this condition will not hold.*/

                swap(&array[i], &array[i+1]);
                done=0;
            }
        }

        /*
        This for loop below actually sorts the array from
        the index 1 to 5 in descending order.
        */

        for (i=5; i>=1; i--) {
            if (array[i] > array[i-1]) {

            /*If the array becomes sorted in descending order,
              this condition will not hold.*/

                swap(&array[i], &array[i-1]);
                done =0;
            }
        }

        /*
        So when the array is fully sorted in descending order,
        the value of done remains 1. Thus it will break the while loop.
        Otherwise, the sorting continues.
        */
    }

    /*
    After finishing the while loop, the array becomes
    array[]={6,5,4,3,2,1}

    So array[0]=6, array[1]=5, array[2]=4,..., array[5]=1

    */
    printf(“%d”, array[3]); /*It will give the output as 3*/
}

So the correct answer is 3.

Answer 4

3 is the answer.

I just ran the code here:

http://ideone.com/cp2VkX