Vaishnavi
BAN USERYou can refer to this code. It uses heap data structure.
This code works fine except the first element printed will always be mat[0][0].
package practice;
import java.util.Scanner;
public class matrix_sorting_problem {
static int m=3,n=4;
static int[] a;
static int[][] mat;
public static void main(String args[]){
mat=new int[m][n];
Scanner s=new Scanner(System.in);
for(int i=0;i<m;i++){
System.out.println("enter values for col "+i );
for(int j=0;j<n;j++){
mat[i][j]=s.nextInt();
}
}
a=new int[m];
int c=0;
int cou=0;
for(int i=0;i<m;){
if(c<n){
a[i]=(mat[c][cou]*100)+(c*10)+cou;
//System.out.println("values of a"+ i+ " "+ a[i]);
c++;
i++;
}
else{
c=0;
cou++;
a[i]=(mat[c][cou]*100)+(c*10)+cou;
//System.out.println("values of a"+ i+ " "+ a[i]);
i++;
}
}
matrix_sorting_problem m=new matrix_sorting_problem();
for(int x=0;x<11;x++)
System.out.println(m.getmin());
}
void heapify(){
int temp=a[0];
int col=temp%10;
int row=(temp/10)%10;
//System.out.println(a[0]+" "+col+" "+row);
if((col+1)<n){
a[0]=(mat[row][col+1])*100+row*10+col+1;
//System.out.println(a[0]+" "+col+" "+row);
}else{
int flag=0;int i=0;
col=(a[i]%10)+1;
row=(a[i]/10)%10;
while(flag!=1){
//System.out.println(col+ " " +row);
//System.out.println("stuck here");
if(col<n){
a[0]=(mat[row][col])*100+row*10+col;
//System.out.println(a[0]);
flag=1;
}else{
i++;
}
if(i<m){
col=(a[i]%10)+1;
row=(a[i]/10)%10;}
else{
a[0]=999;
flag=1;
}
}
}
//a[0]=a[a.length-1];
int i=0;
/*for( i=0;i<m;i++){
System.out.print(" "+ a[i]);
}*/
i=0;
while(((2*i)+1<a.length)&&(((a[i]/100)>(a[2*i+2]/100))||((a[i]/100)>(a[2*i+1]/100)))){
//System.out.println("stuck here in while- value of i"+ i);
if(a[2*i+1]/100>a[2*i+2]/100){
// System.out.println("executing if");
int temp1=a[i];
a[i]=a[2*i+2];
a[2*i+2]=temp1;
i=2*i+2;
}else{
// System.out.println("executing else");
int temp1=a[i];
a[i]=a[2*i+1];
a[2*i+1]=temp1;
i=2*i+1;
}
}
}
int getmin(){
int temp= a[0];
//System.out.println(temp);
heapify();
return temp/100;
}
}
The below code is just for reference. It uses heap data structure.
This code works fine except the first element printed will always be mat[0][0].
- Vaishnavi March 18, 2015