GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
356 views

A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n-1], A[i][j] < A[i][j+1] \text{ and } A[i][j] < A[i+1][j]$

Fill in the blanks:

  1. The smallest item in the array is at $A[i][j]$ where $i=__$ and $j=__.$

  2. The smallest item is deleted. Complete the following $O(n)$ procedure to insert item $x$ (which is guaranteed to be smaller than any item in the last row or column) still keeping $A$ partially sorted.
procedure insert (x: integer);
var i,j: integer;
begin
    i:=1; j:=1, A[i][j]:=x;
    while (x > __ or x > __) do
        if A[i+1][j] < A[i][j] ___ then begin
            A[i][j]:=A[i+1][j]; i:=i+1;
        end
        else begin
            _____
        end
    A[i][j]:= ____
end

 

asked in Algorithms by Veteran (64.6k points)   | 356 views
Clarify..
corrected..

2 Answers

+5 votes
Best answer
a) smallest element is at index 1,1.

b) So we have to give an array which is partially sorted. Definition of partially sorted is given in the question.
We will give the value of x which is less than last row & column value.
At last, 1,1 should be deleted & x should be at its correct place.

  i=1;j=1; a[i][j]=x;
  while ((x>a[i+1][j]) || (x>a[i][j+1]))
  {
        if((a[i+1][j] < x) && (a[i+1][j] <a[i][j+1]))
        {
          a[i][j]=a[i+1][j];
          i=i+1;
        }
    else
        {
          a[i][j]=a[i][j+1];
          j=j+1;
        }
  }
  a[i][j]=x;

 

Enter the dimension of nxn array. Give the value of n
3
Enter the array elements in partially sorted order
2 3 9
5 6 10
8 11 15

Enter the value of x
7

The final output.
3   6   9   
5   7   10   
8   11   15
answered by Boss (5.3k points)  
edited by
+7 votes
(a). i=1 and j=1 (smallest item in the array)

(b).here in while loop (x>A[i+1][j] or x>A[i][j+1])

     A[i][j]:=A[i+1][j]; i:=i+1;

else begin

     A[i][j]:=A[i][j+1]; j=j+1;

end

A[i][j]:=x;
answered by (283 points)  
@Arjun sir, @Bikram sir the solution is wrong.
The question also seems little bit wrong.
I implemented it.
  while (x>a[i+1][j] || x>a[i][j+1])
  {
        if(a[i+1][j] < a[i][j])
        {
          a[i][j]=a[i+1][j];
          i=i+1;
    }
    else
    {
       a[i][j]=a[i][j+1];
       j=j+1;
    }
  }

Output:

Enter the dimension of nxn array. Give the value of n
3
Enter the array elements in partially sorted order
2 3 9
5 6 10
8 11 15

Enter the value of x
7

The final output.
5   3   9   
6   7   10   
8   11   15  

So 5 is at 1,1   3 should be at 1,1. It is not partially sorted.
after first iteration, j is not incremented. So,

7 3 9
5 6 10
8 11 15
becomes
5 3 9
5 6 10
8 11 15.

In next iteration, 5 should be replaced by 3 rt?
@Arjun sir,  j is not incremented but i is incremented.

The order in which it is modified...
 
Enter the array elements in partially sorted order
2 3 9
5 6 10
8 11 15

Enter the value of x
7

5   3   9   
5   6   10   
8   11   15   

5   3   9   
6   6   10   
8   11   15   

The final output.
5   3   9   
6   7   10   
8   11   15
yes, you are correct :)


Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2064 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,647 answers
79,695 comments
31,069 users