qsort

Discussion in 'C Programming' started by John Smith, Nov 17, 2004.

  1. John Smith

    John Smith Guest

    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 <stdio.h>
    #include <stdlib.h>
    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;
    }
     
    John Smith, Nov 17, 2004
    #1
    1. Advertising

  2. John Smith

    Eric Sosman Guest

    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 <stdio.h>
    > #include <stdlib.h>
    > 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) ...

    --
     
    Eric Sosman, Nov 17, 2004
    #2
    1. Advertising

  3. John Smith

    Trent Buck Guest

    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?
     
    Trent Buck, Nov 17, 2004
    #3
  4. 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 <stdio.h>
    > #include <stdlib.h>
    > 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
     
    Andrey Tarasevich, Nov 17, 2004
    #4
  5. John Smith

    pete Guest

    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 <stdio.h>
    > #include <stdlib.h>
    > 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 <stdio.h>
    #include <stdlib.h>

    #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
     
    pete, Nov 18, 2004
    #5
  6. 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.
    > }
    >
     
    Robert Harris, Nov 18, 2004
    #6
  7. John Smith

    pete Guest

    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
     
    pete, Nov 18, 2004
    #7
  8. "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.
     
    Charlie Gordon, Nov 18, 2004
    #8
  9. John Smith

    Eric Sosman Guest

    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.

    --
     
    Eric Sosman, Nov 18, 2004
    #9
  10. 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
     
    Andrey Tarasevich, Nov 18, 2004
    #10
  11. 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
     
    Lawrence Kirby, Nov 18, 2004
    #11
  12. 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
     
    Lawrence Kirby, Nov 18, 2004
    #12
  13. John Smith

    Eric Sosman Guest

    Lawrence Kirby wrote:
    > 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.


    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. [...]

    --
     
    Eric Sosman, Nov 18, 2004
    #13
  14. 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
     
    Lawrence Kirby, Nov 19, 2004
    #14
  15. John Smith

    pete Guest

    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
     
    pete, Nov 19, 2004
    #15
  16. John Smith

    Michael Mair Guest

    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 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.
     
    Michael Mair, Nov 19, 2004
    #16
  17. John Smith

    pete Guest

    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 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
     
    pete, Nov 19, 2004
    #17
  18. 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 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
     
    Lawrence Kirby, Nov 19, 2004
    #18
  19. John Smith

    Michael Mair Guest

    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 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?


    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 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.


    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.
     
    Michael Mair, Nov 19, 2004
    #19
  20. John Smith

    pete Guest

    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 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?

    >
    > 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 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.


    > 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
     
    pete, Nov 19, 2004
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. richard

    Re: qsort and structs and ptrs

    richard, Aug 14, 2003, in forum: C Programming
    Replies:
    0
    Views:
    391
    richard
    Aug 14, 2003
  2. richard

    crashing qsort

    richard, Aug 14, 2003, in forum: C Programming
    Replies:
    34
    Views:
    1,352
  3. Debashish Chakravarty

    [possibly OT] the comparison function in qsort

    Debashish Chakravarty, Nov 23, 2003, in forum: C Programming
    Replies:
    0
    Views:
    321
    Debashish Chakravarty
    Nov 23, 2003
  4. Ingo Brueckl
    Replies:
    5
    Views:
    486
    Keith Thompson
    Dec 19, 2003
  5. Charlie Zender

    Need warning-free qsort() comparison functions

    Charlie Zender, Jan 1, 2004, in forum: C Programming
    Replies:
    21
    Views:
    1,263
Loading...

Share This Page