in Algorithms edited by
5,628 views
35 votes
35 votes

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]$

  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

in Algorithms edited by
5.6k views

3 Comments

Clarify..
0
0
corrected..
1
1

Similar concept asked in GATE_2015

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

Young tableau

29
29

2 Answers

38 votes
38 votes
Best answer
  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$

edited by
by

4 Comments

@eyeamgj Let's take a matrix of 4x4. Either you're gonna travel towards right or bottom if we're starting from the (1,1). So maximum path will be, if you traversed all the way to the bottom row i.e. (1,1) – (2,1) – (3,1) – (4,1) and then you traversed across all the way to the end element (4,4). At max this will take O(n+n). Therefore O(n)
1
1
OK THANK YOU GOT…...
0
0

@Ahwan Sir,

Amazing explanation !

0
0
9 votes
9 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;

4 Comments

@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
1
yes, you are correct :)
1
1
Arjun Sir

For the first question, if input array A[4][4] 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[4][4] may contain the minimum value. So how we can confirm that A[1][1] will contain the minimum value.
0
0

Related questions