1.5k 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



edited | 1.5k views
0
Clarify..
+1
corrected..
+13

https://gateoverflow.in/8148/gate2015-2_31

Young tableau

1. The smallest element is at index $1$,$1$.
2. 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 $n\times n$ 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$

by Boss (12.1k points)
edited
0
nice explanation @Ahwan
0

Superb 🙌

@Ahwan

0

@Ahwan I ran this code on the following input

1 2 3 4

2 3 4 5

3 4 5 6

4 5 6 7

This DD array is partially sorted according to the definition given in the problem.

I tried to insert x=3 , which is lesser than items in the last row and column . I ran the code on this input and got the following output.

2 3 3 4

2 3 4 5

3 4 5 6

4 5 6 7

but this is not partially sorted , can you help me here?

(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;
by (291 points)
+1
@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.
0
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?
+1
@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
+1
yes, you are correct :)
0
Arjun Sir

For the first question, if input array A is:

1 2 4 7

3 5 6 10

8 9 11 14

12 13 15 0

This array also obeys the basic condition A[i][j] <A[i+1][j] and A[i][j]<A[i][j+1] , for all i,j€[1,2,3]. But A may contain the minimum value. So how we can confirm that A will contain the minimum value.