C 2d array not correctly identifying if array is sorted or not

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »

55 Replies - 2007 Views - Last Post: 26 June 2013 - 04:11 PM Rate Topic: -----

#1 Jite25  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 82
  • Joined: 24-February 13

C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 12:12 AM

I'm working on part of a program that that first determines if a group of "tests" (arrays with elements that I define) and if they are not sorted already, it sorts them. However, it is not correctly identifying the sorted or non-sorted arrays.0 is not sorted, 1 is sorted. This is a 3 X 5 array or matrix. If the results of "is it sorted?" is different from expected, it returns a FAILED error, along with the # of the failed test in tests. It's supposed to sort in this order: 1,2,3,4,5 etc.

TESTS


int tests_inputs[NB_TESTS][NB_ROWS][NB_COLS] = {

/*  Test #0 - this is an already sorted matrix to ensure that our function*/
/*            does not mess up a sorted matrix by trying to "sort it again"*/
    { {1 , 2 , 3 , 4 ,  5} ,
      {6 , 7 , 8 , 9 , 10} ,
      {11, 12, 13, 14, 15} } ,

/*  Test #1 - this is a matrix with two elements only being not in order. */
/*            both are located inside the same row*/
    { {1 , 2 , 5 , 4 ,  3} ,
      {6 , 7 , 8 , 9 , 10} ,
      {11, 12, 13, 14, 15} },

// test #2 test for negative numbers

    { {1 , -2 , 3 , 4 ,  5} ,
      {6 , 7 , -8 , 9 , 10} ,
      {11, 12, 13, 14, -15} } ,

// test #3  test last 2 elements

    { {1 , 2 , 3 , 4 ,  5} ,
      {6 , 7 , 8 , 9 , 10} ,
      {11, 12, 13, 15, 14} } ,

// test #4 test middle elements

    { {1 , 2 , 3 , 4 ,  5} ,
      {6 , 8 , 9 , 7 , 10} ,
      {11, 12, 13, 14, 15} } ,

//test #5 matrix is backwards

    { {15 , 14 , 13 , 12 , 11} ,
      {10 , 9 , 8 , 7 , 6} ,
      {5, 4, 3, 2, 1} } ,

// test #6 check first 2

    { {2 , 1 , 3 , 4 ,  5} ,
      {6 , 7 , 8 , 9 , 10} ,
      {11, 12, 13, 14, 15} } ,

// test #7 1st row duplicates

    { {1 , 2 , 3 , 3 ,  5} ,
      {6 , 7 , 8 , 9 , 10} ,
      {11, 12, 13, 14, 15} } ,

// test #8 2nd row duplicates

    { {1 , 2 , 3 , 4 ,  5} ,
      {6 , 7 , 9 , 9 , 10} ,
      {11, 12, 13, 14, 15} } ,

// test #9 3rd row duplicates

    { {1 , 2 , 3 , 4 ,  5} ,
      {6 , 7 , 8 , 9 , 10} ,
      {11, 12, 12, 14, 15} } ,

// test #10 all same positive number

    { {5 , 5 , 5 , 5 ,  5} ,
      {5 , 5 , 5 , 5 ,  5} ,
      {5 , 5 , 5 , 5 ,  5} } ,

// test #11 all same negative number

    { {-5 , -5 , -5 , -5 ,  -5} ,
      {-5 , -5 , -5 , -5 ,  -5} ,
      {-5 , -5 , -5 , -5 ,  -5} } ,

// test #12 all zeroes

    { {0 , 0 , 0 , 0 , 0} ,
      {0 , 0 , 0 , 0 , 0} ,
      {0 , 0 , 0 , 0 , 0} } ,

// test #13 leading zero

    { {0 , 1 , 2 , 3 ,4} ,
      {5 , 6 , 7 , 8, 9} ,
      {10, 11, 12, 13,14} },

// test #14 leading negative numbers

    { {-1 , -2 , -3 , 4 , 5} ,
      {6 , 7 , 8 , 9 , 10} ,
      {11, 12, 13, 14, 15} },

// test #15 1st row duplicates not in order

    { {3 , 2 , 1 , 3 , 5} ,
      {6 , 7 , 8 , 9 , 10} ,
      {11, 12, 13, 14, 15} } ,

// test #16 2nd row duplicates not in order

    { {1 , 2 , 3 , 4 , 5} ,
      {6 , 9 , 7 , 9 , 10} ,
      {11, 12, 13, 14, 15} } ,

// test #17 3rd row duplicates not in order

    { {1 , 2 , 3 , 4 , 5} ,
      {6 , 7 , 8 , 9 , 10} ,
      {11, 12, 13, 14, 12} } ,

// test #18 matrix is all negative numbers, backwards order

   { {-1 , -2 , -3 , -4 , -5} ,
      {-6 , -7 , -8 , -9 , -10} ,
      {-11, -12, -13, -14, -15} }
};




EXPECTED


int tests_expected[NB_TESTS] = {
    1,                     /* #0 first test is a sorted matrix*/
    0,                     /* #1  second is not */
    0,                     // #2 negative numbers are after postives (out of order)
    0,                     // #3 last 2 elements are out of order
    0,                     // #4 3 middle elements are out of order
    0,                     // #5 matrix is in backwards order
    0,                     // #6 1st 2 elements are out of order
    1,                     // #7 duplicates are in order in 1st row
    1,                     // #8 duplicates are in order in 2nd row
    1,                     // #9 duplicates are in order in 3rd row
    1,                     // #10 entire matrix is a single duplicate positive number that is in order
    1,                     // #11 entire matrix is a single duplicate negative number that is in order
    1,                     // #12 entire matrix is filled with zeroes that are in order
    1,                     // #13 leading zero in order
    1,                     // #14 matrix starts with negative numbers and the entire matrix is in order starting from negative
    0,                     // #15 duplicates are in not in order in 1st row
    0,                     // #16 duplicates are in not in order in 2nd row
    0,                     // #17 duplicates are in not in order in 3rd row
    0                      // #18 matrix is all negative numbers, backwards order
};




Testing algorithm

int isMatrixSorted( int data[NB_ROWS][NB_COLS] ){
    /* 
       PARAMETERS   data the two dimensional matrix to be sorted
    */

     for(int i = 0; i < NB_ROWS -1 ; i++){
              for(int j =0 ; j < NB_COLS -1; j++){
        if (data[i][j] > data[i + 1][j])
        return 0;

    }
    }
 return 1;

}






failed tests

#1
#3
#4
#6
#15
#16
#17

This post has been edited by Jite25: 24 June 2013 - 12:14 AM


Is This A Good Question/Topic? 0
  • +

Replies To: C 2d array not correctly identifying if array is sorted or not

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3652
  • View blog
  • Posts: 11,421
  • Joined: 05-May 12

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 12:19 AM

If you consider that accessing a two dimensional array as indexing the row with the first index and the column with the second index (eg. array[row][column]) Then what does tell you about your isMatrixSorted() function?
Was This Post Helpful? 1
  • +
  • -

#3 Jite25  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 82
  • Joined: 24-February 13

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 12:34 AM

View PostSkydiver, on 24 June 2013 - 12:19 AM, said:

If you consider that accessing a two dimensional array as indexing the row with the first index and the column with the second index (eg. array[row][column]) Then what does tell you about your isMatrixSorted() function?



Not sure what you mean.
Was This Post Helpful? 0
  • +
  • -

#4 Jite25  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 82
  • Joined: 24-February 13

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 01:28 AM

Made some changes and now the function looks like this:


int isMatrixSorted( int data[NB_ROWS][NB_COLS], int rowsize, int colsize ){
    /* 
       RETURNS      0 if the matrix data is not sorted
                    1 if it is
       PARAMETERS   data the two dimensional matrix to be sorted
    */

rowsize = 3;
colsize = 5;

    for(int i = 0; i <= rowsize; i++){
        for(int j =0 ; j <= colsize; j++){
            if (data[i][j] > data[i][j + 1]){
                return 0;
            }//end if
        }// end inner for
    }// end outer for
 return 1;

}




failed tests now

#0,7-14
Was This Post Helpful? 0
  • +
  • -

#5 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3652
  • View blog
  • Posts: 11,421
  • Joined: 05-May 12

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 04:58 AM

You are overrunning your 2 dimensional array. When i == 3 (see line 11) then you have gone beyond the number of rows since arrays is C start at 0, and so you should only go from array[0][col] to array[2][col]. The same type of issue happens when j == 5 (see lne 12).
Was This Post Helpful? 1
  • +
  • -

#6 Jite25  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 82
  • Joined: 24-February 13

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 11:15 AM

current code for function


rowsize = 3;
colsize = 5;

    for(int i = 0; i < rowsize; i++){
        for(int j =0 ; j < colsize; j++){
            if (data[i][j] > data[i][j + 1]){
                return 0;
            }//end if
        }// end inner for
    }// end outer for
 return 1;





failed tests
#0,#7-9,#13-14


The failed tests are basically where the matrix is already sorted, where there are duplicates

This post has been edited by Jite25: 24 June 2013 - 11:33 AM

Was This Post Helpful? 0
  • +
  • -

#7 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1102
  • View blog
  • Posts: 4,597
  • Joined: 09-June 09

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 11:21 AM

What happens when j is equal to colsize - 1 in this condition?

 if (data[i][j] > data[i][j + 1]){ 



Hint: The max column index for the 2D array is colsize - 1

This post has been edited by jjl: 24 June 2013 - 11:21 AM

Was This Post Helpful? 1
  • +
  • -

#8 Jite25  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 82
  • Joined: 24-February 13

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 11:36 AM

View Postjjl, on 24 June 2013 - 11:21 AM, said:

What happens when j is equal to colsize - 1 in this condition?

 if (data[i][j] > data[i][j + 1]){ 



Hint: The max column index for the 2D array is colsize - 1


Is this a spillover error? Where I compare element 5 (#0-4) and element 6 where 5 is the max?
Was This Post Helpful? 0
  • +
  • -

#9 Jite25  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 82
  • Joined: 24-February 13

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 12:14 PM

I have a selection sort function that is giving crazy values for the sorted array, like 1,23334434,54453434, etc instead of 1,2,3.



int tmp = 0;

for(int i = 0; i < NB_ROWS - 1; i++){
    int min = i;
    for(int j = i +1 ; j < NB_COLS -1; j++){
        if (data[min] > data[j]){
        min = j;}

        // swap
    tmp = data[min];
    data[min][j] = data[i][j];
    data[i][j] = tmp;


}
}





This post has been edited by Jite25: 24 June 2013 - 02:04 PM

Was This Post Helpful? 0
  • +
  • -

#10 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3652
  • View blog
  • Posts: 11,421
  • Joined: 05-May 12

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 07:14 PM

Yes, that was an overrun error.

As for your sort routine:
- You are obviously ignoring the warning that the compiler is giving you because line 10 should have been warning you about assigning mismatched types.
- On line 6, you are trying to compare entire rows at one time, this is typically not allowed (unless you took extra steps to support it).
Was This Post Helpful? 0
  • +
  • -

#11 Jite25  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 82
  • Joined: 24-February 13

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 07:21 PM

View PostSkydiver, on 24 June 2013 - 07:14 PM, said:

Yes, that was an overrun error.

As for your sort routine:
- You are obviously ignoring the warning that the compiler is giving you because line 10 should have been warning you about assigning mismatched types.
- On line 6, you are trying to compare entire rows at one time, this is typically not allowed (unless you took extra steps to support it).


thanks. My code now looks like this for the sort.



int tmp = 0;
int min =0;

for(int i = 0; i < NB_ROWS -1; i++){
    min = i;
    for(int j = 0 ; j < NB_COLS -1; j++){
        if (data[min][j] > data[i][j + 1]){
        min = j;} // end if


       // swap
    tmp = data[min][j];
    data[min][j] = data[i][j];
    data[i][j] = tmp;


                        }//end col for loop
                    } // end row for loop



Was This Post Helpful? 0
  • +
  • -

#12 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3652
  • View blog
  • Posts: 11,421
  • Joined: 05-May 12

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 07:24 PM

Is it sorting correctly for you now? (I suspect not because you do nothing to deal with data that needs to migrate between rows.)
Was This Post Helpful? 0
  • +
  • -

#13 Jite25  Icon User is offline

  • D.I.C Head

Reputation: -2
  • View blog
  • Posts: 82
  • Joined: 24-February 13

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 07:30 PM

View PostSkydiver, on 24 June 2013 - 07:24 PM, said:

Is it sorting correctly for you now? (I suspect not because you do nothing to deal with data that needs to migrate between rows.)


Right it just doesn't sort them at all. I'm trying to figure out if the problem is with the //swap section or if it's in the finding the min part.

if my unsorted was

1,2,5,4,3
6,7,8,9,10
11,12,13,14,15


it will return this as a "sort"

1,2,13, 2621192,3
6,7,8,9,10
11,12,5,14,15
Was This Post Helpful? 1
  • +
  • -

#14 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3652
  • View blog
  • Posts: 11,421
  • Joined: 05-May 12

Re: C 2d array not correctly identifying if array is sorted or not

Posted 24 June 2013 - 10:38 PM

Your sort code is mixing rows and columns. You picked min to be the row i on line 5, but then you check the columns and remember the column numbers on lines 7 and 8. Lines 12-14 will have j equal to NBCOLS-1, which didn't seem to be your intent.

I suggest taking time to simulate your code on paper instead of just throwing code up on the screen and hoping that it works.
Was This Post Helpful? 1
  • +
  • -

#15 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3652
  • View blog
  • Posts: 11,421
  • Joined: 05-May 12

Re: C 2d array not correctly identifying if array is sorted or not

Posted 25 June 2013 - 05:39 AM

Time to give you two major hints since it's obvious that you are struggling.
Hint #1: First write a function that can sort a 1 dimensional array correctly every time.
Hint #2: Arrays in C and C++ are guaranteed to store the elements in memory contiguously. (eg. an array { { 9, 45 }, { 40, 38 } } is stored in memory as { 9, 45, 40, 38 } )
Was This Post Helpful? 1
  • +
  • -

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »