Solved

Sorts and Saves

Posted on 1997-12-14
13
247 Views
Last Modified: 2011-08-18
I'm having a problem sorting values that are read from an external text file which initialize the array.  The program can read the values with no problem it's just the swap part of the algorithm doesn't seem to work.  I think it has to do with the reassignment of the array variables when the swap function is called.  The other problem is with the destructor function that saves the sorted data to disk.  When viewing the output file, all I see are scientific notation numbers.  The following is the way the input and ouput files should look respectively:

INPUT FILE:   6 7
                       5 5
                       4 3

OUTPUT FILE:  4 3
                           5 5
                           6 7

***************************CODE********************************
#include <iostream.h>
#include <math.h>
#include <iomanip.h>
#include <fstream.h>   //for file streams
#include <stdlib.h>    //for exit function

typedef int bool;
const int false = 0;
const int true = (!false);

class Rectangle  {
      public:
            Rectangle(double inLength = 1.0, double inWidth = 1.0);
            double perimeter() const;
            double area() const;
            void   SetWidth(double w);
            void   SetLength(double l);
            double GetWidth() const;
            double GetLength() const;
            double diagonal() const;
            bool   isSquare() const;
      private:
            double length;
            double width;
};
Rectangle :: Rectangle(double inLength, double inWidth) : length(inLength), width(inWidth){}//Constructor initializer

class recList {
      public:
        recList();
        void  sort();
        void  display();
        ~recList();
      private:
        int n;
        Rectangle recArray[20];
        void  swap(Rectangle &rec1, Rectangle &rec2);
};

void main()
{
  recList recListObj; //declaration of recListObj is of class recList
 
  recListObj.sort();
  recListObj.display();
}

//Functions for class recList/////////////////////////////////////////////////////////////////////////////////////
recList :: recList() //Reads values from input file and assigns them to Rectangle(), SetWidth(), and SetLength()
{
      double inLength, inWidth;
      ifstream infile("proj5in.txt");
      if (!infile)
      {
            cerr << "ERROR READING FILE!";
            exit(1);
      }
      else
            n = 0;
            while ((n < 20) && (infile >> inLength >> inWidth))  //Bounds checking of array
        {
                  recArray[n] = Rectangle(inLength, inWidth);
                  recArray[n].SetWidth(inWidth);
                  recArray[n].SetLength(inLength);
                  n ++;
            }
}      

void recList :: sort()  //Sorts values in recArray in ascending order
{
      int j, top, largest;

      for (top = 0; top < n-1; top++)
       {
             largest = top;
            Rectangle rec1 = recArray[largest].area(), rec2 = recArray[top].area();             
             for (j = top + 1; j < n; j++)
                  if (recArray[j].area() < recArray[largest].area())
                        largest = j;

            swap (rec1, rec2);

            cout << recArray[top].area() << "   " << recArray[largest].area() << endl;
      }
}

void  recList :: swap(Rectangle &rec1, Rectangle &rec2)
{
      Rectangle temp = rec1;
      rec1 = rec2;
      rec2 = temp;
}

void recList :: display()  //Uses sorted array values to control rectangle/square output
{
      //Functions that format decimal point two places
      cout.setf(ios::fixed);
      cout.precision(2);
      
      for (int j = 0; j < n; j++)
      {      
            cout << "Array Element:  " << j  << endl;
            cout << "  Length:" << setw(12) << recArray[j].GetLength();
            cout << setw(20) << "Width:" << setw(12) << recArray[j].GetWidth() << endl;
            cout << "    Area:" << setw(12) << recArray[j].area();
            cout << setw(20) << "Perimeter:" << setw(12) << recArray[j].perimeter() << endl;
            cout << "Diagonal:" << setw(12) << recArray[j].diagonal() << setw(20) << "Type:"
                        << setw(12); recArray[j].isSquare();
          if (recArray[j].isSquare() == 1)//Uses value returned from isSquare() to indicate rectangle or square
                     cout << "Square";
            else
                  cout << "Rectangle";
          cout << endl << endl;
      }
}

recList :: ~recList()  //Writes sorted array values to .txt file
{
      double inLength, inWidth;
      ofstream outfile ("proj5out.txt");
      if (!outfile)
      {
            cerr << "ERROR OPENING FILE!";
            exit(1);
      }
      else
            n = 0;
            while ((n < 20) && (outfile << inLength << inWidth))
        {
                  recArray[n] = Rectangle(inLength, inWidth);
                  recArray[n].SetWidth(inWidth);
                  recArray[n].SetLength(inLength);
                  n ++;
            }
}

//Functions for class rectangle///////////////////////////////////////////////////////////////////////////////////
double Rectangle :: perimeter() const
{
      return (2 * width + 2 * length);//Returns perimeter of rectangle or square
}

double Rectangle :: area() const
{
      return (length * width);//Returns area of rectangle or square
}

void Rectangle :: SetWidth(double w)
{
      width = w;//Assigns w to width
}

void Rectangle :: SetLength(double l)
{
      length = l;//Assigns l to length
}

double Rectangle :: GetWidth() const
{
      return width;//Returns value of width
}

double Rectangle :: GetLength() const
{
      return length;//Returns value of length
}

double Rectangle :: diagonal() const
{
      return (sqrt(pow(length, 2) + pow(width, 2)));//Returns diagonal of rectangle or square
}

bool Rectangle :: isSquare() const
{
       if (length == width)//Tests length and width variables for rectangle or square attributes
            return true;
      else
            return false;
}
Any help is appreciated.
0
Comment
Question by:j_daniels
  • 8
  • 4
13 Comments
 

Author Comment

by:j_daniels
ID: 1176218
Edited text of question
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176219
Answer comming.  I'm typing now.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176220
The basic problem with your sort is thatwhen you swap, you are swaping rectangles that are local (temporary) variables, not items in the array.  That is, you copy items out of the array and then swap the copies.

As for the rest of the logic to the sort, I'm having trouble following it to see if it works.  I suspect there may be another problem because it is not making sense to me.  I can help you fix it, if you want, but there is a better way...

The C++ standard library has a quicksort built in.  Quicksort is MUCH MUCH faster than a bubble-type sort.  (The only dissadvantage is that it recursive and therefore requires a descent amount of stack space, but that should not be a problem.)

The sort procedure is in the search library header search.h).  You specify a pointer to the array, the number of elements and their size.  In addition, you specify a pointer to a procedure that you write that compares two elements to determine which should be considered smaller.  



0
 
LVL 22

Expert Comment

by:nietod
ID: 1176221
The compare procedure would be written like this

int CmpForSrt(const void *P1, const void *P2)
{
   Rectangle *R1 = (Rectagle *) P1;
   Rectangle *R2 = (Rectagle *) P2;

   return R1->area() - R2->area();
}

Note that the return value falls into three categories  If R1<R2 then it should return a number less than 0.  If the two are equal it should return 0.  If R1>R2 it should return a number greater than 0.  The simple subtraction handles all those cases.


0
 
LVL 22

Expert Comment

by:nietod
ID: 1176222
to sort you would then do

qsort(RecArray,n,sizeof(Rectangle),CmpForSrt);

for an array of only a few items, the sqort will be marginally faster.  As the array size grows the speed improvement becomes much larger.  After a hundred items, or so, Q-sort is an order of manitude faster.

I'm not trying to get out of helping you with the bubble sort, I just think you are better off with the q-sort.


The reason that you are getting scientific notation in the output is that the numbers you are outputing are doubles, or floating point numbers.  There are two ways around this.  First, if you do not need decimals, you could change to use integers everywhere instead of doubles.  This will speed things up and reduce the size of code and data.  Of course it means that you can't have fractional coordinates.  I'm not sure if this is a problem in your case or not, in many cases, however, integer coordinates are desirable.  

The other solution is to make the stream output the doubles in the format you want.  I'm not an expert with streams, go I don't know all the options and all the details.  In addition, I don't know exactly what you want.  Your sample output file showed only integers (which is why I mentioned the other option).  Here are your basic posibilities.  You could ouput only the integer porion of the doubles and loose some accuracy, I don't know why you would want this, but you didn't show decimals in your file.  You could output only the decimals that are needed.  That is, 1.00 would appear as 1, but 1.02 would appear as 1.02.  Finally, you could output the numbers as a fixed point format.  In this case all the numbers would have the same number of decimals regardless of whethor or not they were needed.  For example, 1 would appear as 1.00.  (You of course, specify the number of decimals.)

To set the stream to use the format where it displays the numbers with the number of decimals needed (and not extra) use

cout.setf(0,ios_base::floatfield);

To set the stream to use a fixed point, use

cout.setf(ios_base::fixed,ios_base::floatfield);
cout.precision(4);

Change the 4 to the number of decimals you want.

Hope this helps.
0
 

Author Comment

by:j_daniels
ID: 1176223
Unfortunately, I need to use a bubble sort in the program even though it's not as fast as qsort.  As for the output to file problem, I think the values can be changed to ints for writing to file since all that was specified were integers in the output file, especially since the numbers read from file are ints.
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Expert Comment

by:Rumata
ID: 1176224
Change Swap to be:
void recList :: swap(Rectangle &rec1, Rectangle &rec2)
{
Rectangle temp = *rec1;
*rec1 = *rec2;
*rec2 = temp;
}

As for the destructor, use fprintf with %lf flag. Make sure
you include stdio.h

If you need help with fprintf, here's what you do:

FILE *filepointer;

filepointer=fopen("output.file","w");
fprintf(filepointer, "%lf %lf\n",inLength, inWidth);
...
fclose(filepointer);

Hope this helps

0
 
LVL 22

Expert Comment

by:nietod
ID: 1176225
j_daniels is using streams.   fprintf() is not for use with streams.  Better to configure the stream than to go back to C from C++.

Try fixing the Swap and see if the bubble sort works.  If not, I can propose some fixes.  But the way you wrote it seems weird to me.  I'm not sure it it works.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176226
Note, if the permenant file will contain ints.  Is there ary reason to have doubles at runtime?  Ints are smaller and faster.

a first step in fixing the bubble sort, if needed.  Is that in most buble sorts the outer loop starts with the whole array and works down to the first item.  Each iteration of the outer loop finds the largest item in the portion of the array works with and moves it to the end.  Thus the next iteration can work with one less item since the largest item was moved to the end.

you get something like

for (int i=n; i > 0; --i)
{
   // go through - to i and move largest to i.
}

I'll provide more if you need it.  It's just I'm an ex-physics teacher and still believe in letting people do it for themselves.
0
 

Author Comment

by:j_daniels
ID: 1176227
Unfortunately the sort still won't work, keep getting illegal indirection errors with the pointers.  As for the sort algorithim, the reason why I'm using it is because I know it works.  I tested it in another program using a similar setup of classes and the algorithim works fine, of course all the variables were ints.
0
 
LVL 22

Accepted Solution

by:
nietod earned 200 total points
ID: 1176228
Opps.  Rumata threw me off track.  I knew I had commented about your swap.  It wasn't that it was wrong however, it was the code that called the swap that is in error, since it calls swap with local variables, not array entries.  Iou can ignore rumata's comment, it has some problems with indirection and your code was fine.  You need to change the code that calls swap.

But I see some problems.  For example the statmenet

Rectangle rec1 = recArray[largest].area()

(and a similar one for rec2) makes no sense.  area() returns a double, not a rectangle.  I'll assume the ".area()" is a mistake and remove it.

Now I'll change swap to work with array entries, instead of rec1 and rec2.

for (top = 0; top < n-1; top++)
{
   largest = top;
   Rectangle rec1 = recArray[largest];
   Rectangle rec2 = recArray[top];

   for (j = top + 1; j < n; j++)
       if (recArray[j].area() < recArray[largest].area())
          largest = j;
   swap (recArray[largest],recArray[top]);

   }
}
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176229
Oh, having posted this, I see how your algorithm works and why I was confussed.  Your are sorting backwards (from largest to smallest) and your algorithm moves one item toward the front of the array on each iteration.  The usual way is to move it to the back.  That is why I was confussed.  This looks like it should work.  

Now for some clean-up.  We can drop rec1 and rec2.  They aren't being used.  For safety you would be best to declare top, j, and largest when they are initialized, not before.  

Now for some optimization.  In most cases, largest should not change for each j (inner loop iteration).  However, you repeatidly calculate the area of largest, event though it doesn't change often.  To fix this, I calculate and save the area a the start and whenever largest changes.

for (int top = 0; top < n-1; top++)
{
   int    largest   = top;
   double largearea = recArray[largest].area()

   for (int j = top + 1; j < n; j++)
   {
      double jarea = recArray[j].area();

      if (jarea < largearea)
      {
         largest = j;
         largearea = jarea;
      }
   }
   swap (recArray[largest],recArray[top]);
}
                        }
that should speed things up some.  A q-sort would still be a lot better.  Why must you use a bubble sort?

0
 

Author Comment

by:j_daniels
ID: 1176230
Thx so much for the help.
0

Featured Post

Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

Join & Write a Comment

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

707 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now