Thread: sorting the matrix question..

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    sorting the matrix question..

    how to sort the matrix so the sums of the rows
    will go from the biggest sum on the bottom
    to the smallest on top

    like in this example:

    http://img101.imageshack.us/img101/4580/79171873gv6.gif
    Last edited by transgalactic2; 12-20-2008 at 11:06 PM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Just like you would sort anything else. You can use bubblesort, quicksort, insertion sort, ..., ..., ..., ..., ....

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    in pseudo code
    Code:
    for each column  {
    for i = 0; i < Num of rows - 1; i++)  {
       for j = i + 1; j < Num of rows; j++) {
          if(Array[column][i] > Array[column][j]
             swap Array[i][column] with Array[j][column] 
             //using a temp value as a holder
    
          } 
       }
    }
    This is a selection sort, and is not meant as actual code to paste into a program. You'll need to flesh it out
    with real, not pseudo code, but it's pretty much there.
    Last edited by Adak; 12-20-2008 at 05:34 PM.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Adak View Post
    in pseudo code
    Code:
    for each column  {
    for i = 0; i < Num of rows - 1; i++)  {
       for j = i + 1; j < Num of rows; j++) {
          if(Array[column][i] > Array[column][j]
             swap Array[i][column] with Array[j][column] 
             //using a temp value as a holder
    
          } 
       }
    }
    This is a selection sort, and is not meant as actual code to paste into a program. You'll need to flesh it out
    with real, not pseudo code, but it's pretty much there.
    Did you intentionally transpose column/(j,i) around between the comparison and the swap?

    And the original post asks for the "sum of the row" to be sorted- which means that there is a need to first of all calculate the sum of the rows.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I just glanced at his jpg and thought he was trying to do a column sort.

    My intent was that he notice that since it's a square matrix, you could swap column and row, but I'm not sure that will fly, here.

    The craft of writing good pseudo code eludes me. generally. It's either too general, so the specifics are not to be relied on, or it's too specific, and then it is code. The latter is usually quite close, the former is never quite right, and I frequently find it a happy spot in the trash bin.

  6. #6
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i need to do row sort
    and the matrix doesnt have to be square

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Consider each row as it's own string:

    Code:
    for each row
    
       sort each cell in that row
    
    which might look like:
    
    for(r = 0; r < MaxRows; r++)  {
       for(i = 0; i < MaxCols - 1; i++)  {
          for(j = i + 1; j < MaxCols; j++)  {
             if(A[r][i] > A[r][j]  {
                temp = A[r][i];
                A[r][i] = A[r][j];
                A[r][j] = temp;
             }
          }
       }
    }
    The red code handles the rows, the blue part is the standard selection sort for a single dimension array.

    Edit:
    Your picture you linked to in your original post, does not show an array that is row sorted. It shows an array that has been sorted according to the sum of it's rows. That is not what the code above, will do. The above code will move all the lower numbers for each row, to the left position in that row, in ascending order.

    To do a row-sum sort, you will compare only each row's sum, and when they are out of order, with another row, you'll swap the two rows - including all the column values, all the way across the rows.

    For each row: compute a sum. Put the value in a small sum[] array, of one dimension.
    Now you can do your sorting. The slick way to do this is to use an index, and then you show the sorted array by printing it up in the order of the index.

    I am not going to show that, because it's above your coding experience, just yet. For now, just know that there is a sort through an index, that involves making no actual swaps in the array at all, but will show the array *as if* it was sorted, in perfect order.

    Code:
    for(i = 0; i < MaxElementsofSum[] - 1; i++)  {
       for(j = i + 1; j < MaxElementsofSum[]; j++)  {
          if(Sum[i] > Sum[j])   {
             temp = Sum[i];
             Sum[i] = Sum[j];
             Sum[j] = temp;
     
             //now swap the rows elements, from row j to row i
             for(k = 0; k < MaxColumnsofMatrix[]; k++)   {
                temp = Matrix[i][k];
                Matrix[i][k] = Matrix[j][k];
                Matrix[j][k] = temp;
             }
          }
       }
    }
    I haven't run this code, but it looks OK. Isn't that style of indentation (K&R), easy to read? I liiiiiike it!
    Last edited by Adak; 12-21-2008 at 04:58 AM.

  8. #8
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i created an array rows_sum which collects the sums of each row

    what to do now

    Code:
    #include <stdio.h>
    int main(){//star
    	int rows,cols,jndex,input;
    	int sum2=0;
    	printf("enter rows and cols [1..50] ==> ");
    	scanf("%d %d",&rows,&cols);
    	int matrix[rows][cols];
    	int sum[rows][cols];
    	int temp[rows][cols];
    	int transpose [cols][rows];
    	int index,kndex,tndex,gndex,lndex;
       int rows_sum[rows];
    	printf("enter power:");
    	scanf("%d",&input);
    	for (index = 0; index < rows; index++)
    	{
    	    rows_sum[index]=0;
    		for (kndex = 0; kndex < cols; kndex++)
    		{
    			matrix[index][kndex] = 0;
    			sum[index][kndex] = 0;
    			temp[index][kndex] = 0;
    			transpose[index][kndex] = 0;
    		}//end inner for
    	}//end outer for
    	printf("enter numbers in a row for a matrix:"); //stat input
    	for (index = rows - 1;index >= 0; index--)
    	{
    		for (kndex = cols - 1; kndex >= 0; kndex--)
    		{
    			scanf("%d", &matrix[index][kndex]);
    			transpose[kndex][index] = matrix[index][kndex];
    		}
    	}
    	getchar();  //needed because of scanf()
    	//end input
    	//start power operation
    	//  rows sum
    	for (index = 0; index < rows; index++)
    	{
    		for (kndex = 0; kndex < cols; kndex++)
    			rows_sum[index]=rows_sum[index]+matrix[index][kndex];
    		printf("\n");
    	}
          //  end rows sum
    	//start print
    	for (index = 0; index < rows; index++)
    	{
    		for (kndex = 0; kndex < cols; kndex++)
    			printf("%d ", sum[index][kndex]);
    		printf("\n");
    	}
    
    	//end print
    	printf("\n");
    	return 0;
    }//end main func

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    When you want to sort the rows, according to their sums, just copy and paste my code into your program, and check that the Matrix() and the Sums[] arrays in your program, and in my block of code, have the same names.

    My block of code, should not go inside any loops in your program, of course. Then check that the variables I used: i, j, temp, etc., are declared in your program.

    When you want to then print out your matrix, just print it out the normal way, don't use the row_sums array to print out the sorted matrix - no need for that. The whole matrix is already in row-sum order.
    Last edited by Adak; 12-21-2008 at 03:01 PM.

  10. #10
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    I know that "sum[i]" is the sum of row "i"
    what is purpose of this array MaxElementsofSum[] ??

    and why you dont put any value in it when you construct a loop with it
    Code:
    for(i = 0; i < MaxElementsofSum[] - 1; i++)  {        //there is no value inside the cols
       for(j = i + 1; j < MaxElementsofSum[]; j++)  {    //what is the purpose of MaxElementsofSum
          if(Sum[i] > Sum[j])   {
             temp = Sum[i];
             Sum[i] = Sum[j];
             Sum[j] = temp;
     
             //now swap the rows elements, from row j to row i
             for(k = 0; k < MaxColumnsofMatrix[]; k++)   {
                temp = Matrix[i][k];
                Matrix[i][k] = Matrix[j][k];
                Matrix[j][k] = temp;
             }
          }
       }
    }
    Last edited by transgalactic2; 12-21-2008 at 03:23 PM.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is the index sort I referred to earlier. It doesn't sort the matrix at all, but sorts a small index, instead.

    That index array can be used to print out the matrix, just like it was sorted.

    Say that you have an array of three friends ages, and a corresponding array of their names:

    Code:
    int ages[3] = { 30, 20, 40 };
    char names[3][25] = { 
    { "Adam" },
    {"Kevin"  },
    {"Zoi" } };
    So Adam is 30, Kevin is 20, and Zoi is 40. Now we want to print out our friends, sorted by age, but not mess with changing the original age[] or names[] arrays.

    First we need an index array, initialized in sorted order:
    Code:
    int index[3];
    
    //initialize it
    for(i = 0; i < sizeOfIndex; i++)
       index[i] = i;
    
    //Now we sort, using that index:
    for(i = 0; i < sizeOfIndex - 1; i++)  {
    
       for(j = i + 1; j < sizeOfIndex; j++)  {
    
          if(age[index[i]] > age[index[j]]  { //I'm comparing ages, through the index array
             temp = index[i];
             index[i] = index[j];             //only the index contents are swapped
             index[j] = temp;
          }
       }
    }
    
    //now print out the data, in sorted order, by going through the index array.
    putchar('\n');
    for(i = 0; i < sizeOfIndex; i++)
       printf( " Age: %d  Name: %s \n", age[index[i]], names[index[i]] );
    
    //showing:
    
    Age: 20  Name: Kevin
    Age: 30  Name: Adam
    Age: 40  Name: Zoi
    
    /*
    Original arrays still are in their original order:
    
    30 Adam
    20 Kevin
    40 Zoi
    
    */
    Last edited by Adak; 12-21-2008 at 03:38 PM.

  12. #12
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    Quote Originally Posted by Adak View Post
    When you want to sort the rows, according to their sums, just copy and paste my code into your program, and check that the Matrix() and the Sums[] arrays in your program, and in my block of code, have the same names.

    My block of code, should not go inside any loops in your program, of course. Then check that the variables I used: i, j, temp, etc., are declared in your program.

    When you want to then print out your matrix, just print it out the normal way, don't use the row_sums array to print out the sorted matrix - no need for that. The whole matrix is already in row-sum order.
    apparently i tried to understand the wrong code
    what code you meant?

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by transgalactic2 View Post
    apparently i tried to understand the wrong code
    what code you meant?
    This code:
    Code:
    for(i = 0; i < MaxElementsofSum[] - 1; i++)  {       
       for(j = i + 1; j < MaxElementsofSum[]; j++)  {   
          if(Sum[i] > Sum[j])   {
             temp = Sum[i];
             Sum[i] = Sum[j];
             Sum[j] = temp;
     
             //now swap the rows elements, from row j to row i
             for(k = 0; k < MaxColumnsofMatrix[]; k++)   {
                temp = Matrix[i][k];
                Matrix[i][k] = Matrix[j][k];
                Matrix[j][k] = temp;
             }
          }
       }
    }
    MaxElementsOfSum[] is the number of elements in the Sum[] array, which hold a sum in them. In your example
    with a 4 X 4 matrix, you would have 4 elements in Sum[].

  14. #14
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i tried to implement that
    sum is an array which holds the sum of each row
    i switched MaxColumnsofMatrix[] by "rows" (because rows is the number cells in the sum array)
    but i get many error of this type

    ex2.c(62) : error C2109: subscript requires array or pointer type
    Code:
    #include <stdio.h>
    int main(){//star
    	int rows,cols,jndex,input;
    	int sum2=0;
    	printf("enter rows and cols [1..50] ==> ");
    	scanf("%d %d",&rows,&cols);
    	int matrix[rows][cols];
    	int sum[rows][cols];
    	int temp[rows][cols];
    	int transpose [cols][rows];
    	int index,kndex,tndex,gndex,lndex;
       int rows_sum[rows];
    	printf("enter power:");
    	scanf("%d",&input);
    	for (index = 0; index < rows; index++)
    	{
    	    rows_sum[index]=0;
    		for (kndex = 0; kndex < cols; kndex++)
    		{
    			matrix[index][kndex] = 0;
    			sum[index][kndex] = 0;
    			temp[index][kndex] = 0;
    			transpose[index][kndex] = 0;
    		}//end inner for
    	}//end outer for
    	printf("enter numbers in a row for a matrix:"); //stat input
    	for (index = rows - 1;index >= 0; index--)
    	{
    		for (kndex = cols - 1; kndex >= 0; kndex--)
    		{
    			scanf("%d", &matrix[index][kndex]);
    			transpose[kndex][index] = matrix[index][kndex];
    		}
    	}
    	getchar();  //needed because of scanf()
    	//end input
    	//start power operation
    	//  rows sum
    	for (index = 0; index < rows; index++)
    	{
    		for (kndex = 0; kndex < cols; kndex++)
    			rows_sum[index]=rows_sum[index]+matrix[index][kndex];
    		printf("\n");
    	}
          //  end rows sum
    	 
    int i,j,k,temp;
    for(i = 0; i <rows - 1; i++)  {       
       for(j = i + 1; j <rows; j++)  {   
          if(rows_sum[i] >rows_sum[j])   {
             temp = rows_sum[i];
             rows_sum[i] = rows_sum[j];
             rows_sum[j] = temp;
     
             //now swap the rows elements, from row j to row i
             for(k = 0; k <rows; k++)   {
                temp = matrix[i][k];
                matrix[i][k] = matrix[j][k];
                matrix[j][k] = temp;
             }
          }
       }
    }
    Last edited by transgalactic2; 12-22-2008 at 02:40 AM.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So far as I can tell, line 62 is the penultimate closing brace. If you're going to remove lines so that we can't count, you'll have to tell us what line line 62 actually is.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. power operation on a matrix question..
    By transgalactic2 in forum C Programming
    Replies: 6
    Last Post: 12-19-2008, 11:11 AM
  2. Music Programming - Serial Matrix Display
    By CrazyHorse in forum C Programming
    Replies: 1
    Last Post: 11-12-2007, 04:16 PM
  3. Replies: 3
    Last Post: 04-29-2005, 02:03 AM
  4. Replies: 21
    Last Post: 04-25-2005, 07:18 PM
  5. an actual question (sorting arrays)
    By master5001 in forum C Programming
    Replies: 4
    Last Post: 08-13-2001, 10:21 PM