2

Here is my problem: I have a struct:

struct point { int x; int y; }; 

and then I have an array:

for (int i = 0;i < n;i++) { arr[i].x=rand() % n + 1; } 

I defined the quicksort function as follows:

 void quicksort(int *a, int left, int right); 

and I want to sort the point by X coordinate, so I call the quicksort:

quicksort(arr.x, 0, n-1); 

And this is the error message:

error: request for member 'x' in 'arr', which is of non-class type 'point [(((unsigned int)(((int)n) + -0x000000001)) + 1)]'

Sorry if the question is too stupid or badly formulated, the truth is I'm a newbie and I'm really willing to learn as much as possible and I'd be very thankful for your help!

4
  • 1
    Avoid using rand. Commented Sep 23, 2013 at 15:35
  • 5
    You should use std::sort, and define a custom comparator. Commented Sep 23, 2013 at 15:36
  • 1
    You cannot slice up structures that way. (Even if you could, you wouldn't want to, because that would sort the x coordinates and pair them against a random y coordinate rather than the one they were paired with originally.) Commented Sep 23, 2013 at 15:39
  • What is the value of y Commented Sep 23, 2013 at 15:40

7 Answers 7

3

If you always want to sort by x, then you can hard-code it into the sort function, and just pass a pointer to the array to sort:

void quicksort(point * arr, int left, int right) { // test points with // if (arr[i].x < arr[j].x) {/* i sorts before j */} } quicksort(arr, 0, n-1); 

To specify a class member to sort by, you need a pointer-to-member, not a pointer; something like:

void quicksort(point * arr, int point::*member, int left, int right){ // test points with // if (arr[i].*member < arr[j].*member) {/* i sorts before j */} } quicksort(arr, &point::x, 0, n-1); 

More generically, you could follow the example of std::sort and accept any comparison functor:

template <typename RandIter, typename Compare> void quicksort(RandIter begin, RandIter end, Compare compare) { // test points with // if (compare(*it1, *it2)) {/* *it1 sorts before *it2 */} } quicksort(arr, arr+n, [](point const &lhs, point const &rhs) {return lhs.x < rhs.x;}); 

And of course, unless you're learning how to implement a sorting algorithm, just use std::sort.

Sign up to request clarification or add additional context in comments.

5 Comments

It may also be beneficial to implement an operator< for point.
@greyfade: If you're using std::sort or a comparator that defaults to std::less, and you always want the same comparison, and you don't mind a (possibly misleading) meaning of < to be defined in other contexts, then maybe.
Thanks a lot man! You just saved me of a lot of pain)) as soon as I gain 15 reputation I will vote up for this answer. This helped me a lot! :)
Compare(*it1, *it2) would create the function object. I'm not sure this is allowed for a lambda. Maybe use a parameter name Compare c and use this object c(*it1, *it2)?
@DyP: You're right, I wasn't thinking properly when I wrote that. Fixed now.
0
quicksort(arr,0,n-1); 

then within quicksort, try to compare the arr[i].x

Comments

0

There are a few problems with your code.
1. quicksort accepts int* but you try to pass int value x
2. You try to pass int but you actually call an undefined variable arr.x

What you need to do is either call in the form of &arr[i].x, but to accomplish what you want, you probably want to pass the entire struct as a pointer.

Comments

0

You need to pass arr as the parameter, as that is the array to be sorted. arr.x is meaningless. You are not passing the string "arr.x" as a parameter which can somehow be interpreted as meaning sort on the x field - when the compiler sees this, it is looking for an x element of arr, which doesn't exist, as the error message suggests - only the elements of arr (e.g. arr[0]) have x elements (accessed as arr[0].x).

Comments

0

Assuming this is for academic purposes (why else would you declare your own sorting algorithm instead of using one of the ones already implemented with a custom comparator?), you can do this a few ways:

Array

std::array<point, 10> myArray; // declares an array of size 10 for points template<size_t N> void quicksort(std::array<point, N>& arr, ...) { // implement sort operating on arr } 

Vector

std::vector<point> myVector; // declares a dynamic array/vector of points void quicksort(std::vector<point>& arr, ...) { // implement sort operating on arr } 

If for some god-awful reason, you want to keep it in C:

Legacy

const size_t SIZE = 10; point arr[SIZE]; // declare an array of 10 points void quicksort(point* p, const size_t n, ...) { // implement sort operating on elements in p passing in SIZE for n } 

Comments

0

I'd rather defined the function as:

 void quicksort(void *a,int left,int right, size_t size, int (*fp)(void*,void*)); 

size is the size of one element of array and fp is a compare function which returns true if the two arguments are equal. Now you can pass the call the function as:

quicksort(arr,0,n-1,sizeof(arr)/sizeof(arr[0]), compare); 

where function compare is something like:

int compare(void* a, void* b) { return *((int*)a) >= *((int*)b); } 

Rest of the implementation of function is trivial I think.

1 Comment

my approach is too C'ish. Pardon me for that.
0

(almost) never try to fool the system by passing a pointer to a member when you really want to pass a pointer to an object. Do as Grijesh suggested. Passing a member can lead to horrible side effects. For example, quicksort is going to sort all the integers together, regardless of which of them are X's and which are Y's. In milder cases you may get wrong compare criteria, and often hard to debug effects such as incorrect pointer optimization. Just be honest with the compiler and pass the object pointer if you need to pass an object pointer. There are very very very few exceptions, mostly to do with low-level system programming where the "other side' of the function call won't be able to handle the object.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.