The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
433 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 (67.5k points)
edited ago by | 433 views
Clarify..
corrected..

2 Answers

+6 votes
Best answer
  1. 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 $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 (7.5k points)
edited ago 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 (293 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 :)


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

28,946 questions
36,792 answers
91,068 comments
34,689 users