435,474 Members | 3,139 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,474 IT Pros & Developers. It's quick & easy.

Bubble Sort with an array filled with classes.

 P: 25 Hello everyone, I am familiar with a normal bubble sort when dealing with an array of number but I am unsure as how to implement a sort when I have an array that is filled with classes which hold multiple values. I need to make a bubble sort that reaches into an array called Tree which has in each storage location a class called Christmas Tree which have the values Species, Height, trunkDiameter, and costPerFoot. The sort will need to sort the different trees by species (which is a string) and then by costPerFoot (a double). Regular bubble sort: Expand|Select|Wrap|Line Numbers void bubblesort (int a[], int n) // n = SIZE; {      bool sorted = false;      for (int i = 0; i < n-1 && !sorted; i++)      {          sorted = true;          for (int j = 0; j < (n-1-i); j++)          {              if (a[j] > a[j+1])              {                       swap (a[j], a[j+1]);                       sorted = false;              }          }      } } Any ideas? Nov 30 '07 #1
12 Replies

 P: 25 I had an idea. I have a function called getSpecies() and getCost() which simply returns the values found in whatever array area your in. Could I... Expand|Select|Wrap|Line Numbers void bubblesort (char a[], int n) // n = SIZE; {      bool sorted = false;      for (int i = 0; i < n-1 && !sorted; i++)      {          sorted = true;          for (int j = 0; j < (n-1-i); j++)          {              if ( a[j].getSpecies() > a[j+1].getSpecies() )              {                       swap (a[j], a[j+1]);                       sorted = false;              }          }      } }     Nov 30 '07 #2

 Expert 2.5K+ P: 3,652 That idea will work...if you pass an array of this class/struct. Right now you are passing in a character array, then trying to use a class function on it. Characters are not classes. You will want to pass a Tree[] to your function and sort that. Even better, overload the < and > operators for Tree. You can compare names first - if the names are the same, you can compare some other attribute. This will allow you to write a generalized bubblesort using templates: Expand|Select|Wrap|Line Numbers template  void bubble_sort(Comparable[] array, int size); Nov 30 '07 #3

 P: 25 That idea will work...if you pass an array of this class/struct. Right now you are passing in a character array, then trying to use a class function on it. Characters are not classes. You will want to pass a Tree[] to your function and sort that. Even better, overload the < and > operators for Tree. You can compare names first - if the names are the same, you can compare some other attribute. This will allow you to write a generalized bubblesort using templates: Expand|Select|Wrap|Line Numbers template  void bubble_sort(Comparable[] array, int size); I havnt worked with templates so im a bit confused. Would it look something like this? template void bubble_sort(Tree[], int size); Nov 30 '07 #4

 P: 25 Im afraid that may be too difficult for my experience with C++. Anyway this is what im up to: Expand|Select|Wrap|Line Numbers void bubblesort (??? a[], int n); // Prototype   void bubblesort (Tree[], int n) // n = SIZE; {      bool sorted = false;      for (int i = 0; i < n-1 && !sorted; i++)      {          sorted = true;          for (int j = 0; j < (n-1-i); j++)          {              if ( a[j].getSpecies() > a[j+1].getSpecies() )              {                       swap (a[j], a[j+1]);                       sorted = false;              }          }      } } Is there a data type or something I could do in order for it to work? Nov 30 '07 #5

 P: 25 Im so sorry but some of that I dont understand, im only in Intro to C++ and we are at the final stage of our learning for the semester so vectors and the like I havnt gotton to yet. I did however find a way that it will work but I encounter a problem that maybe someone can help me with. The point of this program is to open up a file with an unknown number of Tree[]s in it then read the lines and put the correct data into the correct part in the array in the class. Example data Douglas Fir 3.38 4.38 12.29 Ponderous Pine 11.37 5.45 11.5 So I have a for loop that I thought would read each part and put it into its correct area: Expand|Select|Wrap|Line Numbers for (int i = 0; inData; i++)     {         inData >> s;           inData.ignore(MAX, '\t');         inData >> h;           inData.ignore(MAX, '\t');         inData >> tD;           inData.ignore(MAX, '\t');         inData >> cPF;           inData.ignore(MAX, '\t');           Tree[i].setSpecies(s);         Tree[i].setHeight(h);         Tree[i].setTrunkDiameter(tD);         Tree[i].setCostPerFoot(cPF);           count++;     } But whenever I check my program it only gives me the output of my constructor function so its as if the programs cursor is not in the right location or not doing something right. This is last problem I can find so help is appreciated! Nov 30 '07 #7

 Expert Mod 5K+ P: 9,197 In order to do so, you need to provide the following function in your Tree class: Code: ( cpp ) bool operator<(Tree& rightHandSide) const; There is also the option of writing the operator< as a regular global function: Expand|Select|Wrap|Line Numbers bool operator<(Tree& lefthandside, Tree& rightHandSide);   In your sort you should, be able to: Expand|Select|Wrap|Line Numbers if ( a[j] < a[j+1] ) {   }   Nov 30 '07 #8

 P: 25 Ok, ive made some progress and im down to my last two problems. First off, after ive opened up the file and sorted my trees by Species, I want to sort them ALSO by cost. but I am unsure of how to do that. Current bubblesort for species: Expand|Select|Wrap|Line Numbers void bubblesort ( ChristmasTree a[],int n) // n = SIZE; {      bool sorted = false;      for (int i = 0; i < n-1 && !sorted; i++)      {          sorted = true;          for (int j = 0; j < (n-1-i); j++)          {              if ( a[j].getSpecies() > a[j+1].getSpecies() )              {                       swap (a[j], a[j+1]);                       sorted = false;              }                }      } } The last problem is with outputting the trees to the screen. I have a for loop that outputs them like so: Expand|Select|Wrap|Line Numbers for (int i = 0; i < count - 1; i++)      {          cout << fixed                   << setprecision(2)                << Tree[i].getSpecies()    << endl;          cout << Tree[i].getHeight()     << endl;          cout << Tree[i].calculateCost() << endl;                 total += Tree[i].calculateCost();      }        cout << "There are " << count << " trees listed." << endl;      cout << "The average price of a tree is " << total/count << endl; But in the actual output I get my constructor listed like 20 times before it starts listing the other trees. whats up with that? Ex. Expand|Select|Wrap|Line Numbers Blue Spruce 8.36 188.10 Blue Spruce 9.98 224.55 Douglas Fir 3.38 41.41 Douglas Fir 4.88 59.78 Douglas Fir 8.59 105.23 Fraser Fir 6.00 77.70 Fraser Fir 6.00 77.70 Fraser Fir 6.00 77.70 Fraser Fir 6.00 77.70 Fraser Fir 6.00 77.70 Fraser Fir 6.00 77.70   Ponderosa Pine 11.37 130.75 Ponderosa Pine 12.83 147.54 Ponderosa Pine 11.09 127.53 Ponderosa Pine 5.58 64.17 Ponderosa Pine 6.81 78.31 Ponderosa Pine 4.12 47.38 Nov 30 '07 #9

 Expert 2.5K+ P: 3,652 Do you want to sort separately i.e. have two separate functions - one that sorts by cost, the other that sorts by species? This is fairly simple - you can copy and paste your code, and change getSpecies to getCost. Or do you want them sorted by species, and each subset of species sorted by cost? To do this, in your sort, consider when you would need to sort by cost - only when the species is the same, right? Then you can add another possibility to your if...statement in the inner loop. Nov 30 '07 #10

 P: 25 Do you want to sort separately i.e. have two separate functions - one that sorts by cost, the other that sorts by species? This is fairly simple - you can copy and paste your code, and change getSpecies to getCost. Or do you want them sorted by species, and each subset of species sorted by cost? To do this, in your sort, consider when you would need to sort by cost - only when the species is the same, right? Then you can add another possibility to your if...statement in the inner loop. When you say add another possiblity do you mean add something like: if(a[j].getSpecies() > a[j+1].getSpecies() || a[j].calculateCost() > a[j+1].calculateCost()) or add another if statement? Nov 30 '07 #11

 Expert 2.5K+ P: 3,652 I mean you should either say: Expand|Select|Wrap|Line Numbers if (a[j].species > a[j+1].species OR (a[j] and a[j+1] have the same species AND a[j].cost > a[j+1].cost)) {    // swap...blah blah blah. } or you should say Expand|Select|Wrap|Line Numbers if (a[j].species > a[j+1].species) {    // swap...blah blah blah } else if (a[j] and a[j+1] have the same species AND a[j].cost > a[j+1].cost) {    // swap...blah blah blah } Nov 30 '07 #12

 Expert Mod 5K+ P: 9,197 You might consider a comparator function. Here you write a function that does the correct comparison and pass the address of the function to the bubble sort as an argument. You would write a function that takes two Tree& arguments and you pass a pointer to this function to the bubble sort as a function pointer. Inside the sort you call the function by using the function pointer. The sort will then produce the sequence based on that call. Assume you have written: Expand|Select|Wrap|Line Numbers bool Seq1(Tree& left, Tree& right);            //sorts ascending bool Seq2(Tree& left, Three& right);          //sorts descending bool Seq3(Tree&left, Tree& right);            //sorts by SPECIES ascending etc...   Your sort: Expand|Select|Wrap|Line Numbers void bubblesort (int a[], int n, bool (*Compare)(Tree&, Tree&)) {        if (Compare(a[i], a[i+1])        {                //a[i] is "less" than a[i+1]        } }   Then you can call the sort to get three different sequences: Expand|Select|Wrap|Line Numbers bubblesort(a, 100, Seq1); bubblesort(a, 100, Seq2); bubblesort(a, 100, Seq3);   To use your operator< you could: Expand|Select|Wrap|Line Numbers bool Seq4(Tree& left, Tree& right) {     return left < right: }   and to sort in the reverse sequence (>=): Expand|Select|Wrap|Line Numbers bool Seq4(Tree& left, Tree& right) {     if (left < right)      {            return false;      }      return true;   Dec 1 '07 #13 