Link to home
Start Free TrialLog in
Avatar of tetoo
tetoo

asked on

sorting array by row length

I have 2 dimentional arrays which initialized with 0 values in the begining and I call function to fill up this array with different numbers  from 1 to 80. keeping in mind that those zeros should be ignored.
so when I print the array I dont have those zeros appeared at all.
for( int  i=0; candidatepath[i][0]>0; i++)
      {
            for ( int j=0; candidatepath[i][j]>0; j++)
            {
                  cout<<candidatepath[i][j]<<"   ";
                  
            }
            cout<<endl;
      }

what I need to do is sorting this 2 dimensional array based in the row lenght from the shortest to longest rows. keeping in mind that if there are 2 rows have got the same length they should still keep the same order which they already have.
can you help me how this can be done.

thnxs
Avatar of josgood
josgood
Flag of United States of America image

Are you defining a longer row as having more non-zero numbers than a shorter row?
Avatar of tetoo
tetoo

ASKER

the array is 80 * 80 and its filled up with zeros to just reconize the numbers between 1 and 80 that going to be store in this array so for example I would have this result if I print out the array

9   36   6  
65   31   80   74   6  
41   28   80   6  
41   25   14   74   6  
9   28   6  
65   31   55   36   6  
41   25   14   36   6  
9   64   80   5   6  

by the way forgot to mintion something that could help that is the 1st array always in my array is the sgortes one always.
for(int  i=0; candidatepath[i][0]>0; i++)
	{
		for ( int j=0; candidatepath[i][j]>0; j++)
		{
			cout<<candidatepath[i][j]<<"   ";
			
		}
		cout<<endl;
	}

Open in new window

My key thoughts are:
1)  Have a structure Entry that records the length of a row.
2)  Have a vector of these structures
3)  Sort the vector
4)  Display in the order given by the vector

I wasn't clear on whether a row can have numbers after the first zero, so I assumed that it can.

Reference pages are:
          http://www.cppreference.com/cppvector/index.html
sort algorithm  http://www.cppreference.com/cppalgorithm/sort.html

Sample code for a small array
#include
#include  
#include
#include
#include

// Used to record length of each row in a vector
struct Entry { int row; int size; };

// Needed for sort algorithm
bool cmp(const Entry& a, const Entry& b ) { return a.size < b.size; }              

// Get length of a row
int RowLength(const int* abc, int cols) {
   int result = 0;
   while (cols--) if (*abc++ > 0) result++;
   return result;
}

int main(int argc, wchar_t *argv[]) {
   const int rows = 4, cols = 3;
   int abc[rows][cols];
   // fill the array
   abc[0][0] = 1; abc[0][1] = 1; abc[0][2] = 1;
   abc[1][0] = 2; abc[1][1] = 2; abc[1][2] = 0;
   abc[2][0] = 3; abc[2][1] = 3; abc[2][2] = 0;
   abc[3][0] = 4; abc[3][1] = 0; abc[3][2] = 0;
   // get length of each row
   std::vector sorting;
   for (int i = 0; i < rows; i++) {
      Entry anEntry; anEntry.row = i; anEntry.size = RowLength(abc[i], cols);
      sorting.push_back(anEntry);
   }
   // sort the array
   std::sort(sorting.begin(),sorting.end(), cmp);
   
   for (int i = 0; i < rows; i++) {
      int row = sorting[i].row;
      for (int j = 0; j < cols; j++) {
         if (abc[row][j] > 0) std::cout << abc[row][j] << " ";
      }
      std::cout << std::endl;
   }
   return 0;
}

>>>> std::sort(sorting.begin(),sorting.end(), cmp);
The std::sort isn't stable. It might sort rows with equal lengths so that they have a different order than before. Use std::stable_sort to fix that.

Regards, Alex

If you want to sort your original 2-dim array, you couldn't do it with STL stable_sort as (A) the 'rows' were plain C arrays where no operator= is defined. Also (B) the array of the rows has no iterator hence it isn't usable with std::stable_sort.

(A) could be solved by defining a struct which makes your 'rows' class objects:

struct Row
{
     int cells[MAX_COLS];
     int length() const
     {
           int len = MAX_COLS;
           while (len > 0 && cells[len-1] == 0) --len;
           return len;
     }
     bool operator <= (const Row& r)
     {
          return length() <= r.length();
     }
     Row & operator= (const Row& r)
     {
           memcpy(cells, r.cells, sizeof(cells));
     }
};

With the above you can *cast* your 2-dim array  to a 1-dim array of Row type if the size of a Row is exactly the same as the size of a 'row' in your array. You need to define the MAX_COLS same as the width of your table. In case MAX_COLS is an odd number you also may need to change the alignment to int size (compiler settings) so that a Row exactly overlays one of your rows.

(B) could be solved by using your own stable sort e. g. a mergesort like that

 void merge(Row array[], int low, int mid, int upp)
 {
      int left = low;
      int right = mid+1;
      int next = 0;
      int temparray = new int [upp-low+1];
      // merge arrays
      while (left <= mid && right <= upp)
      {
           if (array[left] <= array[right])
               temparray[++next] = array[left++];
           else
               temparray[++next] = array[right++];
      }
      // take the rest of left array (if somewhat left)
      for (;left <= mid; ++left)
            temparray[++next] = array[left];
      // take the rest of right array (if somewhat left)
      for (;right<= mid; right++)
            temparray[++next] = array[right];
      // copy temparray
      while (0 < next--)
           array[low + next] =  temparray[next];
 }

 void mergesort(Row array[], int low, int upp)
 {
        if (low == upp) return;
        int mid = (low + upp)/2;
        mergesort(array, low, mid );
        mergesort(array, mid+1, upp );
        merge(array, low, mid, upp);
 }


Your Main would look like

int main ()
{
     // define and fill candidatepath like you did it before
     ....

     // turn candidatepath to an array of Row objects
     Row * rowArray = (Row*)&candidatepath[0][0];
     
     // sort it
     mergesort(rowArr, 0, MAX_ROWS-1);

     // ok the candidatepath is now sorted

     return 0;
}
>>The std::sort isn't stable
Alex, could you point me to an URL that discusses this?

Thank you.

Joe
>>The std::sort isn't stable
Actually, it is compiler dependent. I assumed most implementations were using quicksort which isn't stable.

>>>> Alex, could you point me to an URL that discusses this?
I only found that on a quick search

http://en.literateprograms.org/Merge_sort_(C_Plus_Plus)

which not necessarily must be a reference. But the existance of std::stable_sort may be an indication that the standard doesn't require std::sort to be stable.

Regards, Alex
Alex,

I hadn't seen this before, but I think you're right.  From the MSDN (granting that this is a compiler dependency)

sort
Arranges the elements in a specified range into a nondescending order or according to an ordering criterion specified by a binary predicate.
http://msdn.microsoft.com/en-us/library/ecdecxh1(VS.80).aspx

stable_sort
Arranges the elements in a specified range into a nondescending order or according to an ordering criterion specified by a binary predicate and preserves the relative ordering of equivalent elements.
http://msdn.microsoft.com/en-us/library/z02ba27t(VS.80).aspx

"and preserves the relative ordering of equivalent elements" indicates that you're right -- stable_sort needs to be used in this answer.


Avatar of tetoo

ASKER

Dear
I have used that code in e. g. a mergesort (B stage ) and I got those errors can u help me  to sort them out I
although I have already decleared both functions  
void merge(Row array[], int low, int mid, int upp)  and
void mergesort(Row array[], int low, int upp) in my class  I still got those errors

srand80.cpp
srand80.cpp(73) : error C2061: syntax error : identifier 'Row'
srand80.cpp(74) : error C2061: syntax error : identifier 'Row'
srand80.cpp(2626) : error C2065: 'Row' : undeclared identifier
srand80.cpp(2626) : error C2146: syntax error : missing ')' before identifier 'a
rray'
srand80.cpp(2626) : error C2182: 'merge' : illegal use of type 'void'
srand80.cpp(2626) : error C2059: syntax error : ')'
srand80.cpp(2627) : error C2143: syntax error : missing ';' before '{'
srand80.cpp(2627) : error C2447: missing function header (old-style formal list?
)
srand80.cpp(2651) : error C2146: syntax error : missing ')' before identifier 'a
rray'
srand80.cpp(2651) : error C2182: 'mergesort' : illegal use of type 'void'
srand80.cpp(2651) : error C2059: syntax error : ')'
srand80.cpp(2652) : error C2143: syntax error : missing ';' before '{'
srand80.cpp(2652) : error C2447: missing function header (old-style formal list?
)
srand80.cpp(2734) : error C2065: 'rowArray' : undeclared identifier
srand80.cpp(2734) : error C2059: syntax error : ')'
srand80.cpp(2737) : error C2065: 'rowArr' : undeclared identifier
srand80.cpp(2737) : error C2065: 'MAX_ROWS' : undeclared identifier

Avatar of tetoo

ASKER

Dear itsmeandnobodyelse,
Dear
I have used that code in e. g. a mergesort (B stage ) and I got those errors can u help me  to sort them out I
although I have already decleared both functions  
void merge(Row array[], int low, int mid, int upp)  and
void mergesort(Row array[], int low, int upp) in my class  I still got those errors

srand80.cpp
srand80.cpp(73) : error C2061: syntax error : identifier 'Row'
srand80.cpp(74) : error C2061: syntax error : identifier 'Row'
srand80.cpp(2626) : error C2065: 'Row' : undeclared identifier
srand80.cpp(2626) : error C2146: syntax error : missing ')' before identifier 'a
rray'
srand80.cpp(2626) : error C2182: 'merge' : illegal use of type 'void'
srand80.cpp(2626) : error C2059: syntax error : ')'
srand80.cpp(2627) : error C2143: syntax error : missing ';' before '{'
srand80.cpp(2627) : error C2447: missing function header (old-style formal list?
)
srand80.cpp(2651) : error C2146: syntax error : missing ')' before identifier 'a
rray'
srand80.cpp(2651) : error C2182: 'mergesort' : illegal use of type 'void'
srand80.cpp(2651) : error C2059: syntax error : ')'
srand80.cpp(2652) : error C2143: syntax error : missing ';' before '{'
srand80.cpp(2652) : error C2447: missing function header (old-style formal list?
)
srand80.cpp(2734) : error C2065: 'rowArray' : undeclared identifier
srand80.cpp(2734) : error C2059: syntax error : ')'
srand80.cpp(2737) : error C2065: 'rowArr' : undeclared identifier
srand80.cpp(2737) : error C2065: 'MAX_ROWS' : undeclared identifier

thnx 4 ur assistance :)
>>srand80.cpp(73) : error C2061: syntax error : identifier 'Row'
define the Row structure before line 73

>>If you want to sort your original 2-dim array, you couldn't do it with STL stable_sort as (A) the 'rows' were plain C >>arrays where no operator= is defined. Also (B) the array of the rows has no iterator hence it isn't usable with >>std::stable_sort.
>>(A) could be solved by defining a struct which makes your 'rows' class objects:
It can also be solved as in my original answer, by creating a simple struct and using std::vector.  This avoids the need to write mergesort.  Alex's suggestion of std::stable_sort instead of my usage of std::sort is a good one.

Would you please post your code as you currently have it?  Either Alex or I (or many others here) can fix it.
Avatar of tetoo

ASKER

if I post the code prehaps you wont be able 2 run it coz you need a both network simulatior + VS6 the compiler that Im using to save the time hope if u can figer out where is the problem and help me ..
I got one class as you can see in the attached code snippet  and I defined the Row structure after this class and got those errors and help .... I pointed the number of lines which have errors on them .

the errors :
srand80.cpp
srand80.cpp(74) : error C2061: syntax error : identifier 'Row'
srand80.cpp(75) : error C2061: syntax error : identifier 'Row'
srand80.cpp(2652) : error C2440: 'initializing' : cannot convert from 'int *' to
 'int'
        This conversion requires a reinterpret_cast, a C-style cast or function-
style cast
srand80.cpp(2657) : error C2109: subscript requires array or pointer type
srand80.cpp(2657) : error C2440: '=' : cannot convert from 'struct Row' to 'int'

        No user-defined-conversion operator available that can perform this conv
ersion, or the operator cannot be called
srand80.cpp(2659) : error C2109: subscript requires array or pointer type
srand80.cpp(2659) : error C2440: '=' : cannot convert from 'struct Row' to 'int'

        No user-defined-conversion operator available that can perform this conv
ersion, or the operator cannot be called
srand80.cpp(2663) : error C2109: subscript requires array or pointer type
srand80.cpp(2663) : error C2440: '=' : cannot convert from 'struct Row' to 'int'

        No user-defined-conversion operator available that can perform this conv
ersion, or the operator cannot be called
srand80.cpp(2666) : error C2109: subscript requires array or pointer type
srand80.cpp(2666) : error C2440: '=' : cannot convert from 'struct Row' to 'int'

        No user-defined-conversion operator available that can perform this conv
ersion, or the operator cannot be called
srand80.cpp(2669) : error C2109: subscript requires array or pointer type
srand80.cpp(2669) : error C2679: binary '=' : no operator defined which takes a
right-hand operand of type 'int' (or there is no acceptable conversion)
srand80.cpp(2758) : error C2065: 'rowArr' : undeclared identifier
srand80.cpp(2758) : error C2065: 'MAX_ROWS' : undeclared identifier
NMAKE : fatal error U1077: 'cl.exe' : return code '0x2'
Stop.
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <math.h>
#include <string.h>
#include <omnetpp.h>
#include <fstream.h>
#include "packet_m.h"
 
#define TIMER_CONNECTION_REQUEST -1
#define PKT_FORWARD               0
#define PKT_FAIL                  1
#define PKT_SUCCES                2
#define TIMER_CONN_RELEASE        3
#define interarrival              1 
#define candidate_pathnumber      4
#define windowsize                20
#define min_BW                    0.1
#define max_BW                    2
#define ratio                     0.85
#define MAX_COLS                  30 //<------ defined it here(no error)
 
class Doarc01 : public cSimpleModule
{
private:
 
static int connection[100][100];
static int newarray[100][100];
static int pos[100];
static double RejCon;
static int ConnCounter,numoflinks;
static double totalBlockedBandwidth;
static int connectionRequest;
static double BP;
static int connflag;
static double totalCarriedBandwidth;
static double mincredit1[100][100],mincredit2[100][100],mincredit3[100][100],mincredit4[100][100];
static double altcredit1[100][100],altcredit2[100][100],altcredit3[100][100];
static double residualBandwidth[100][100];
int NumNode;
int set[500],pathestimate[500],visited[100],predecessor[100],path[100],candidatepath[30][30];
int window1[81][windowsize];
int window2[81][windowsize];
int window3[81][windowsize];
int window4[81][windowsize];
int window11[81][windowsize];
int window22[81][windowsize];
int window33[81][windowsize];
int destination;
int source;
 
cMessage *generateConReq;
 
public:
 
Doarc01();
 
virtual void initialize();
virtual void handleMessage(cMessage *msg);
double shift(int final_index,int value, int Des, int flag);
double shift1(int final_index,int value, int destn, int flag);
void merge(Row array[], int low, int mid, int upp)  //<------- line 74
void mergesort(Row array[], int low, int upp)    //<-----------line 75
void random_node();
void sort(int pinXY[100][2]);
void randomEdge();
int dijkstra(int source, int destination);
void printpath(int x,int i,int p[],int b[],int cc);
int minimum(int a[],int m[]);
void Generate();
void candidatePath1(int source, int destination);
void load();
int calMinHop();
int dijkstra2(int source, int destination);
int final_index;		
};
 
struct Row    //<------------------------------- I put it here 
{
     int cells[MAX_COLS];
     int length() const
     {
           int len = MAX_COLS; 
           while (len > 0 && cells[len-1] == 0) --len;
           return len;
     }
     bool operator <= (const Row& r)
     {
          return length() <= r.length();
     }
     Row & operator= (const Row& r)
     {
           memcpy(cells, r.cells, sizeof(cells));
     }
};
 
int Doarc01::connection[100][100]={0};
int Doarc01::newarray[100][100]={0};
int Doarc01::pos[100]={0};
double Doarc01::mincredit1[100][100]={5};
double Doarc01::mincredit2[100][100]={5};
double Doarc01::mincredit3[100][100]={5};
double Doarc01::mincredit4[100][100]={5};
double Doarc01::altcredit1[100][100]={5};
double Doarc01::altcredit2[100][100]={5};
double Doarc01::altcredit3[100][100]={5};
double Doarc01::residualBandwidth[100][100]={150};
int Doarc01::connectionRequest=0;
double Doarc01::BP=0;
int Doarc01::ConnCounter=0;
 
Define_Module(Doarc01);
 
Doarc01::Doarc01()
{
 for(int i=1;i<100;i++)
   for(int j=1;j<100;j++)
   {
      Doarc01::connection[i][j]=0;
      Doarc01::newarray[i][j]=0;
      Doarc01::mincredit1[i][j]=5;
      Doarc01::mincredit2[i][j]=5;
      Doarc01::mincredit3[i][j]=5;
      Doarc01::mincredit4[i][j]=5;
      Doarc01::altcredit1[i][j]=5;
      Doarc01::altcredit2[i][j]=5;
      Doarc01::altcredit3[i][j]=5;
      Doarc01::residualBandwidth[i][j]=150;
   }
		
  for( i=0;i<100;i++)
  Doarc01::pos[i]=0;
}
 
void merge(Row array[], int low, int mid, int upp)    
 {
      int left = low;
      int right = mid+1;
      int next = 0;
      int temparray = new int [upp-low+1];   
      // merge arrays
      while (left <= mid && right <= upp)
      {
           if (array[left] <= array[right])
               temparray[++next] = array[left++]; //<------- line 2657
           else
               temparray[++next] = array[right++]; //<-------line 2659
      }
      // take the rest of left array (if somewhat left)
      for (;left <= mid; ++left)
            temparray[++next] = array[left]; //<------------line 2663
      // take the rest of right array (if somewhat left)
      for (;right<= mid; right++)
            temparray[++next] = array[right]; //<------------line 2666
      // copy temparray
      while (0 < next--)
           array[low + next] =  temparray[next]; //<----------line 2669
 }
 
void mergesort(Row array[], int low, int upp)
 {
        if (low == upp) return;
        int mid = (low + upp)/2;
        mergesort(array, low, mid );
        mergesort(array, mid+1, upp );
        merge(array, low, mid, upp);
 }
 
void Doarc01::Generate()
{
  if(Doarc01::connectionRequest==70000)
  {    
   BP=(double) Doarc01::RejCon / (double) Doarc01::connectionRequest; 
   endSimulation();
  }
	Doarc01::connectionRequest++;
	int T=0;
	int path_lenght;
         source=index();
	int count;
	do
	{
	destination=intuniform(1,NumNode-1);
	}while(source==destination);
 
    for(int  i=0;pos[i]>0;i++)
        pos[i]=0;
	
    for(  i=0; candidatepath[i][0]>0; i++)
    {
       for (int j=0; candidatepath[i][j]>0; j++)
       {
	 candidatepath[i][j]=0;			
       }		
   }
candidatePath1(source,destination);	
for(  i=0; candidatepath[i][0]>0; i++)
{
   for ( int j=0; candidatepath[i][j]>0; j++)
   {
      cout<<candidatepath[i][j]<<"   ";
   }
       cout<<endl;
}
 
// turn candidatepath to an array of Row objects
     Row * rowArray = (Row*)&candidatepath[0][0];  
     
     // sort it
     mergesort(rowArr, 0, MAX_ROWS-1); //<----------------- line 2757
 
}

Open in new window

Here are some things to start you off...

Fixes:
1)  Move struct Row definition before virtual void initialize();
    This provides the compiler with a definition for the struct when compiling the prototype
       void merge(Row array[], int low, int mid, int upp)
2)  Add semicolon at the end of
        void merge(Row array[], int low, int mid, int upp);  //<------- line 74
        void mergesort(Row array[], int low, int upp);    //<-----------line 75
3)  In  for(i=1;i<100;i++), i goes out of scope at the end of the loop.  Instead, I did  
        Doarc01::Doarc01()
        {
         int i;
         for(i=1;i<100;i++)
4)  Changed
       void merge(Row array[], int low, int mid, int upp)    
    to
       void merge(struct Row array[], int low, int mid, int upp)    
    It's not clear to me why the "struct" is required
5)  This line
      int temparray = new int [upp-low+1];  
    is more problematic.  I'll come back to this
6)  Line 194 (for me)
        for(  i=0; candidatepath[i][0]>0; i++)
    needs a type for i, as in
       for(int i=0; candidatepath[i][0]>0; i++)
7)  Ditto for line 201
       for(  i=0; candidatepath[i][0]>0; i++)
8)  References to cout need std:: namespace specified, as i
       cout<
After looking at merge and mergesort for a while, I've decided I need to let Alex guide you on these.  I keep wanting to do it with std::vector, and that's not the way he is guiding you.

The problem I see is:
1)  The "Row array[]" argument makes a copy of the original array, and so copying temparray back into array doesn't change the caller's original array.  That makes mergesort a no-operation -- it ends up doing nothing because the copy of the array is destroyed when the function is exited.

I tried to make array a "reference to array to Row" but couldn't get the syntax right.

The solution I originally proposed ran on my box.

Alex, over to you.
>>>> Alex, over to you.
;-)

I'll do it this evening as I am currently have some guests for lunch.

You may try to compile the following (put all in .cpp file)

#include   // because of memcpy

#define MAX_COLS 10  // change here
#define MAX_ROWS 5   // change here

struct Row
{
     int cells[MAX_COLS];
     int length() const
     {
           int len = MAX_COLS;
           while (len > 0 && cells[len-1] == 0) --len;
           return len;
     }
     bool operator <= (const Row& r)
     {
          return length() <= r.length();
     }
     Row & operator= (const Row& r)
     {
           memcpy(cells, r.cells, sizeof(cells));
     }
};

 void merge(Row array[], int low, int mid, int upp)
 {
      int left = low;
      int right = mid+1;
      int next = 0;
      int temparray = new int [upp-low+1];
      // merge arrays
      while (left <= mid && right <= upp)
      {
           if (array[left] <= array[right])
               temparray[++next] = array[left++];
           else
               temparray[++next] = array[right++];
      }
      // take the rest of left array (if somewhat left)
      for (;left <= mid; ++left)
            temparray[++next] = array[left];
      // take the rest of right array (if somewhat left)
      for (;right<= mid; right++)
            temparray[++next] = array[right];
      // copy temparray
      while (0 < next--)
           array[low + next] =  temparray[next];
 }

 void mergesort(Row array[], int low, int upp)
 {
        if (low == upp) return;
        int mid = (low + upp)/2;
        mergesort(array, low, mid );
        mergesort(array, mid+1, upp );
        merge(array, low, mid, upp);
 }


int main ()
{
     // define and fill candidatepath like you did it before
     int candidatepath[MAX_ROWS][MAX_COLS] = { { 1, 2, 5, 6, 7, 0, },
                                                                                { 10, 2, 15, 6, 7, 6, 9, 99, 0} ,
                                                                                { 10, 2, 15, 87, 7, 0, } ,
                                                                                { 1100, 15, 6, 23, 0, } ,
                                                                                { 10, 2, 15, 0, } ,
                                                                             };    
  // ....

     // turn candidatepath to an array of Row objects
     Row * rowArray = (Row*)&candidatepath[0][0];
     
     // sort it
     mergesort(rowArr, 0, MAX_ROWS-1);

     // ok the candidatepath is now sorted

     return 0;
}

>>>> 1)  The "Row array[]" argument makes a copy of the original array,

No, any plain array will be passed as a pointer to the first array element. That is same wit C or C++.




Avatar of tetoo

ASKER

I did every thing as u said still same errors .. got some question to make sure that I did every thing

1. where the struct Row definition should be in the code coz I ve changed from the place that shown above in the snippet and put it  before virtual void initialize(); but same result.


>>// define and fill candidatepath like you did it before
     int candidatepath[MAX_ROWS][MAX_COLS] = { { 1, 2, 5, 6, 7, 0, },
                                                                                { 10, 2, 15, 6, 7, 6, 9, 99, 0} ,
                                                                                { 10, 2, 15, 87, 7, 0, } ,
                                                                                { 1100, 15, 6, 23, 0, } ,
                                                                                { 10, 2, 15, 0, } ,
                                                                             };    
about the definition of candidatepath[][] I did it in inisilazation in the class and I call the function
candidatePath1(source,destination) to fill it up and print it out using the for loop as following
      
      for(  i=0; candidatepath[i][0]>0; i++)
      {
            for ( int j=0; candidatepath[i][j]>0; j++)
            {
                  cout<
There have been a few typos. The following compiles

#include   // because of memcpy

#define MAX_COLS 10  // change here
#define MAX_ROWS 5   // change here

struct Row
{
     int cells[MAX_COLS];
     int length() const
     {
           int len = MAX_COLS;
           while (len > 0 && cells[len-1] == 0) --len;
           return len;
     }
     bool operator <= (const Row& r)
     {
          return length() <= r.length();
     }
     Row & operator= (const Row& r)
     {
         memcpy(&cells, &r.cells, sizeof(cells));
         return *this;
     }
};

 void merge(Row array[], int low, int mid, int upp)
 {
      int  left = low;
      int  right = mid+1;
      int  next = 0;
      Row* temparray = new Row [upp-low+1];
      // merge arrays
      while (left <= mid && right <= upp)
      {
           if (array[left] <= array[right])
               temparray[++next] = array[left++];
           else
               temparray[++next] = array[right++];
      }
      // take the rest of left array (if somewhat left)
      for (;left <= mid; ++left)
            temparray[++next] = array[left];
      // take the rest of right array (if somewhat left)
      for (;right<= mid; right++)
            temparray[++next] = array[right];
      // copy temparray
      while (0 < next--)
           array[low + next] =  temparray[next];
 }

 void mergesort(Row array[], int low, int upp)
 {
        if (low == upp) return;
        int mid = (low + upp)/2;
        mergesort(array, low, mid );
        mergesort(array, mid+1, upp );
        merge(array, low, mid, upp);
 }


int main ()
{
     // define and fill candidatepath like you did it before
     int candidatepath[MAX_ROWS][MAX_COLS] =
         { { 1, 2, 5, 6, 7, 0, },
            { 10, 2, 15, 6, 7, 6, 9, 99, 0} ,
            { 10, 2, 15, 87, 7, 0, } ,
            { 1100, 15, 6, 23, 0, } ,
            { 10, 2, 15, 0, } ,
         };    
  // ....

     // turn candidatepath to an array of Row objects
     Row * rowArray = (Row*)&candidatepath[0][0];
     
     // sort it
     mergesort(rowArray, 0, MAX_ROWS-1);

     // ok the candidatepath is now sorted

     return 0;
}

>>>> I did it in inisilazation in the class and I call the function
>>>> candidatePath1(source,destination) to fill it up and print it out using the for loop as following

Yes that is ok. The only thing you should consider is to have the same x-dim and y-dim (I called them MAX_COLS and MAX_ROWS).

>>>>      for(  i=0; candidatepath[i][0]>0; i++)
>>>>      {
>>>>            for ( int j=0; candidatepath[i][j]>0; j++)

You better would have the for loops like

     for(  i=0; candidatepath[i][0]>0 && i < MAX_ROWS; i++)
     {
           for ( int j=0; candidatepath[i][j]>0 && j < MAX_ROWS ; j++)


Otherwise you can't make full rows and must have at least one zero in each row.

 


Avatar of tetoo

ASKER

I did every thing as u said but still have the following errors

srand80.cpp
srand80.cpp(2655) : error C2065: 'Row' : undeclared identifier
srand80.cpp(2655) : error C2146: syntax error : missing ')' before identifier 'a
rray'
srand80.cpp(2655) : error C2182: 'merge' : illegal use of type 'void'
srand80.cpp(2655) : error C2059: syntax error : ')'
srand80.cpp(2656) : error C2143: syntax error : missing ';' before '{'
srand80.cpp(2656) : error C2447: missing function header (old-style formal list?
)
srand80.cpp(2681) : error C2146: syntax error : missing ')' before identifier 'a
rray'
srand80.cpp(2681) : error C2182: 'mergesort' : illegal use of type 'void'
srand80.cpp(2681) : error C2059: syntax error : ')'
srand80.cpp(2682) : error C2143: syntax error : missing ';' before '{'
srand80.cpp(2682) : error C2447: missing function header (old-style formal list?
)
srand80.cpp(2770) : error C2065: 'rowArr' : undeclared identifier
NMAKE : fatal error U1077: 'cl.exe' : return code '0x2'
Stop.

I think the struct Row difintion should be some where else I put it before virtual void initialize();
as josgood sugest
>> Move struct Row definition before virtual void initialize();
    This provides the compiler with a definition for the struct when compiling the prototype
       void merge(Row array[], int low, int mid, int upp)
>>>> srand80.cpp(2655) : error C2065: 'Row' : undeclared identifier

The struct Row must be defined above - best immediately after the include staments (like I did it in my last post) or you add it to a header file.

The error after most likely are following errors.

>>>> srand80.cpp(2770) : error C2065: 'rowArr' : undeclared identifier

Im my last code, rowArr is defined 3 lines above

        Row * rowArray = (Row*)&candidatepath[0][0];

Avatar of tetoo

ASKER

>>>>>>The struct Row must be defined above - best immediately after the include staments
:) its ok now

>>>>>>Im my last code, rowArr is defined 3 lines above

        Row * rowArray = (Row*)&candidatepath[0][0];
ya I can c that and it exactulay there but this error still appear any idea why ???

srand80.cpp
srand80.cpp(2768) : error C2065: 'rowArr' : undeclared identifier
NMAKE : fatal error U1077: 'cl.exe' : return code '0x2'
Stop.

its the only error now :(
Can you post your code around the error?
   // sort it
>>>>>     mergesort(rowArray, 0, MAX_ROWS-1);

Here, you must use rowArray  not rowArr.
Avatar of tetoo

ASKER

ya its works now without any debuging errors but the simulation hang and gave windows error from the 1st time seems that error in for loop or while .. it gives this kind of errors with such cases

I made sure that is the MAX_COLS and MAX_ROWS got the same size as the candidatepath[30][30] array wich is 30 cant think bout any other problem occured . any idea
Avatar of tetoo

ASKER

when I disable the sort function program run ok with out any problem ..

// mergesort(rowArray, 0, MAX_ROWS-1);
Can you post the contents of candidatepath? I'll do some own tests this evening when you give me the numbers.
Avatar of tetoo

ASKER

the contents of candidaepath are numbers between 1 to 80 and so it will have source and distenation and all the possible paths between them but the source will not be in the candedatepath  I ll give some example as result of the program runing:

example 1: in this example sourc=43   DESTination=23 but 1st cell in every row doesnt have the number 43 it has the 2nd number but you can see the destenation there and all paths ends with 23 . I should tell that this array is filled up with zeros at the begining but I didnt type them and the size of this array is 30*30

7   17   44   80   23  
22   11   32   39   23  
10   63   31   80   23  
22   79   16   74   14   23  
10   49   16   44   39   23  
7   17   32   80   68   23  
22   33   35   44   80   23  
7   79   16   32   39   23  
22   11   32   80   23  

example 2:
19   60   50   45   24  
31   55   57   34   24  
31   17   42   18   24  
28   80   44   35   4   24  
19   40   29   18   24  
66   41   25   57   34   24  
31   63   76   59   45   24  
19   20   33   59   4   24  
19   60   71   34   24  
31   17   15   45   24  
31   44   35   27   34   24  
19   40   29   4   24  
31   63   38   59   45   24  
19   60   42   18   24  
31   16   60   35   4   24  
19   54   12   29   18   24  
Avatar of tetoo

ASKER

>>>>I should tell that this array is filled up with zeros at the begining but I didnt type them and the size of this array is 30*30

what I mean by that is

7   17   44   80   23  
22   11   32   39   23   0 0 0 0 0 .... and so on for all the rows
10   63   31   80   23  
22   79   16   74   14   23  
10   49   16   44   39   23  
7   17   32   80   68   23  
22   33   35   44   80   23  
7   79   16   32   39   23  
22   11   32   80   23  

I dont need thse zeros in any thing in my program just to initilize the candedatepath .
If you change all

  temparray[++next]

to

  temparray[next++]  

it should work.

>>>> I dont need thse zeros in any thing in my program just to initilize the candedatepath .
You can make the candidatepath all zeros by simply

  int candidatepath[MAX_ROWS][MAX_COLS] = { 0 };
Avatar of tetoo

ASKER

now the program works but something goes wrong in candidatepath becase when I print it out b4 the sort I can see all the rows there but after sorting nothing being printed at all and its affect all the methods thats needs the candidatepath .
candidatePath1(source,destination);
	
	for(  i=0; candidatepath[i][0]>0 && i < MAX_ROWS; i++)
	{
	for ( int j=0; candidatepath[i][j]>0 && j < MAX_ROWS ; j++)
		{
			cout<<candidatepath[i][j]<<"   ";	
		}
		cout<<endl;
	}
 
 
	// turn candidatepath to an array of Row objects
     Row * rowArray = (Row*)&candidatepath[0][0];
 
	 // sort it
     mergesort(rowArray, 0, MAX_ROWS-1);
 
	 for(  i=0; candidatepath[i][0]>0 && i < MAX_ROWS; i++)
	{
	for ( int j=0; candidatepath[i][j]>0 && j < MAX_ROWS ; j++)
		{
			cout<<candidatepath[i][j]<<"   ";	
		}
		cout<<endl;
	}

Open in new window

The inner loop should go upto MAX_COLS (but that won't change any).

Please post the output of the first loop.

And the definition of the candidatepath.
Avatar of tetoo

ASKER

this is the output of the 1st loop :

60   44   80   5  
35   44   39   5  
34   57   55   68   5  
12   54   44   13   5  
42   17   44   3   5  
60   16   74   6   5  
35   17   32   39   5  
12   54   64   3   5  
60   44   39   5  
35   44   13   5  
35   44   80   5  
and nothing for the 2nd one as I said and its changed alot of things in my program.
and this is how I defined the candidate path
int set[500],pathestimate[500],visited[100],predecessor[100],path[100],candidatepath[30][30];
Avatar of tetoo

ASKER

I have got another idea and dont know why its nt working could you advice me here
I creat an array which have the length for each row in candidatepath. I called it pos and I tried to sort the array this way in the attached code snippet.

pathcount : is the number of the rows in the candidatepath.
and I defined teemp[30][30] as candidatepath
when I trace the output of the iff statment seems to b working but I tried to print out the candidatepath after sorting but still as it is and when I tried to print out teemp it does nt printout any thing at all .. IS IT right what I did or cant b sorted like this way ..thnx

for(int nn=0; nn<pathcount; nn++)
        {
                for(int ee=0; ee<pathcount-1 ; ee++)
                {
 
                        if(pos[ee]>pos[ee+1])
                        {
                           for ( int j=0; candidatepath[ee][j]>0; j++)		         {
										 teemp[ee][j]=candidatepath[ee+1][j];
                           candidatepath[ee+1][j]=candidatepath[ee][j];			 candidatepath[ee][j]=teemp[ee][j];
	                   }						}
                        
                        
                }
        }
for(int ee=0;ee<pathcount;ee++)
cout<<pos[ee]<<endl;
 
for(  i=0; candidatepath[i][0]>0; i++)
{
  for ( int j=0; candidatepath[i][j]>0; j++)
  {
    cout<<candidatepath[i][j]<<"   ";
			
  }
   cout<<endl;
}
    cout<<"++++++++++++++++++teeeeeeeeemp+++++++++++++++++"<<endl;
for(  i=0; teemp[i][0]>0; i++)
{
  for ( int j=0; teemp[i][j]>0; j++)
  {
     cout<<teemp[i][j]<<"   ";
			
  }
     cout<<endl;
}

Open in new window

>>>> candidatepath[30][30];
You should initialize it with all zeros (same may happen for teemp array), e. g. by

 int candidatepath[30][30] = { 0 };

The problem is that the struct Row determines row length by searching zeros from the back (right), while your outputs always stop at the first zero from the left. If the array isn't completely initialized, it might get bad results when sorting.


>>>> for(  i=0; candidatepath[i][0]>0; i++)
That would stop at the first zero in the first column of the table.
Avatar of tetoo

ASKER

>>>>>>>>>>>>>>You should initialize it with all zeros (same may happen for teemp array)

I did in the same way as in the attached code snippet. and the teemp as well
for(  i=0; candidatepath[i][0]>0; i++)
	{
		for (int j=0; candidatepath[i][j]>0; j++)
		{
			candidatepath[i][j]=0;
			
		}
		
	}
 
 
	for(  i=0; teemp[i][0]>0; i++)
	{
		for (int j=0; teemp[i][j]>0; j++)
		{
			teemp[i][j]=0;
			
		}
		
	}

Open in new window

>>>> for(  i=0; candidatepath[i][0]>0; i++)
>>>>     for (int j=0; candidatepath[i][j]>0; j++)
That isn't a correct initialization. It stops at the first zero in either direction and let all later non-zeros untouched.

The following is correct:

for(  i=0; i < 30; i++)
    for(  j=0; j < 30; j++)
        candidatepath[i][j]=0;


ASKER CERTIFIED SOLUTION
Avatar of tetoo
tetoo

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
>>>>              if(pos[ee]>pos[ee+1])

That is wrong. You have to compare

      if(pos[nn]>pos[ee])

and than swap row nn and row ee.

The sorting is called 'bubble sort' and the two most outer loops should be

for(int nn=0; nn
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial