Sorting Two lists

[biebo]

I have a matrix, represented by rows and columns, this is a matrix Market format

Below is an example . Its a 5 x 5 matrix, here there size of list is 11

5 5 11 <-- header
1 1 1 <-- list starts
2 2 10.5
3 3 0.01499999999999999944
1 4 6
4 2 250.5
4 4 -280
4 5 33.32000000000000028
5 5 12
4 1 6
2 4 250.5
5 4 33.32000000000000028


My problem is simple, I want it to be sorted row wise.

like :

1 1 1
1 4 6
2 2 10.5
2 4 250.5
3 3 0.01499999999999999944
4 1 6
4 2 250.5
4 4 -280
4 5 33.32000000000000028
5 4 33.32000000000000028
5 5 12

I have made a program, but its buggy

Can any body help me with this , Any good algorithm ?


------
-----
My program

---

/*
* Matrix Market I/O example program
*
* Read a real (non-complex) sparse matrix from a Matrix Market (v. 2.0) file.
* and copies it to stdout. This porgram does nothing useful, but
* illustrates common usage of the Matrix Matrix I/O routines.
* (See http://math.nist.gov/MatrixMarket for details.)
*
* Usage: a.out [filename] > output
*
*
* NOTES:
*
* 1) Matrix Market files are always 1-based, i.e. the index of the first
* element of a matrix is (1,1), not (0,0) as in C. ADJUST THESE
* OFFSETS ACCORDINGLY offsets accordingly when reading and writing
* to files.
*
* 2) ANSI C requires one to use the "l" format modifier when reading
* double precision floating point numbers in scanf() and
* its variants. For example, use "%lf", "%lg", or "%le"
* when reading doubles, otherwise errors will occur.
*/

#include <stdio.h>
#include <stdlib.h>
#include "./mmio.h"
#include "./mmio.c"

//void converMM(double *I,double *J, int N, int nz, double *val);

int main(int argc, char *argv[])
{
int ret_code;
MM_typecode matcode;
FILE *f;
int M, N, nz;
int *I, *J;
long i;
double *val;

if (argc < 2)
{
fprintf(stderr, "Usage: %s [martix-market-filename] [martix-market-New-filename] \n", argv[0]);
exit(1);
}
else
{
if ((f = fopen(argv[1], "r")) == NULL)
exit(1);
}

if (mm_read_banner(f, &matcode) != 0)
{
printf("Could not process Matrix Market banner.\n");
exit(1);
}


/* This is how one can screen matrix types if their application */
/* only supports a subset of the Matrix Market data types. */

if (mm_is_complex(matcode) && mm_is_matrix(matcode) &&
mm_is_sparse(matcode) )
{
printf("Sorry, this application does not support ");
printf("Market Market type: [%s]\n", mm_typecode_to_str(matcode));
exit(1);
}

/* find out size of sparse matrix .... */

if ((ret_code = mm_read_mtx_crd_size(f, &M, &N, &nz)) !=0)
exit(1);

// we are adding the redundant values i.e upper or lower diagonal
// which ever is missing in the .mtx file, in order to make it easy
// for our application to use that file, which has all entries of a
// symmetric sparse matrix.

/* reseve memory for matrices */
long tolSize = 2*nz - N;
printf("tolsize = %d nz = %d \n",tolSize,nz);
I = (int *) malloc(tolSize * sizeof(int));
J = (int *) malloc(tolSize * sizeof(int));
val = (double *) malloc(tolSize * sizeof(double));


/* NOTE: when reading in doubles, ANSI C requires the use of the "l" */
/* specifier as in "%lg", "%lf", "%le", otherwise errors will occur */
/* (ANSI C X3.159-1989, Sec. 4.9.6.2, p. 136 lines 13-15) */
printf("Reading from file %s\n",argv[1]);
int count = 0;
for (i=0; i<nz; i++)
{
fscanf(f, "%d %d %lg\n", &I[i], &J[i], &val[i]);
I[i]--; /* adjust from 1-based to 0-based */
J[i]--;

if(I[i] != J[i]){
I[count+nz] = J[i];
J[count+nz] = I[i];
val[count+nz] = val[i];
count++;
}else{
printf(" %d %d = %lg \n", I[i], J[i], val[i]);
}
}

printf("Before .");
for (i=0; i<tolSize; i++)
printf("%d %d %20.19g\n", I[i]+1, J[i]+1, val[i]);


if (f !=stdin)
fclose(f);


printf("Reading DONE\n",argv[1]);
printf("Sorting row wise\n");
//Sort column wise
long j;
double temp;
for(i=0;i<tolSize;i++){
// if(i % 10000 == 0)
// printf("i = %d\n",i);
for(j=tolSize;j>i;j--){

if(I[j-1] > I[j]){
//swap
temp = J[j-1];
J[j-1] = J[j];
J[j] = temp;

temp = I[j-1];
I[j-1] = I[j];
I[j] = temp;

temp = val[j-1];
val[j-1] = val[j];
val[j] = temp;

}
}
}




printf("Sorting colmn wise\n");
// Sort row coln, but row is still the first preference.
count = 0;
int row = 0;
int range = 0;
int ii;
for(ii = 0; ii< tolSize;ii++){

if(ii == tolSize - 1){
row++;
}

if(row == I[ii] ){ //&& col !=(N-1)
count++;
}else{

// Sort on row..

if(row == N){
count++;
row--;
}
// printf("row = %d count = %d \n",row,count);
for(i=0;i<count;i++){
for(j=0;j<i;j++){
if(J[range+i] < J[range+j]){


temp = J[range+i];
J[range+i] = J[range+j];
J[range+j] = temp;

temp = I[range+i];
I[range+i] = I[range+j];
I[range+j] = temp;

temp = val[range+i];
val[range+i] = val[range+j];
val[range+j] = temp;

}
}
}
range += count;
count = 1;
row++;
}// Sorting ends




}

printf("After \n");
printf(" %d %d %lg\n", I[0], J[0], val[0]);
printf(" %d %d %lg\n", I[1], J[1], val[1]);


printf("Writing to file %s \n",argv[2]);
/************************/
/* now write out matrix */
/************************/

if ((f = fopen(argv[2], "w")) == NULL)
exit(1);

// mm_write_banner(f, matcode);
mm_write_mtx_crd_size(f, M, N, tolSize);

for (i=0; i<tolSize; i++)
fprintf(f, "%d %d %20.19g\n", I[i]+1, J[i]+1, val[i]);
// printf("%d %d %20.19g\n", I[i]+1, J[i]+1, val[i]);



fclose(f);


printf("DONE\n");

free(I);
free(J);
free(val);

return 0;
}

[nuzzle]

Can any body help me with this , Any good algorithm ?

You can use an existing sorting algorithm.

Sort a vector of row indexes (alternatively pointers to rows). Then afterwards you reorganize the matrix according to the sorted row order.

To decide whether two row indexes are to be swaped you don't compare the indexes themselves but the corresponding rows.

[mellice]

You can use Young Tableau
http://en.wikipedia.org/wiki/Young_tableau

I think this will solve your problem, also if you need the code that will sort the young tableau you can google "sort Young Tableau" and a lot of implementations will show up

regards