search
Log In
4 votes
323 views

The next two questions refer to the following program.

In the code below reverse$(A,i,j)$ takes an array $A,$ indices $i$ and $j$ with $i\leq j,$ and reverses the segment $A[i],A[i+1],\cdots,A[j].$ For instance if $A=[0,1,2,3,4,5,6,7]$ then, after we apply reverse$(A,3,6),$ the contents of the array will be $A=[0,1,2,6,5,4,3,7].$

function mystery (A[0...99]) {
  int i, j, m;
  for (i = 0; i < 100; i++) {
    m = i;
  for (j = i; j < 100; j++) {
    if (A[j] > A[m]) {
        m = j;
       }
     }
     reverse(A,i,m);
   }
   return;
 }

When the procedure terminates, the array A has been:

  1. Sorted in descending order
  2. Sorted in ascending order
  3. Reversed
  4. Left unaltered
in Programming
recategorized by
323 views
0
Where are the next two questions??

2 Answers

0 votes

 

Just take a simple example as : - arr : 3 5 1 2 4 6 

 For outer loop when i=0,m=0 and now internal loop execute from j=i to length of arr and check for each element greatest element in the array form j=i to length of array, and save its index in the variable m. Now reverse(A,0,m) will just reverse the array from the index i to m so the greatest element will now become the first element and 

So on :

 

Pic1 

 

Caption

 

0 votes

Here we are given 100 elements in the array with indices 0 to 99 

In the outer loop ,we will take the first element position as m=0;, then inner loop simply checks one by one which is largest and saves its position as m . and apply reverse from i to m i.e from 0 to m ,which will bring the largest element in the first position and the remaining array elements will be in random order.

Now we will apply the  2nd iteration from i=1 ,put m=1; and repeat the above step which will bring the largest element from remaining array to i=1 position ,hence it is just like sorted the array in descending order

Related questions

1 vote
2 answers
1
168 views
The next two questions refer to the following program. In the code below reverse$(A,i,j)$ takes an array $A,$ indices $i$ and $j$ with $i\leq j,$ and reverses the segment $A[i],A[i+1],\cdots,A[j].$ For instance if $A=[0,1,2,3,4,5,6,7]$ ... ; } return; } The number of times the test $A[ j ] > A[ m ]$ is executed is: $4950$ $5050$ $10000$ Depends on the contents of $A$
asked Sep 13, 2019 in Programming gatecse 168 views
1 vote
1 answer
2
274 views
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$ The language $L_{1}\cup L_{2}$ is: regular, but not context-free context-free, but not regular both regular and context-free neither regular nor context-free
asked Sep 13, 2019 in Theory of Computation gatecse 274 views
1 vote
1 answer
3
218 views
Let $A$ be an $NFA$ with $n$ states. Which of the following is necessarily true? The shortest word in $L(A)$ has length at most $n-1.$ The shortest word in $L(A)$ has length at least $n.$ The shortest word not in $L(A)$ has length at most $n-1.$ The shortest word not in $L(A)$ has length at least $n.$
asked Sep 13, 2019 in Theory of Computation gatecse 218 views
5 votes
3 answers
4
360 views
Suppose that the figure to the right is a binary search tree. The letters indicate the names of the nodes, not the values that are stored. What is the predecessor node, in terms of value, of the root node $A?$ $D$ $H$ $I$ $M$
asked Sep 13, 2019 in DS gatecse 360 views
...