The Gateway to Computer Science Excellence
+19 votes
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

in Algorithms by Veteran (52.1k points)
edited by | 1.5k views
0
Clarify..
+1
corrected..
+13

Similar concept asked in GATE_2015

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

Young tableau

2 Answers

+22 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$

by Boss (12.1k points)
edited by
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?

+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;
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[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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,168 answers
193,841 comments
94,047 users