Sort of <algorithm> problem

[vrakas]

hello,
I have 2 int arrays Mass[n] and Volume[n],
and i need to sort them according to their quotient(M[i]/V[i]) i.e. density.
(oh and I want to use the sort of <algorithm>)
I really HAVE NO IDEA how to do this using the modified sort but a friend told me i could create a struct that would have the two arrays in. I tried so:
struct item{
unsigned int V[];
unsigned int M[];
};
but the problem is that the length of the array is given by the user.(struct must be defined before main but i get n(length) obviously after int main() starts).
i thought of std::sort(rotsa.begin(), rotsa.end(), &rotsa_sorter);
and using the comp:
bool rotsa_sorter(rotsa const& lhs, rotsa const& rhs) {

if (((lhs.M)*(rhs.V)) > ((rhs.M)*(lhs.V)))
//instead of having two quotients i used that if a/b=c/d and b,c!=0 then a*d=c*b
{return lhs>rhs;}
else{return lhs<rhs;}
}
but it didn't work at all. Any ideas? either on another way of doing the sort or maybe you could help me correct my code?
Thanks very very much :)

[MrHutch]

Are the arrays concurrent? So you're looking for the quotient of M[0] and V[0], then M[1] and V[1] all the way up to M[n] and V[n]?

[Catfish2]

Please use code tags for posting source code, see the <> button on the right menu when posting.

C++ has an alternative to plain arrays: std::vector (in your case, you could also use std::list).

#include <vector>

struct item {
    std::vector<unsigned int> V;
    std::vector<unsigned int> M;
};

Now you can use resize() to change the size to whatever the user wants.
http://cplusplus.com/reference/stl/vector/resize/

[MrHutch]

If they're concurrent, I'd just use a class then have a vector for that class. Ignore any dodgy indentation, it's VS's fault.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class item
{
private:
	int mass;
	int volume;
public:
	item():mass(0), volume(0){};
	void Set(int m, int v)
	{
		mass = m;
		volume = v;
	}
	int GetQuotient()
	{
		return mass/volume;
	}
};

bool QuotientComp(item a, item b)
{
	return a.GetQuotient() < b.GetQuotient();
}

int main(int argc, char* argv[])
{
   vector<item> my_items;
   vector<item>::iterator it;
   item temp;

   temp.Set(10,2); // Quotient will be 5
   my_items.push_back(temp);

   temp.Set(8,4);  // Quotient will be 2
   my_items.push_back(temp);

   temp.Set(8,2); // Quotient will be 4
   my_items.push_back(temp);

   // Unsorted order by quotient: 5 2 4

   sort(my_items.begin(), my_items.end(), QuotientComp);

   cout << "Sorted items:";

   for (it=my_items.begin(); it!=my_items.end(); ++it)
	   cout << " " << it->GetQuotient();
}

Output:

Sorted items: 2 4 5 

[vlad from moscow]

You can create an auxiliary array of pairs, sort it and then copy each first member of pair in the original array.

[kev82]

Sorting the two arrays is a bit tricky, because std::sort expects the items being sorted to be single objects, and each item you have is actually two separate things. You can take an approach like iHutch105 so that each element is an actual object, and you only have a single array, you could make a proxy object that correctly handles assignment and comparison on the underlying arrays - although this is a bit complex, or personally, I would recommend you sort the indices. That is, you leave the original arrays alone, but create a new array of indices into the actual arrays, and sort that.

To sort the indices you should:

1) Create an array with with same number of elements as your mass and volume and set array[i] = i
2) Create a function indexLessThan(int *mass, int *density, int index1, int index2) which returns true if the density at index index1 is less than the density at index2 - you pretty much implemented this in your original post
3) Call sort on the array of indices using tr1::bind(indexLessThan, massArray, densityArray, _1, _2) as the comparator. If you don't have access to bind, this can be done with a struct with operator() - google for functors.
4) You should now be left with an array where the i'th element gives the index in the mass and volume arrays of the i'th sorted element. ie the mass of the third sorted item is mass[sortedIndices[2]].

Also be careful using integers for mass and volume.

[vlad from moscow]

@kev82

The problem is that now you have another task to build the result array mass according to the sorted indexes.:)

[vrakas]

although i got some creative answers here it turned out to be more easy to write a quicksort on my own. :) but thank you all

[viliml]

Ther eis a much much easier way which requires only for you to make a vector of pairs and a function! The first element of the pair is the mass, and the second is the volume

#include <algorithm>
#include <vector>

using namespace std;

bool comp(pair<int, int> a, pair<int, int> b)
{
      return a.first/a.second<b.first/b.second;
      }

int main()
{
     vector<pair<int, int> > density;
     // yadda yadda yadda
     sort(density.begin(), density.end(), comp);
     // blah blah blah
     }