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

My answer was 4 in this ques. someone confirm??

---

answer is 3.. i was wrong. the trick was that u have to run that loop again which i had not done as when you are running that 2nd for loop , it will make done equals 0 and then that while loop will again run. i think whosoever have written this ques. answer as 4, most of them would have done this mistake. one more wrong. it was an easy ques., feeeling disappointed. :(

---

Code mentioned in the question is a variant of Bubble Sort.

---

int array[] = \{3, 5, 1, 4, 6, 2};

some one correct it.

---

very true @mohit

I also did the same mistake and so did the most of us, because as soon as we start doing loop execution through pen and paper we think that 'I got this question and it's so easy'. but we tend to forgot the little things (which are indeed converted into the huge blunder obviously) and lost good 1 or 2 marks just because of laziness :(

---

Someone correct the question ...

---

Notice that both the for-loops intend to arrange the array in descending order.

---

This was a really good question with a $\mathbf{SWEET}$ trap.

---

This Question is a variant of bubble sort technique.

The first for loop will displace lightest element to last place and second loop will place heaviest element in first place.

While continues till all  the elements are completely in descending order .😃

---

this ‘done’ must have made many students commit silly mistakes...

---

This question realises us that if you feel any question very easy in gate. Well, see once more because there is most probable chances you are missing something...

---

There are two variations of this question, in Made Easy’s PYQ book the second for loop is outside the while loop, but here both for loops are inside the while loop. Which one is the correct one? (both have the output = 3)

---

Madeasy was wrong if second loop is outside the while.loop is impossible to get the answer as 3

---

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