449,411 Members | 1,022 Online Need help? Post your question and get tips & solutions from a community of 449,411 IT Pros & Developers. It's quick & easy.

# Questions about qsort( ) to sort pointer to struct.

 P: n/a Hi! I have questions about qsort( ). Is anyone be willing to help? I use the following struct: struct Struct_A{ double value; ... } *AA, **pAA; After allocating memory, I have pAA[n], and AA[n]. For all i, 0 <= i < n, pAA[i] = &AA[i] ; I want to retrieve all the AA[i].value's according to the value(decending order). So I want to sort. Instead of sorting the whole AA[n](size_of(struct Struct_A) is very large), I use pAA[i] as a handle and sort pAA[i] according to pAA[i]->value. pAA->value should be the biggest one. I triied: qsort( (void **) pAA, n, sizeof(struct Struct_A * ), comp); and int comp(const void * row1, const void * row2) struct Struct_A * Arow1 = (struct Struct_A *) row1; struct Struct_A * Arow2 = (struct Struct_A *) row2; if ( Arow1->value < Arow2->value) return (1); elseif if if ( Arow1->value > Arow2->value) return (-1); else return(0); } The code can run, but not in the way I need. before sort: pAA->value = 0.688875 pAA->value = 0.580136 pAA->value = 0.379049 pAA->value = 0.606478 pAA->value = 0.742888 pAA->value = 0.908687 pAA->value = 0.969579 after sort pAA->value = 0.969579 pAA->value = 0.908687 pAA->value = 0.742888 pAA->value = 0.606478 pAA->value = 0.688875 pAA->value = 0.379049 pAA->value = 0.580136 and the following one works. int comp(const void * row1, const void * row2) { struct Struct_A * Arow1 = *((struct Struct_A **) row1); struct Struct_A * Arow2 = *((struct Struct_A **) row2); if ( Arow1->value < Arow2->value) return (1); else if ( Arow1->value > Arow2->value) return (-1); else return 0; } Why does "*((struct Struct_A **) row1)" work? but not "(struct Struct_A *) row1"? To me, Both row1 point to the same location "&AA[i]". I am confused why the (struct Struct_A *) row1 version can not lead to the correct result? Is anyone able to use PLAIN English explain what is the difference? and why dose the 2nd can not sort by "value"? A sorting need to swap data. The first one swap pAA[i] and pAA[j] if necessary. What data will the (struct Struct_A *) row1 version indeed swap? Thanks! Nov 14 '05 #1
4 Replies

 P: n/a PCHOME wrote: Hi! I have questions about qsort( ). Is anyone be willing to help? I use the following struct: struct Struct_A{ double value; ... } *AA, **pAA; After allocating memory, I have pAA[n], and AA[n]. For all i, 0 <= i < n, pAA[i] = &AA[i] ; I want to retrieve all the AA[i].value's according to the value(decending order). So I want to sort. Instead of sorting the whole AA[n](size_of(struct Struct_A) is very large), I use pAA[i] as a handle and sort pAA[i] according to pAA[i]->value. pAA->value should be the biggest one. I triied: qsort( (void **) pAA, n, sizeof(struct Struct_A * ), comp); It would be better to use qsort (pAA, n, sizeof *pAA, comp); First, the `(void**)pAA' cast is wrong -- you will get away with it on many machines, but it is wrong nonetheless and there's no benefit in taking unnecessary risks. The correct cast would be `(void*)pAA' but even that much is unnecessary (assuming a prototype for qsort() is in scope, which it certainly should be). In fact, with the prototype the compiler will treat your original as equivalent to `(void*)(void**)pAA'. Second, `sizeof *pAA' is preferable to your original. The original you wrote was correct, but `sizeof *pAA' offers fewer opportunities to make silly errors. The compiler knows what type `pAA' points to; let the compiler do the work of figuring out the size. and int comp(const void * row1, const void * row2) struct Struct_A * Arow1 = (struct Struct_A *) row1; This would be right if you were sorting an array of `struct Struct_A' objects, but you're not: you're sorting an array of pointers to such objects. `row1' does not point to a struct; it points to a pointer to a struct. Here's what you need: struct Struct_A * Arow1 = * (struct Struct_A **)row1; That is: You convert `row1' from `void*' to a pointer to an element of the array. Then since the array element is itself a pointer to the ultimate struct, you apply `*' to the converted array pointer to fetch the struct pointer. Here's a simple rule: The type of the first argument to qsort() is the type to which the comparison function's arguments should be converted, give or take a `const'. [...] and the following one works. int comp(const void * row1, const void * row2) { struct Struct_A * Arow1 = *((struct Struct_A **) row1); Right. The things being sorted are pointers, and comp() receives pointers to two of those things, hence the double `**': comp() receives pointers to pointers. Why does "*((struct Struct_A **) row1)" work? but not "(struct Struct_A *) row1"? To me, Both row1 point to the same location "&AA[i]". No, `row1' points to an element in the `pAA' array and not to a struct at all. The array element points to a struct in the `AA' array, but `row1' does not point there. | | | | +------+ +-------------+ row1 ---> |pAA[i]----> | AA[j] | +------+ +-------------+ | | | | +------+ +-------------+ | | | | (You say that i==j when the sort begins, but that will not remain true when qsort() rearranges the `pAA' array.) -- Er*********@sun.com Nov 14 '05 #2

 P: n/a PCHOME wrote: Hi! I have questions about qsort( ). Is anyone be willing to help? I use the following struct: struct Struct_A{ double value; ... } *AA, **pAA; After allocating memory, I have pAA[n], and AA[n]. For all i, 0 <= i < n, pAA[i] = &AA[i] ; I want to retrieve all the AA[i].value's according to the value(decending order). So I want to sort. Instead of sorting the whole AA[n](size_of(struct Struct_A) is very large), I use pAA[i] as a handle and sort pAA[i] according to pAA[i]->value. pAA->value should be the biggest one. I triied: qsort( (void **) pAA, n, sizeof(struct Struct_A * ), comp); and int comp(const void * row1, const void * row2) struct Struct_A * Arow1 = (struct Struct_A *) row1; struct Struct_A * Arow2 = (struct Struct_A *) row2; if ( Arow1->value < Arow2->value) return (1); elseif if if ( Arow1->value > Arow2->value) return (-1); else return(0); } The code can run, but not in the way I need. before sort: pAA->value = 0.688875 pAA->value = 0.580136 pAA->value = 0.379049 pAA->value = 0.606478 pAA->value = 0.742888 pAA->value = 0.908687 pAA->value = 0.969579 after sort pAA->value = 0.969579 pAA->value = 0.908687 pAA->value = 0.742888 pAA->value = 0.606478 pAA->value = 0.688875 pAA->value = 0.379049 pAA->value = 0.580136 and the following one works. int comp(const void * row1, const void * row2) { struct Struct_A * Arow1 = *((struct Struct_A **) row1); struct Struct_A * Arow2 = *((struct Struct_A **) row2); if ( Arow1->value < Arow2->value) return (1); else if ( Arow1->value > Arow2->value) return (-1); else return 0; } Why does "*((struct Struct_A **) row1)" work? but not "(struct Struct_A *) row1"? To me, Both row1 point to the same location "&AA[i]". I am confused why the (struct Struct_A *) row1 version can not lead to the correct result? Is anyone able to use PLAIN English explain what is the difference? I wish I could. and why dose the 2nd can not sort by "value"? A sorting need to swap data. The first one swap pAA[i] and pAA[j] if necessary. What data will the (struct Struct_A *) row1 version indeed swap? /* BEGIN output new.c */ AA.value is 0.688875 AA.value is 0.580136 AA.value is 0.379049 AA.value is 0.606478 AA.value is 0.742888 AA.value is 0.908687 AA.value is 0.969579 pAA->value is 0.969579 pAA->value is 0.908687 pAA->value is 0.742888 pAA->value is 0.688875 pAA->value is 0.606478 pAA->value is 0.580136 pAA->value is 0.379049 /* END output new.c */ /* BEGIN new.c */ #include #include #define NELEM 7 struct Struct_A { double value; struct Struct_A *next; }; int comp(const void *arg1, const void *arg2); int main(void) { struct Struct_A *AA, **pAA; unsigned index; AA = malloc(NELEM * sizeof *AA); pAA = malloc(NELEM * sizeof *pAA); if (AA == NULL || pAA == NULL) { exit(EXIT_FAILURE); } AA.value = 0.688875; AA.value = 0.580136; AA.value = 0.379049; AA.value = 0.606478; AA.value = 0.742888; AA.value = 0.908687; AA.value = 0.969579; puts("/* BEGIN output new.c */\n"); for (index = 0; index != NELEM; ++index) { pAA[index] = AA + index; printf("AA[%u].value is %f\n", index, AA[index] .value); } putchar('\n'); qsort(pAA, NELEM, sizeof *pAA, comp); for (index = 0; index != NELEM; ++index) { printf("pAA[%u]->value is %f\n", index, pAA[index]->value); } free(AA); free(pAA); puts("\n/* END output new.c */"); return 0; } int comp(const void *arg1, const void *arg2) { double value_1 = (**(struct Struct_A**)arg1).value; double value_2 = (**(struct Struct_A**)arg2).value; return value_1 > value_2 ? -1 : value_1 != value_2; } /* END new.c */ -- pete Nov 14 '05 #3

 P: n/a Nice job! Nov 15 '05 #4

 P: n/a "I_have_nothing" writes: Nice job! What? Don't assume that your readers have access to the article to which you're replying. (It appears to have expired on my server.) If you've been following this newsgroup, you've seen the following many times: If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 15 '05 #5

### This discussion thread is closed

Replies have been disabled for this discussion. 