edited by
5,663 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

edited by

2 Answers

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

Related questions

26 votes
26 votes
1 answer
4
Kathleen asked Oct 9, 2014
5,106 views
A complete, undirected, weighted graph $G$ is given on the vertex $\{0, 1,\dots, n -1\}$ for any fixed ‘n’. Draw the minimum spanning tree of $G$ ifthe weight of the ...