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

# qsort

 P: n/a I'm trying to figure out qsort(). I haven't seen any practical examples, only synopsis. In the code below, the array is not sorted. Can someone give me some help? #include #include int compare(const void* a, const void* b); int main(void) { int idx; int array[] = {243, 12, 99, 106, 122, 77, 242}; qsort(array, 7, 4, &compare); for(idx=0; idx<7; ++idx) printf("%d\t", array[idx]); printf("\n"); return 0; } int compare(const void* a, const void* b) { if(a < b) return -1; if(a == b) return 0; if(a > b) return 1; } Nov 14 '05 #1
32 Replies

 P: n/a John Smith wrote: I'm trying to figure out qsort(). I haven't seen any practical examples, only synopsis. In the code below, the array is not sorted. Can someone give me some help? #include #include int compare(const void* a, const void* b); int main(void) { int idx; int array[] = {243, 12, 99, 106, 122, 77, 242}; qsort(array, 7, 4, &compare); The `&' is harmless, but unnecessary. The `4' may be true for your C implementation, but is not universal: each C implementation chooses its own "best" size for `int', and different implementations choose differently. For portability, write `sizeof array[0]' instead. for(idx=0; idx<7; ++idx) printf("%d\t", array[idx]); printf("\n"); return 0; } int compare(const void* a, const void* b) { if(a < b) return -1; if(a == b) return 0; if(a > b) return 1; } Here's your difficulty. The comparison function's arguments are not two array elements, but pointers to two array elements. You are comparing the pointers, but you want to compare the pointed-to objects. Here is one way to do it: int compare(const void *a, const void *b) { int u = *(const int*)a; int v = *(const int*)b; if (u < v) ... -- Er*********@sun.com Nov 14 '05 #2

 P: n/a Quoth John Smith on or about 2004-11-17: if(a < b) return -1; if(a == b) return 0; if(a > b) return 1; First of all, shouldn't these be dereferenced? Nov 14 '05 #3

 P: n/a John Smith wrote: I'm trying to figure out qsort(). I haven't seen any practical examples, only synopsis. In the code below, the array is not sorted. Can someone give me some help? #include #include int compare(const void* a, const void* b); int main(void) { int idx; int array[] = {243, 12, 99, 106, 122, 77, 242}; qsort(array, 7, 4, &compare); for(idx=0; idx<7; ++idx) printf("%d\t", array[idx]); printf("\n"); return 0; } int compare(const void* a, const void* b) { if(a < b) return -1; if(a == b) return 0; if(a > b) return 1; } Inside your 'compare' implementation you are comparing pointers instead of comparing the values pointed by those pointers. You are supposed to do the latter, not the former. For example, you can do it as follows int compare(const void* a, const void* b) { int ia = *(const int*) a; int ib = *(const int*) b; return (ia > ib) - (ia < ib); } Also, it makes more sense to form arguments of 'qsort' by using 'sizeof', instead of specifying concrete values explicitly qsort(array, sizeof array / sizeof *array, sizeof *array, &compare); -- Best regards, Andrey Tarasevich Nov 14 '05 #4

 P: n/a John Smith wrote: I'm trying to figure out qsort(). I haven't seen any practical examples, only synopsis. In the code below, the array is not sorted. Can someone give me some help? #include #include int compare(const void* a, const void* b); int main(void) { int idx; int array[] = {243, 12, 99, 106, 122, 77, 242}; qsort(array, 7, 4, &compare); for(idx=0; idx<7; ++idx) printf("%d\t", array[idx]); printf("\n"); return 0; } int compare(const void* a, const void* b) { if(a < b) return -1; if(a == b) return 0; if(a > b) return 1; } #include #include #define NELM (sizeof array / sizeof *array) int compare(const void* a, const void* b); int main(void) { int idx; int array[] = {243, 12, 99, 106, 122, 77, 242}; qsort(array, NELM, sizeof *array, compare); for (idx = 0; idx < NELM; ++idx) { printf("%d\t", array[idx]); } putchar('\n'); return 0; } int compare(const void* a, const void* b) { const int aa = *(int*)a; const int bb = *(int*)b; return bb > aa ? -1 : aa > bb; } -- pete Nov 14 '05 #5

 P: n/a pete wrote: [snip] int compare(const void* a, const void* b) { const int aa = *(int*)a; should be: const int aa = *(const int *)a; const int bb = *(int*)b; return bb > aa ? -1 : aa > bb; return aa - bb; would be the usual idiom. } Nov 14 '05 #6

 P: n/a Robert Harris wrote: pete wrote: [snip] int compare(const void* a, const void* b) { const int aa = *(int*)a; should be: const int aa = *(const int *)a; It makes no difference. You wind up with const int aa, either way. const int bb = *(int*)b; return bb > aa ? -1 : aa > bb; return aa - bb; would be the usual idiom. (aa - bb) is entirely unacceptable as a generic compar function expression. If aa equals INT_MAX and bb equals -1, then you have undefined behavior. } -- pete Nov 14 '05 #7

 P: n/a "John Smith" wrote in message news:5qNmd.252445\$%k.66766@pd7tw2no... I'm trying to figure out qsort(). I haven't seen any practical examples, only synopsis. In the code below, the array is not sorted. Can someone give me some help? int compare(const void* a, const void* b) { if(a < b) return -1; if(a == b) return 0; if(a > b) return 1; } The compare function is incorrect. Other replies have given correct alternatives. Here is my question : What is the semantics of comparing void* for anything but equality ? It is non standard to subtract void pointers (but a dubious gcc extension) What about comparison ? Is it also an extension or is it defined in the standard ? Chqrlie. Nov 14 '05 #8

 P: n/a Charlie Gordon wrote: "John Smith" wrote in message news:5qNmd.252445\$%k.66766@pd7tw2no...int compare(const void* a, const void* b){ if(a < b) return -1; if(a == b) return 0; if(a > b) return 1;} The compare function is incorrect. Other replies have given correct alternatives. Here is my question : What is the semantics of comparing void* for anything but equality ? It is non standard to subtract void pointers (but a dubious gcc extension) What about comparison ? Is it also an extension or is it defined in the standard ? The comparison is well-defined (as I learned to my surprise not long ago) under the usual condition that the two pointers point to or just after the same array. qsort() guarantees this (although bsearch() obviously does not), so the comparison is valid. However, the fact that the comparison is valid doesn't imply that it's usable by qsort()! The compare() function must define a consistent ordering, even while qsort() is busy rearranging the array. If the compare() function's result changes as the items are shuffled about, the ordering is inconsistent and qsort()'s behavior is undefined. Various people have run afoul of this by trying to compare the pointers to equal elements in an attempt to achieve a stable sort, e.g. int compare(const void *p, const void *q) { int a = *(const int*)p; int b = *(const int*)q; if (a < b) return -1; if (a > b) return +1; /* Equal elements; try for stability */ if (p < q) return -1; if (p > q) return +1; return 0; /* stupid qsort()! */ } is wrong, R-O-N-G, wrong. The outcome of comparing two equal integers would depend on their relative locations in the array, and these locations can change as qsort() does its work. -- Er*********@sun.com Nov 14 '05 #9

 P: n/a Robert Harris wrote: ... int compare(const void* a, const void* b) { const int aa = *(int*)a; should be: const int aa = *(const int *)a; const int bb = *(int*)b; return bb > aa ? -1 : aa > bb; return aa - bb; would be the usual idiom. The usual idiom would be return (aa > bb) - (aa < bb); A mere 'aa - bb' can produce signed overflow, which makes it entirely useless. -- Best regards, Andrey Tarasevich Nov 14 '05 #10

 P: n/a On Thu, 18 Nov 2004 12:18:56 +0000, pete wrote: Robert Harris wrote: pete wrote: > [snip] > int compare(const void* a, const void* b) > { > const int aa = *(int*)a; should be: const int aa = *(const int *)a; It makes no difference. You wind up with const int aa, either way. True the int* cast is correct, but not casting away const is better style. Reasonable compiler often will issue a warning about that or can be made to, and it is a good warning to turn on. Lawrence Nov 14 '05 #11

 P: n/a On Thu, 18 Nov 2004 10:58:06 -0500, Eric Sosman wrote: .... The comparison is well-defined (as I learned to my surprise not long ago) under the usual condition that the two pointers point to or just after the same array. qsort() guarantees this I don't see anything in the description of qsort() that guarantees this. It would be quite reasonable for an implementation for qsort() to copy an element of the array into a local temporary and compare against that. This is a natural thing to do in some sorting algorithms. Lawrence Nov 14 '05 #12

 P: n/a Lawrence Kirby wrote: On Thu, 18 Nov 2004 10:58:06 -0500, Eric Sosman wrote: ... The comparison is well-defined (as I learned to mysurprise not long ago) under the usual condition thatthe two pointers point to or just after the same array.qsort() guarantees this I don't see anything in the description of qsort() that guarantees this. The C89 wording isn't clear, but C99 makes it explicit: 7.20.5 Searching and sorting utilities /2/ The implementation shall ensure that [...] both arguments (when called from qsort), are pointers to elements of the array. [...] -- Er*********@sun.com Nov 14 '05 #13

 P: n/a On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote: Lawrence Kirby wrote: .... I don't see anything in the description of qsort() that guarantees this. The C89 wording isn't clear, but C99 makes it explicit: 7.20.5 Searching and sorting utilities /2/ The implementation shall ensure that [...] both arguments (when called from qsort), are pointers to elements of the array. [...] OK, it is required in C99. Very strange though, it potentially reduces the efficiency of the implementation for no obvious benefit. Lawrence Nov 14 '05 #14

 P: n/a Lawrence Kirby wrote: On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote: Lawrence Kirby wrote: ... I don't see anything in the description of qsort() that guarantees this. The C89 wording isn't clear, but C99 makes it explicit: 7.20.5 Searching and sorting utilities /2/ The implementation shall ensure that [...] both arguments (when called from qsort), are pointers to elements of the array. [...] OK, it is required in C99. Very strange though, it potentially reduces the efficiency of the implementation for no obvious benefit. I must be misunderstanding what you're saying. I don't see how you can write a compar function without knowing that the arguments are pointers to array elements. Is this the same thing as what you're talking about? My C89 last draft has: 4.10.5.2 The qsort function The contents of the array are sorted in ascending order according to a comparison function pointed to by compar , which is called with two arguments that point to the objects being compared. -- pete Nov 14 '05 #15

 P: n/a pete wrote: Lawrence Kirby wrote:On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:Lawrence Kirby wrote:...I don't see anything in the description of qsort()that guarantees this. The C89 wording isn't clear, but C99 makes it explicit: 7.20.5 Searching and sorting utilities /2/ The implementation shall ensure that [...] both arguments (when called from qsort), are pointers to elements of the array. [...]OK, it is required in C99.Very strange though, it potentially reduces theefficiency of the implementation for no obvious benefit. Umh, I cannot think of a situation where you cannot make do with pointers to array elements -- the information is hidden behind void *, so I fail to see the restriction. One possible benefit could be that for keys giving the same value, you want to keep the order in which the respective objects (and thus the pointers) were stored. This could of course be done by extending the key but maybe is not possible in a straightforward way. If we are looking at the same array, the pointers can be compared whereas this is not possible if we memcpy() one of the objects. I must be misunderstanding what you're saying. I don't see how you can write a compar function without knowing that the arguments are pointers to array elements. Is this the same thing as what you're talking about? My C89 last draft has: 4.10.5.2 The qsort function The contents of the array are sorted in ascending order according to a comparison function pointed to by compar , which is called with two arguments that point to the objects being compared. The thing is that in C89, I could memcpy() one array element and pass a pointer to it to the function pointed to by compar, whereas in the C99 version this is forbidden. Cheers Michael -- E-Mail: Mine is a gmx dot de address. Nov 14 '05 #16

 P: n/a Michael Mair wrote: pete wrote: Lawrence Kirby wrote:On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote: Lawrence Kirby wrote:... >I don't see anything in the description of qsort()>that guarantees this. The C89 wording isn't clear, but C99 makes it explicit: 7.20.5 Searching and sorting utilities /2/ The implementation shall ensure that [...] both arguments (when called from qsort), are pointers to elements of the array. [...]OK, it is required in C99.Very strange though, it potentially reduces theefficiency of the implementation for no obvious benefit. Umh, I cannot think of a situation where you cannot make do with pointers to array elements -- the information is hidden behind void *, so I fail to see the restriction. One possible benefit could be that for keys giving the same value, you want to keep the order in which the respective objects (and thus the pointers) were stored. This could of course be done by extending the key but maybe is not possible in a straightforward way. If we are looking at the same array, the pointers can be compared whereas this is not possible if we memcpy() one of the objects. I must be misunderstanding what you're saying. I don't see how you can write a compar function without knowing that the arguments are pointers to array elements. Is this the same thing as what you're talking about? My C89 last draft has: 4.10.5.2 The qsort function The contents of the array are sorted in ascending order according to a comparison function pointed to by compar , which is called with two arguments that point to the objects being compared. The thing is that in C89, I could memcpy() one array element and pass a pointer to it to the function pointed to by compar, whereas in the C99 version this is forbidden. Thank you. -- pete Nov 14 '05 #17

 P: n/a On Fri, 19 Nov 2004 14:22:07 +0100, Michael Mair wrote: pete wrote: Lawrence Kirby wrote:On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote: Lawrence Kirby wrote:... >I don't see anything in the description of qsort()>that guarantees this. The C89 wording isn't clear, but C99 makes it explicit: 7.20.5 Searching and sorting utilities /2/ The implementation shall ensure that [...] both arguments (when called from qsort), are pointers to elements of the array. [...]OK, it is required in C99.Very strange though, it potentially reduces theefficiency of the implementation for no obvious benefit. Umh, I cannot think of a situation where you cannot make do with pointers to array elements -- the information is hidden behind void *, so I fail to see the restriction. A simple example is an insertion sort. A basic implementation compares adjacent elements. If they are out of order it swaps them and moves on. Essentially one element moves along the array until it is in its correct place. An optimisation of this is to copy that element to a temporary variable and compare that against array elements, move them when out of order and finally write your temporary back to the free slot in the array when you find the right position. Esssentially you can optimise a lot of swap operations into moves. With the requirements of C99 the element must stay in the array for the purposes of comparison so this optimisation is no longer possible. You can "make do" but what is the benefit of potentially cripping the efficiency of the qsort() implementation? One possible benefit could be that for keys giving the same value, you want to keep the order in which the respective objects (and thus the pointers) were stored. This could of course be done by extending the key but maybe is not possible in a straightforward way. If we are looking at the same array, the pointers can be compared whereas this is not possible if we memcpy() one of the objects. Comparing addresses does *not* make a sort stable, because during the sort process the position of elements varies and not necessarily in a consistent way (think for example of the partitioning process that Quicksort uses). Indeed ANY test of relative addresses that can affect the result of the comparison function will guarantee that the function no longer generates a consistent ordering relation. So there is no value in supporting relative pointer comparisons. I must be misunderstanding what you're saying. I don't see how you can write a compar function without knowing that the arguments are pointers to array elements. When comparing 2 elements all you need is access to the values of those elements, whether they are part of the same array or not is not useful or relevant information. Is this the same thing as what you're talking about? My C89 last draft has: 4.10.5.2 The qsort function The contents of the array are sorted in ascending order according to a comparison function pointed to by compar , which is called with two arguments that point to the objects being compared. The thing is that in C89, I could memcpy() one array element and pass a pointer to it to the function pointed to by compar, whereas in the C99 version this is forbidden. Yes, that's the problem, C99 appears to have invented a pointless and counterproductive restriction. Lawrence Nov 14 '05 #18

 P: n/a Lawrence Kirby wrote: On Fri, 19 Nov 2004 14:22:07 +0100, Michael Mair wrote:pete wrote:Lawrence Kirby wrote:On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:>Lawrence Kirby wrote:>>I don't see anything in the description of qsort()>>that guarantees this.>> The C89 wording isn't clear, but C99 makes it explicit:>> 7.20.5 Searching and sorting utilities> /2/ The implementation shall ensure that [...] both> arguments (when called from qsort), are pointers to> elements of the array. [...]OK, it is required in C99.Very strange though, it potentially reduces theefficiency of the implementation for no obvious benefit.Umh, I cannot think of a situation where you cannot make dowith pointers to array elements -- the information is hiddenbehind void *, so I fail to see the restriction. A simple example is an insertion sort. A basic implementation compares adjacent elements. If they are out of order it swaps them and moves on. Essentially one element moves along the array until it is in its correct place. An optimisation of this is to copy that element to a temporary variable and compare that against array elements, move them when out of order and finally write your temporary back to the free slot in the array when you find the right position. Esssentially you can optimise a lot of swap operations into moves. With the requirements of C99 the element must stay in the array for the purposes of comparison so this optimisation is no longer possible. You can "make do" but what is the benefit of potentially cripping the efficiency of the qsort() implementation? Okay, so we essentially have to switch from a few memcpy()s to one memmove(). For small partitions left by a quicksort or a "nearly" sorted array, we probably will lose something. I guess Shell sort would be even more pathological as you cannot use one memmove but would have to first find out where everything goes and then loop again to do the memcpy()s. Thank you for explaining. One possible benefit could be that for keys giving the samevalue, you want to keep the order in which the respectiveobjects (and thus the pointers) were stored.This could of course be done by extending the key but maybeis not possible in a straightforward way. If we are lookingat the same array, the pointers can be compared whereas thisis not possible if we memcpy() one of the objects. Comparing addresses does *not* make a sort stable, because during the sort process the position of elements varies and not necessarily in a consistent way (think for example of the partitioning process that Quicksort uses). Indeed ANY test of relative addresses that can affect the result of the comparison function will guarantee that the function no longer generates a consistent ordering relation. So there is no value in supporting relative pointer comparisons. Er, perhaps I am slow on the uptake but IMO a quicksort _can_ keep the previous relative order when partitioning. If I've time today, I will try it out. However, the requirements from the standard are probably not strong enough for that to portably work. Apart from that, I do _not_ want to say that it is a good idea to bring in relative position as sorting criteria. But this is the only "benefit" I could think of. Did the standard people give any rationale as to why they changed the wording? Otherwise this might be a good question for c.s.c. Cheers Michael -- E-Mail: Mine is a gmx dot de address. Nov 14 '05 #19

 P: n/a Michael Mair wrote: Lawrence Kirby wrote: On Fri, 19 Nov 2004 14:22:07 +0100, Michael Mair wrote:pete wrote:Lawrence Kirby wrote:>On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:>>>Lawrence Kirby wrote:>>>>I don't see anything in the description of qsort()>>>that guarantees this.>>>> The C89 wording isn't clear, but C99 makes it explicit:>>>> 7.20.5 Searching and sorting utilities>> /2/ The implementation shall ensure that [...] both>> arguments (when called from qsort), are pointers to>> elements of the array. [...]>>OK, it is required in C99.>Very strange though, it potentially reduces the>efficiency of the implementation for no obvious benefit.Umh, I cannot think of a situation where you cannot make dowith pointers to array elements -- the information is hiddenbehind void *, so I fail to see the restriction. A simple example is an insertion sort. A basic implementation compares adjacent elements. If they are out of order it swaps them and moves on. Essentially one element moves along the array until it is in its correct place. An optimisation of this is to copy that element to a temporary variable and compare that against array elements, move them when out of order and finally write your temporary back to the free slot in the array when you find the right position. Esssentially you can optimise a lot of swap operations into moves. With the requirements of C99 the element must stay in the array for the purposes of comparison so this optimisation is no longer possible. You can "make do" but what is the benefit of potentially cripping the efficiency of the qsort() implementation? Okay, so we essentially have to switch from a few memcpy()s to one memmove(). For small partitions left by a quicksort or a "nearly" sorted array, we probably will lose something. I guess Shell sort would be even more pathological as you cannot use one memmove but would have to first find out where everything goes and then loop again to do the memcpy()s. Shell sort with a temp variable doesn't need any relooping that I'm aware of. e_type is a user defined nonarray type. GT is a user defined "greater than" macro. If e_type were to be an array, then all of the e_type assignments would have to be replaced with memcpy calls. void s3sort(e_type *array, size_t nmemb) { e_type temp, *i, *j, *k, *after; after = array + nmemb; if (nmemb > (size_t)-1 / 3) { nmemb = (size_t)-1 / 3; } do { for (i = array + nmemb; i != after; ++i) { j = i - nmemb; if (GT(j, i)) { k = i; temp = *k; do { *k = *j; k = j; if (nmemb + array > j) { break; } j -= nmemb; } while (GT(j, &temp)); *k = temp; } } nmemb = nmemb != 2 ? 3 * nmemb / 7 : 1; } while (nmemb != 0); } The references to memcpy and memmove suggest that you're talking about writing qsort in C. qsort can't depend on malloc (and friends) to provide the temp object, because malloc may fail with valid arguments, while qsort may not. That means that if qsort is going to use a temp variable, it must have an alternative way if malloc fails. Automatic variables are unsuitable for temp types larger than char, because their alignment requirements may be less than their size, while array elements of the same size may need to be aligned at their full size. One possible benefit could be that for keys giving the samevalue, you want to keep the order in which the respectiveobjects (and thus the pointers) were stored.This could of course be done by extending the key but maybeis not possible in a straightforward way. If we are lookingat the same array, the pointers can be compared whereas thisis not possible if we memcpy() one of the objects. Er, perhaps I am slow on the uptake but IMO a quicksort _can_ keep the previous relative order when partitioning. If I've time today, I will try it out. Any array sorting algorithm that compares and swaps nonadjacent elements, like quicksort does, is going to have a very hard time being made stable, if stable sorting is what you're talking about. -- pete Nov 14 '05 #20

 P: n/a Lawrence Kirby wrote:pete wrote:Umh, I cannot think of a situation where you cannot make dowith pointers to array elements -- the information is hiddenbehind void *, so I fail to see the restriction. A simple example is an insertion sort. A basic implementation compares adjacent elements. If they are out of order it swaps them and moves on. Essentially one element moves along the array until it is in its correct place. An optimisation of this is to copy that element to a temporary variable and compare that against array elements, move them when out of order and finally write your temporary back to the free slot in the array when you find the right position. Esssentially you can optimise a lot of swap operations into moves. With the requirements of C99 the element must stay in the array for the purposes of comparison so this optimisation is no longer possible. You can "make do" but what is the benefit of potentially cripping the efficiency of the qsort() implementation? Leave the "moving" item in place in the array until you discover its destination, then swap it with its neigbors in one operation. One of Jon Bentley's "Programming Pearls" columns shows a neat way of doing this, or you could use memcpy-memmove-memcpy via a temporary area (note that the restriction applies only when the comparison function is called; the use of non-array memory is permitted at other times during the sort). There's another consideration: How would qsort() acquire sufficient temporary memory to hold a copy of an item of arbitrary size? malloc() is unattractive because it can fail but qsort() cannot. qsort() could, of course, be a wrapper around two implementations, one for use when malloc() succeeds and a fall-back to cope with failure -- but that seems unattractive, since the dynamic memory doesn't seem to add much to the overall efficiency. [...] Yes, that's the problem, C99 appears to have invented a pointless and counterproductive restriction. The restriction doesn't seem counter-productive, but I admit I don't see much point in it. A comparison function might, perhaps, modify the pointed-to elements (in a way that doesn't affect the computed result, of course, and after casting away the `const'-ness), and such modifications would be problematic if two versions of "the same" element could co-exist simultaneously. But why would a comparison function want to do such a thing? I remain baffled. -- Er*********@sun.com Nov 14 '05 #21

 P: n/a pete wrote: Michael Mair wrote:Lawrence Kirby wrote:On Fri, 19 Nov 2004 14:22:07 +0100, Michael Mair wrote:pete wrote: >Lawrence Kirby wrote:>>>>On Thu, 18 Nov 2004 13:29:38 -0500, Eric Sosman wrote:>>>>>>>Lawrence Kirby wrote:>>>>>>I don't see anything in the description of qsort()>>>>that guarantees this.>>>>>> The C89 wording isn't clear, but C99 makes it explicit:>>>>>> 7.20.5 Searching and sorting utilities>>> /2/ The implementation shall ensure that [...] both>>> arguments (when called from qsort), are pointers to>>> elements of the array. [...]>>>>OK, it is required in C99.>>Very strange though, it potentially reduces the>>efficiency of the implementation for no obvious benefit.Umh, I cannot think of a situation where you cannot make dowith pointers to array elements -- the information is hiddenbehind void *, so I fail to see the restriction.A simple example is an insertion sort. A basic implementationcompares adjacent elements. If they are out of order it swapsthem and moves on. Essentially one element moves alongthe array until it is in its correct place.An optimisation of this is to copy that element to atemporary variable and compare that against array elements,move them when out of order and finally write your temporaryback to the free slot in thearray when you find the right position.Esssentially you can optimise a lot of swap operations into moves.With the requirements of C99 theelement must stay in the array for the purposes of comparisonso this optimisation is no longer possible.You can "make do" but what is thebenefit of potentially cripping the efficiency of the qsort()implementation?Okay, so we essentially have to switch from a few memcpy()s toone memmove(). For small partitions left by a quicksort or a"nearly" sorted array, we probably will lose something.I guess Shell sort would be even more pathological as you cannotuse one memmove but would have to first find out where everythinggoes and then loop again to do the memcpy()s. Shell sort with a temp variable doesn't need any relooping that I'm aware of. We are still in the setting that you *must* *not* use the temporary variable for comparing -- this is the whole point. If we may use it, of course no relooping is necessary. But the requirement that both arguments passed to compar are pointers to objects residing _inside_ the array (which is what we are talking about) effectively makes it impossible to avoid swapping the "equidistant" non-adjacent elements if not by some type of relooping. Example: We look at the N-distant subsets and are looking for the right position of some element X within its remainder class. We compare X with the elements with index index(X)-i*N. If we use a temporary variable and have to copy an element to a position with higher index, we have to copy the temporary object into the "free slot" in order to be able to compare again. With insertion sort, we have N==1. So, we can just find out where exactly X goes, copy it to temp, memmove() the elements in between one element size "up" and insert X which should be cheaper than doing 2*(number of elements to move) memcpy()s. Alternatively, with the information available, we could just replace the memmove() by (number of elements to move)+1 memcpy()s. In the non-contiguous setting of Shell sort (N>1), This is exactly what I would do. The relooping probably is cheaper than the additional memcpy() calls. e_type is a user defined nonarray type. GT is a user defined "greater than" macro. If e_type were to be an array, then all of the e_type assignments would have to be replaced with memcpy calls. void s3sort(e_type *array, size_t nmemb) { e_type temp, *i, *j, *k, *after; after = array + nmemb; if (nmemb > (size_t)-1 / 3) { nmemb = (size_t)-1 / 3; } do { for (i = array + nmemb; i != after; ++i) { j = i - nmemb; if (GT(j, i)) { k = i; temp = *k; do { *k = *j; k = j; if (nmemb + array > j) { break; } j -= nmemb; } while (GT(j, &temp)); ^^^^^^^^^^^^ Here goes your approach. *k = temp; } } nmemb = nmemb != 2 ? 3 * nmemb / 7 : 1; } while (nmemb != 0); } I hope I made the problem clearer now. The references to memcpy and memmove suggest that you're talking about writing qsort in C. qsort can't depend on malloc (and friends) to provide the temp object, because malloc may fail with valid arguments, while qsort may not. That means that if qsort is going to use a temp variable, it must have an alternative way if malloc fails. Automatic variables are unsuitable for temp types larger than char, because their alignment requirements may be less than their size, while array elements of the same size may need to be aligned at their full size. This is a problem I silently excluded and would rather see as separate. One possible benefit could be that for keys giving the samevalue, you want to keep the order in which the respectiveobjects (and thus the pointers) were stored.This could of course be done by extending the key but maybeis not possible in a straightforward way. If we are lookingat the same array, the pointers can be compared whereas thisis not possible if we memcpy() one of the objects.Er, perhaps I am slow on the uptake but IMO a quicksort _can_ keepthe previous relative order when partitioning. If I've time today, Iwill try it out. Any array sorting algorithm that compares and swaps nonadjacent elements, like quicksort does, is going to have a very hard time being made stable, if stable sorting is what you're talking about. Yep, that is what I was talking about -- I was unaware of the term "stable sorting", so I only now found out that this is what I wanted to say... Cheers Michael -- E-Mail: Mine is a gmx dot de address. Nov 14 '05 #22

 P: n/a Eric Sosman wrote: Lawrence Kirby wrote:pete wrote:Umh, I cannot think of a situation where you cannot make dowith pointers to array elements -- the information is hiddenbehind void *, so I fail to see the restriction.A simple example is an insertion sort. A basic implementationcompares adjacent elements. If they are out of order it swaps them andmoves on. Essentially one element moves along the array until it is in itscorrect place. An optimisation of this is to copy that element to atemporary variable and compare that against array elements, move them whenout of order and finally write your temporary back to the free slot in thearray when you find the right position. Esssentially you can optimise alot of swap operations into moves. With the requirements of C99 theelement must stay in the array for the purposes of comparison so thisoptimisation is no longer possible. You can "make do" but what is thebenefit of potentially cripping the efficiency of the qsort()implementation? Leave the "moving" item in place in the array until you discover its destination, then swap it with its neigbors in one operation. One of Jon Bentley's "Programming Pearls" columns shows a neat way of doing this, or you could use memcpy-memmove-memcpy via a temporary area (note that the restriction applies only when the comparison function is called; the use of non-array memory is permitted at other times during the sort). Do you remember which column? I did not want to go through all the material of the 2nd Edition as it is on the web and could not find the specific one googling. There's another consideration: How would qsort() acquire sufficient temporary memory to hold a copy of an item of arbitrary size? malloc() is unattractive because it can fail but qsort() cannot. qsort() could, of course, be a wrapper around two implementations, one for use when malloc() succeeds and a fall-back to cope with failure -- but that seems unattractive, since the dynamic memory doesn't seem to add much to the overall efficiency. How would you do that in a portable way? My first thought was bytewise XORing for swapping two elements but this usually is the worst way to do it... However, without having any kind of dynamic memory allocation the only other thing is having a (medium-sized) fixed temp-array and memcpy()ing and memmove()ing junks of at most the size of that array. Sounds unattractive, too. [...]Yes, that's the problem, C99 appears to have invented a pointless andcounterproductive restriction. The restriction doesn't seem counter-productive, but I admit I don't see much point in it. A comparison function might, perhaps, modify the pointed-to elements (in a way that doesn't affect the computed result, of course, and after casting away the `const'-ness), and such modifications would be problematic if two versions of "the same" element could co-exist simultaneously. But why would a comparison function want to do such a thing? I remain baffled. Perhaps a pet algorithm of someone. As I wondered aloud elsewhere: Does anyone know a reason for this? I think the example of an underlying Shell sort shows that you would have to change qsort() implementation to one with more cost -- which is really unnecessary. Cheers Michael -- E-Mail: Mine is a gmx dot de address. Nov 14 '05 #23

 P: n/a Michael Mair wrote: Eric Sosman wrote: Leave the "moving" item in place in the array until youdiscover its destination, then swap it with its neigbors inone operation. One of Jon Bentley's "Programming Pearls"columns shows a neat way of doing this, or you could usememcpy-memmove-memcpy via a temporary area (note that therestriction applies only when the comparison function iscalled; the use of non-array memory is permitted at othertimes during the sort). Do you remember which column? I did not want to go through all the material of the 2nd Edition as it is on the web and could not find the specific one googling. I don't recall the column, but I do recall the method. The challenge is to exchange two adjacent regions of an array, when the two regions may not be the same size: abcRSTUVWXYZ -> RSTUVWXYZabc In the insertion-sort context, "abc" has been determined to belong just after its neighbors "RSTUVWXYZ," and the challenge is to get it there. With a temporary area big enough for "abc" this is simple: memcpy() "abc" to the temporary, slide the rest leftward with memmove(), and them memcpy() the temporary to the right-hand end. You could even make do with a smaller temporary area by using multiple "rotations:" abcRSTUVWXYZ -> bcRSTUVWXYZa -> cRSTUVWXYZab -> RSTUVWXYZabc This is unattractive, though, because it copies all the data multiple times. Bentley tells the sad tale of many programmers who tried to make the exchange efficiently but using only a fixed amount of temporary space. The efforts, he said, were discouraging: horribly complex code with a tendency to fall over and die when confronted by edge cases. Look what happens, though, if you reverse the array in place, byte-for-byte (or element-for-element): abcRSTUVWXYZ -> ZYXWVUTSRcba The two segments are now in the proper positions, but each segment has been reversed. Correct this by reversing each segment individually: ZYXWVUTSRcba -> RSTUVWXYZcba ^^^^^^^^^ ^^^^^^^^^ RSTUVWXYZcba -> RSTUVWXYZabc ^^^ ^^^ .... and the job is complete. "But what about efficiency? Surely there's a better way than moving every byte twice!" Bentley thinks not, based on observation of the complicated but "efficient" codes. Compilers can easily unroll and otherwise optimize the simple loop of an in-place reversal, but the more complicated codes didn't lend themselves to optimization: too many decisions, too many branches, and so on. Not only was the "inefficient" method easy to write and easy to verify, but it actually turned out to be faster than the (often bug-ridden) "efficient" methods. If sufficient temporary space is available, I think the memcpy/memmove/memcpy method is probably best. But if you've only got a fixed amount of extra space and it isn't quite big enough, the three-rotation method has much to recommend it. -- Er*********@sun.com Nov 14 '05 #24

 P: n/a Eric Sosman wrote: Michael Mair wrote:Eric Sosman wrote: Leave the "moving" item in place in the array until youdiscover its destination, then swap it with its neigbors inone operation. One of Jon Bentley's "Programming Pearls"columns shows a neat way of doing this, or you could usememcpy-memmove-memcpy via a temporary area (note that therestriction applies only when the comparison function iscalled; the use of non-array memory is permitted at othertimes during the sort).Do you remember which column? I did not want to go through allthe material of the 2nd Edition as it is on the web and couldnot find the specific one googling. I don't recall the column, but I do recall the method. The challenge is to exchange two adjacent regions of an array, when the two regions may not be the same size: abcRSTUVWXYZ -> RSTUVWXYZabc In the insertion-sort context, "abc" has been determined to belong just after its neighbors "RSTUVWXYZ," and the challenge is to get it there. With a temporary area big enough for "abc" this is simple: memcpy() "abc" to the temporary, slide the rest leftward with memmove(), and them memcpy() the temporary to the right-hand end. You could even make do with a smaller temporary area by using multiple "rotations:" abcRSTUVWXYZ -> bcRSTUVWXYZa -> cRSTUVWXYZab -> RSTUVWXYZabc This is unattractive, though, because it copies all the data multiple times. Bentley tells the sad tale of many programmers who tried to make the exchange efficiently but using only a fixed amount of temporary space. The efforts, he said, were discouraging: horribly complex code with a tendency to fall over and die when confronted by edge cases. Look what happens, though, if you reverse the array in place, byte-for-byte (or element-for-element): abcRSTUVWXYZ -> ZYXWVUTSRcba The two segments are now in the proper positions, but each segment has been reversed. Correct this by reversing each segment individually: ZYXWVUTSRcba -> RSTUVWXYZcba ^^^^^^^^^ ^^^^^^^^^ RSTUVWXYZcba -> RSTUVWXYZabc ^^^ ^^^ ... and the job is complete. "But what about efficiency? Surely there's a better way than moving every byte twice!" Bentley thinks not, based on observation of the complicated but "efficient" codes. Compilers can easily unroll and otherwise optimize the simple loop of an in-place reversal, but the more complicated codes didn't lend themselves to optimization: too many decisions, too many branches, and so on. Not only was the "inefficient" method easy to write and easy to verify, but it actually turned out to be faster than the (often bug-ridden) "efficient" methods. If sufficient temporary space is available, I think the memcpy/memmove/memcpy method is probably best. But if you've only got a fixed amount of extra space and it isn't quite big enough, the three-rotation method has much to recommend it. Thank you :-))) -Michael -- E-Mail: Mine is an /at/ gmx /dot/ de address. Nov 14 '05 #25

 P: n/a > > [...] Yes, that's the problem, C99 appears to have invented a pointless and counterproductive restriction. The restriction doesn't seem counter-productive, but I admit I don't see much point in it. A comparison function might, perhaps, modify the pointed-to elements (in a way that doesn't affect the computed result, of course, and after casting away the `const'-ness), and such modifications would be problematic if two versions of "the same" element could co-exist simultaneously. But why would a comparison function want to do such a thing? I remain baffled. Such a function could do this for statistical purposes. Another possibility is that the comparison could require acquiring external resources to which a handle may need to be stored in the object. Some other cacheing mechanism might entail modifying the compared objects... Modifying the objects during the comparison violates the prototype for the comparison function where the parameters are defined as const void *, so this was probably not the intent of the standard, thus not the reason for the restriction. I am more inclined to assume that specific alignment constraints unknown to qsort(), and not necessarily matched by malloc(), make it a good reason to enforce that the objects always be array elements at comparison time. Chqrlie. Nov 14 '05 #26

 P: n/a On Fri, 19 Nov 2004 16:13:08 +0000, pete wrote: .... The references to memcpy and memmove suggest that you're talking about writing qsort in C. qsort can't depend on malloc (and friends) to provide the temp object, Certainly it can. because malloc may fail with valid arguments, while qsort may not. That means that if qsort is going to use a temp variable, it must have an alternative way if malloc fails. That's one solution to the problem. But consider that failing due to lack of resources could in principle happen to ANY standard library function, or indeed any user-defined function. If the C standard forbade such failure the language would be to all intents and purposes unimplementable. qsort() doesn't have a way to flag a failure to complete the sort to the caller, so in such circumstances it can't return. It CAN cause the program execution to terminate abnormally, e.g. by calling abort(). This isn't really any different to a program "crashing" at any point due to lack of stack space (on relevant stack based implementations). Automatic variables are unsuitable for temp types larger than char, because their alignment requirements may be less than their size, while array elements of the same size may need to be aligned at their full size. However qsort() is part of the implementation so it can be written with knowledge of implementation alignment characteristics, in the same way that malloc() can. Of course allocation failure is a possibility here too. Lawrence Nov 14 '05 #27

 P: n/a Lawrence Kirby wrote: On Fri, 19 Nov 2004 16:13:08 +0000, pete wrote: ... The references to memcpy and memmove suggest that you're talking about writing qsort in C. qsort can't depend on malloc (and friends) to provide the temp object, Certainly it can. because malloc may fail with valid arguments, while qsort may not. That means that if qsort is going to use a temp variable, it must have an alternative way if malloc fails. That's one solution to the problem. But consider that failing due to lack of resources could in principle happen to ANY standard library function, or indeed any user-defined function. If the C standard forbade such failure the language would be to all intents and purposes unimplementable. If an implementation cannot translate and execute a program like the one described in N869 5.2.4.1, [#1], then it is not a conforming implementation. qsort() doesn't have a way to flag a failure to complete the sort to the caller, so in such circumstances it can't return. It CAN cause the program execution to terminate abnormally, e.g. by calling abort(). You just made that up. There's nothing in the standard which suggests that qsort can call abort when qsort is called with valid arguments. -- pete Nov 14 '05 #28

 P: n/a On Wed, 01 Dec 2004 14:00:27 +0000, pete wrote: Lawrence Kirby wrote: On Fri, 19 Nov 2004 16:13:08 +0000, pete wrote: ... > The references to memcpy and memmove > suggest that you're talking about writing qsort in C. > qsort can't depend on malloc (and friends) > to provide the temp object, Certainly it can. > because malloc may fail with valid arguments, while qsort may not. > That means that if qsort is going to use a temp variable, > it must have an alternative way if malloc fails. That's one solution to the problem. But consider that failing due to lack of resources could in principle happen to ANY standard library function, or indeed any user-defined function. If the C standard forbade such failure the language would be to all intents and purposes unimplementable. If an implementation cannot translate and execute a program like the one described in N869 5.2.4.1, [#1], then it is not a conforming implementation. But it is up to the implementation to choose the program. It will clearly choose a program that it can translate and execute. This does not require it to be able to translate and execute successfully any other program. The compiler could be written to recognise this program specifically and just generate code to produce the correct output. Indeed the program could be designed to produce no output. qsort() doesn't have a way to flag a failure to complete the sort to the caller, so in such circumstances it can't return. It CAN cause the program execution to terminate abnormally, e.g. by calling abort(). You just made that up. There's nothing in the standard which suggests that qsort can call abort when qsort is called with valid arguments. I'll try to be clearer. Any program (except the one designated containing examples of the translation limits) can fail in execution at any point without creating a conformance issue for the implementation. If qsort() is part of the implementation and if it decides it can't complete the operation, it is at perfect liberty to cause the execution of the program to fail. I suggested calling abort() as a means to achieve this. If you don't like that it isn't a problem, it will just have to use some "internal" mechanism, e.g. it could do the equivalent of causing a stack overflow (or whatever makes sense on the implementation). Lawrence Nov 14 '05 #29

 P: n/a Lawrence Kirby wrote: On Wed, 01 Dec 2004 14:00:27 +0000, pete wrote: Lawrence Kirby wrote: On Fri, 19 Nov 2004 16:13:08 +0000, pete wrote: ... > The references to memcpy and memmove > suggest that you're talking about writing qsort in C. > qsort can't depend on malloc (and friends) > to provide the temp object, Certainly it can. > because malloc may fail with valid arguments, > while qsort may not. > That means that if qsort is going to use a temp variable, > it must have an alternative way if malloc fails. That's one solution to the problem. But consider that failing due to lack of resources could in principle happen to ANY standard library function, or indeed any user-defined function. If the C standard forbade such failure the language would be to all intents and purposes unimplementable. If an implementation cannot translate and execute a program like the one described in N869 5.2.4.1, [#1], then it is not a conforming implementation. But it is up to the implementation to choose the program. It will clearly choose a program that it can translate and execute. This does not require it to be able to translate and execute successfully any other program. The compiler could be written to recognise this program specifically and just generate code to produce the correct output. Indeed the program could be designed to produce no output. It has nothing to do with choosing. Anything that can't translate and execute a C program, isn't a C implementation. It's as simple as that. -- pete Nov 14 '05 #30

 P: n/a pete writes: Lawrence Kirby wrote: [...] But it is up to the implementation to choose the program. It will clearly choose a program that it can translate and execute. This does not require it to be able to translate and execute successfully any other program. The compiler could be written to recognise this program specifically and just generate code to produce the correct output. Indeed the program could be designed to produce no output. It has nothing to do with choosing. Anything that can't translate and execute a C program, isn't a C implementation. It's as simple as that. No, it's not as simple as that. The following is a C program. On a system with infinite available memory, it will never terminate. No real system can execute it (unless it optimizes away the recursive calls). static void recurse(void) { char data[1024]; recurse(); recurse(); } int main(void) { recurse(); } This is an extreme case, but all implementations have capacity limitations. -- 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 14 '05 #31

 P: n/a > The following is a C program. On a system with infinite available memory, it will never terminate. No real system can execute it (unless it optimizes away the recursive calls). static void recurse(void) { char data[1024]; recurse(); recurse(); } int main(void) { recurse(); } Well, a clever C compiler might just compile this as a single infinite loop, but I wouldn't count on it. This piece of code will confuse a lot of them as to optimizing. This is an extreme case, but all implementations have capacity limitations. This is an infinite recursion. Therefore, it goes beyond the scope of any programming language except maybe a formal Turing machine. In the real world, infinite recursion makes no sense. Can we really speak of capacity limitations? Yes and no. What is infinite capacity, to begin with? What kind of problem would an infinite recursion be able to solve? And lastly, does infinity really exist? Is our universe finite or infinite? Are we going too far? ;-) Nov 14 '05 #32

 P: n/a Guillaume <"grsNOSPAM at NOTTHATmail dot com"> writes: The following is a C program. On a system with infinite available memory, it will never terminate. No real system can execute it (unless it optimizes away the recursive calls). static void recurse(void) { char data[1024]; recurse(); recurse(); } int main(void) { recurse(); } Well, a clever C compiler might just compile this as a single infinite loop, but I wouldn't count on it. This piece of code will confuse a lot of them as to optimizing. Which is what I meant by "unless it optimizes away the recursive calls". (I should have referred to transforming them into an infinite loop; my wording implied eliminating them altogether, which is of course invalid.) This is an extreme case, but all implementations have capacity limitations. This is an infinite recursion. Therefore, it goes beyond the scope of any programming language except maybe a formal Turing machine. In the real world, infinite recursion makes no sense. Can we really speak of capacity limitations? Yes and no. [snip] I agree with your last statement, except for the "and no" part. All implementations have capacity limitations, some more stringent than others. If a program has, for example, allocated *almost* all the memory available to it, a call to qsort() (or to any function) may fail due to a lack of memory. Since qsort() in particular is likely to be recursive, it's entirely possible for the initial call to qsort() to succeed, but for the program to run out of memory while qsort() is running. There's no mechanism for qsort() to report this (or any other failure) to the caller; aborting the program is probably the most reasonable response. The standard provides a mechanism to report running out of heap (malloc() returning a null pointer), but not to report running out of stack. (The standard doesn't use the terms "heap" and "stack", but you get the idea.) The standard also allows an implementation to be very sloppy about documenting its capacity limitations. Since the amount of memory available to a program can vary randomly depending on the current state of the system, that's probably unavoidable. -- 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 14 '05 #33

### This discussion thread is closed

Replies have been disabled for this discussion.