473,372 Members | 840 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,372 software developers and data experts.

Bubble Sort with an array filled with classes.

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[100] 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
  1. void bubblesort (int a[], int n) // n = SIZE;
  2. {
  3.      bool sorted = false;
  4.      for (int i = 0; i < n-1 && !sorted; i++)
  5.      {
  6.          sorted = true;
  7.          for (int j = 0; j < (n-1-i); j++)
  8.          {
  9.              if (a[j] > a[j+1])
  10.              {
  11.                       swap (a[j], a[j+1]);
  12.                       sorted = false;
  13.              }
  14.          }
  15.      }
  16. }
Any ideas?
Nov 30 '07 #1
12 8605
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
  1. void bubblesort (char a[], int n) // n = SIZE;
  2. {
  3.      bool sorted = false;
  4.      for (int i = 0; i < n-1 && !sorted; i++)
  5.      {
  6.          sorted = true;
  7.          for (int j = 0; j < (n-1-i); j++)
  8.          {
  9.              if ( a[j].getSpecies() > a[j+1].getSpecies() )
  10.              {
  11.                       swap (a[j], a[j+1]);
  12.                       sorted = false;
  13.              }
  14.          }
  15.      }
  16. }
  17.  
  18.  
Nov 30 '07 #2
Ganon11
3,652 Expert 2GB
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
  1. template <class Comparable>
  2. void bubble_sort(Comparable[] array, int size);
Nov 30 '07 #3
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
  1. template <class Comparable>
  2. void bubble_sort(Comparable[] array, int size);
I havnt worked with templates so im a bit confused. Would it look something like this?

template <class Tree>
void bubble_sort(Tree[], int size);
Nov 30 '07 #4
Im afraid that may be too difficult for my experience with C++. Anyway this is what im up to:

Expand|Select|Wrap|Line Numbers
  1. void bubblesort (??? a[], int n); // Prototype
  2.  
  3. void bubblesort (Tree[], int n) // n = SIZE;
  4. {
  5.      bool sorted = false;
  6.      for (int i = 0; i < n-1 && !sorted; i++)
  7.      {
  8.          sorted = true;
  9.          for (int j = 0; j < (n-1-i); j++)
  10.          {
  11.              if ( a[j].getSpecies() > a[j+1].getSpecies() )
  12.              {
  13.                       swap (a[j], a[j+1]);
  14.                       sorted = false;
  15.              }
  16.          }
  17.      }
  18. }
Is there a data type or something I could do in order for it to work?
Nov 30 '07 #5
Ganon11
3,652 Expert 2GB
Im afraid that may be too difficult for my experience with C++. Anyway this is what im up to:

Expand|Select|Wrap|Line Numbers
  1. void bubblesort (??? a[], int n); // Prototype
  2.  
  3. void bubblesort (Tree[], int n) // n = SIZE;
  4. {
  5.      bool sorted = false;
  6.      for (int i = 0; i < n-1 && !sorted; i++)
  7.      {
  8.          sorted = true;
  9.          for (int j = 0; j < (n-1-i); j++)
  10.          {
  11.              if ( a[j].getSpecies() > a[j+1].getSpecies() )
  12.              {
  13.                       swap (a[j], a[j+1]);
  14.                       sorted = false;
  15.              }
  16.          }
  17.      }
  18. }
Is there a data type or something I could do in order for it to work?
We're closer here. First, I'll explain about templates.

Templates basically allow you to write a generalized function. So, if I had a function:

Expand|Select|Wrap|Line Numbers
  1. template <class T>
  2. T addTwo(T& objectOne, T& objectTwo) {
  3.    return objectOne + objectTwo;
  4. }
I can now call addTwo on any class or type that the + operator makes sense. So, for instance, I could call it in this way:

Expand|Select|Wrap|Line Numbers
  1. int x = addTwo<int>(5, 20);
Note the <int> - this tells the function what class or type I am filling in for the template. So, by putting the <int> there, I've effectively changed this function to

Expand|Select|Wrap|Line Numbers
  1. int addTwo(int& objectOne, int& objectTwo) {
  2.    return objectOne + objectTwo;
  3. }
But that change only lasts for that one call. I can still later say

Expand|Select|Wrap|Line Numbers
  1. double y = addTwo<double>(3.5, 12.02);
and it will work. I can even add classes that have a + operator - for instance, if I defined a Vector class, and gave it a + operator, I could say

Expand|Select|Wrap|Line Numbers
  1. Vector resultant = addTwo<Vector>(firstVec, secondVec);
All three of these examples work.

Now, in your case, you are writing a bubblesort function. When sorting, generally you only need to know if an object is less than or greater than another object. You don't care what type the objects are, as long as you can compare them - they could be numbers, they could be Trees, they could be Apple Pies, they could be anything, as long as you can compare them. You put this into code by using a template, and when it comes time to compare one object to another, use the '<' operator. You can assume that whatever object you are sorting has the '<' operator, because it makes no sense to sort an object that cannot be sorted.

Now that you are using templates, you can write a generic bubble sort function. When writing it, forget the fact that you are working with Trees. Just think about sorting some general object - it's common to think about sorting integers, as it's easy to visualize and see whether integer A is larger than or smaller than integer B. Once you have your bubblesort function working, then you have one more thing to worry about - does your Tree class overload the '<' operator?

In order to do so, you need to provide the following function in your Tree class:

Expand|Select|Wrap|Line Numbers
  1. bool operator<(Tree& rightHandSide) const;
The body of this function will determine if the current tree is less than the rightHandSide tree, and if so, return true. Otherwise, it must return false. This is where you will compare the Tree's species type and anything else you wanted to sort by.
Nov 30 '07 #6
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
  1. for (int i = 0; inData; i++)
  2.     {
  3.         inData >> s;
  4.  
  5.         inData.ignore(MAX, '\t');
  6.         inData >> h;
  7.  
  8.         inData.ignore(MAX, '\t');
  9.         inData >> tD;
  10.  
  11.         inData.ignore(MAX, '\t');
  12.         inData >> cPF;
  13.  
  14.         inData.ignore(MAX, '\t');
  15.  
  16.         Tree[i].setSpecies(s);
  17.         Tree[i].setHeight(h);
  18.         Tree[i].setTrunkDiameter(tD);
  19.         Tree[i].setCostPerFoot(cPF);
  20.  
  21.         count++;
  22.     }
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
weaknessforcats
9,208 Expert Mod 8TB
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
  1. bool operator<(Tree& lefthandside, Tree& rightHandSide);
  2.  
In your sort you should, be able to:
Expand|Select|Wrap|Line Numbers
  1. if ( a[j] < a[j+1] )
  2. {
  3.  
  4. }
  5.  
Nov 30 '07 #8
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
  1. void bubblesort ( ChristmasTree a[],int n) // n = SIZE;
  2. {
  3.      bool sorted = false;
  4.      for (int i = 0; i < n-1 && !sorted; i++)
  5.      {
  6.          sorted = true;
  7.          for (int j = 0; j < (n-1-i); j++)
  8.          {
  9.              if ( a[j].getSpecies() > a[j+1].getSpecies() )
  10.              {
  11.                       swap (a[j], a[j+1]);
  12.                       sorted = false;
  13.              }
  14.  
  15.  
  16.  
  17.          }
  18.      }
  19. }
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
  1. for (int i = 0; i < count - 1; i++)
  2.      {
  3.          cout << fixed                   << setprecision(2) 
  4.               << Tree[i].getSpecies()    << endl;
  5.          cout << Tree[i].getHeight()     << endl;
  6.          cout << Tree[i].calculateCost() << endl;
  7.  
  8.               total += Tree[i].calculateCost();
  9.      }
  10.  
  11.      cout << "There are " << count << " trees listed." << endl;
  12.      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
  1. Blue Spruce
  2. 8.36
  3. 188.10
  4. Blue Spruce
  5. 9.98
  6. 224.55
  7. Douglas Fir
  8. 3.38
  9. 41.41
  10. Douglas Fir
  11. 4.88
  12. 59.78
  13. Douglas Fir
  14. 8.59
  15. 105.23
  16. Fraser Fir
  17. 6.00
  18. 77.70
  19. Fraser Fir
  20. 6.00
  21. 77.70
  22. Fraser Fir
  23. 6.00
  24. 77.70
  25. Fraser Fir
  26. 6.00
  27. 77.70
  28. Fraser Fir
  29. 6.00
  30. 77.70
  31. Fraser Fir
  32. 6.00
  33. 77.70
  34.  
  35. Ponderosa Pine
  36. 11.37
  37. 130.75
  38. Ponderosa Pine
  39. 12.83
  40. 147.54
  41. Ponderosa Pine
  42. 11.09
  43. 127.53
  44. Ponderosa Pine
  45. 5.58
  46. 64.17
  47. Ponderosa Pine
  48. 6.81
  49. 78.31
  50. Ponderosa Pine
  51. 4.12
  52. 47.38
Nov 30 '07 #9
Ganon11
3,652 Expert 2GB
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
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
Ganon11
3,652 Expert 2GB
I mean you should either say:

Expand|Select|Wrap|Line Numbers
  1. 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)) {
  2.    // swap...blah blah blah.
  3. }
or you should say

Expand|Select|Wrap|Line Numbers
  1. if (a[j].species > a[j+1].species) {
  2.    // swap...blah blah blah
  3. } else if (a[j] and a[j+1] have the same species AND a[j].cost > a[j+1].cost) {
  4.    // swap...blah blah blah
  5. }
Nov 30 '07 #12
weaknessforcats
9,208 Expert Mod 8TB
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
  1. bool Seq1(Tree& left, Tree& right);            //sorts ascending
  2. bool Seq2(Tree& left, Three& right);          //sorts descending
  3. bool Seq3(Tree&left, Tree& right);            //sorts by SPECIES ascending
  4. etc...
  5.  
Your sort:
Expand|Select|Wrap|Line Numbers
  1. void bubblesort (int a[], int n, bool (*Compare)(Tree&, Tree&))
  2. {
  3.        if (Compare(a[i], a[i+1])
  4.        {
  5.                //a[i] is "less" than a[i+1]
  6.        }
  7. }
  8.  
Then you can call the sort to get three different sequences:
Expand|Select|Wrap|Line Numbers
  1. bubblesort(a, 100, Seq1);
  2. bubblesort(a, 100, Seq2);
  3. bubblesort(a, 100, Seq3);
  4.  
To use your operator< you could:
Expand|Select|Wrap|Line Numbers
  1. bool Seq4(Tree& left, Tree& right)
  2. {
  3.     return left < right:
  4. }
  5.  
and to sort in the reverse sequence (>=):
Expand|Select|Wrap|Line Numbers
  1. bool Seq4(Tree& left, Tree& right)
  2. {
  3.     if (left < right)
  4.      {
  5.            return false;
  6.      }
  7.      return true;
  8.  
Dec 1 '07 #13

Sign in to post your reply or Sign up for a free account.

Similar topics

4
by: Chris | last post by:
I have a bubble sort for a 2-dimensional array that sorts a string,number pair based on the number. The code for the sort is as follows: Private Sub SortArray(ByRef roundarray(,) As String)...
8
by: Protoman | last post by:
Why doesn't my double bubble sort algorithm sort; it just spits the numbers out, int the exact same order that I inputted them. Code: void swap(int& i,int& j) { i^=j; j^=i; i^=j;
0
by: Slowjam | last post by:
How do I correct the program below to search all the anagrams in a given file. First, for each word, build another word (its key) with all its letters sorted. For instance, build "dorw" for...
5
kuchma2000
by: kuchma2000 | last post by:
Hi. I have a C program (see code below) which I need to urgrade. All I need to do is: a. Extract the temps for the City #1 and store in a one dimensional array, display the array. b. Sort the one...
20
by: Acolyte | last post by:
Hey, I'm working on a project that involves sorting a two-dimensional array of integers using bubble sort. I've got it semi-working, my only issue is that it seems to be 'losing' values, I'm assuming...
5
Sheepman
by: Sheepman | last post by:
I've been working on this since Wednesday and am at a total loss. I need to bubble sort a randomly generated list of numbers. I got the numbers in about 15 minutes. The remainder of the 3 days have...
14
by: xtheendx | last post by:
I am writing a gradbook type program. It first allows the user to enter the number of students they want to enter. then allows them to enter the first name, last name, and grade of each student. The...
7
by: mahdiahmadirad | last post by:
Hi dears! I wrote a simple bubble sort algorithm. it works properly when we compare full arrays but i want to sort a 2d array according to a specific part of array. it has some problem to swapping...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: aa123db | last post by:
Variable and constants Use var or let for variables and const fror constants. Var foo ='bar'; Let foo ='bar';const baz ='bar'; Functions function $name$ ($parameters$) { } ...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.