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



Clarify..
corrected..

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
edited by
(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;
@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 :)