Sorting an Array of double

Discussion in 'C++' started by Geoff, May 27, 2013.

  1. Geoff

    Geoff Guest

    I have an application that maintains two arrays of transmitter and
    receiver frequencies. The arrays are optionally sorted by user command
    which invokes the following functions.

    // globals
    #define MAX_ELEMENTS 1000
    double Tx[MAX_ELEMENTS + 1];
    double Rx[MAX_ELEMENTS + 1];

    int compare(const void *e1, const void *e2)
    {
    return (int)(* (double *)e1 - * (double *)e2);
    }

    void SortFreqs()
    {
    printf("Transmitters= %i ... ", Ttotal);
    qsort (Tx, Ttotal, sizeof(double), compare);
    printf("Receivers= %i ... ", Rtotal);
    qsort (Rx, Rtotal, sizeof(double), compare);
    }

    The data is typically entered by hand to 4 decimal places and the
    analysis of the data (intermodulation study) is done to
    user-modifiable precision of 3 decimal places. The user could enter
    data to greater precision but I don't think DBL_EPSILON will ever be a
    factor. The terminal array element is always 0.0 and the total number
    of elements is always <= 1000 and the sort excludes the terminal zero.

    It seems qsort is perfectly adequate for this purpose. Comments?
    Geoff, May 27, 2013
    #1
    1. Advertising

  2. Geoff

    Luca Risolia Guest

    Geoff wrote:

    > #define MAX_ELEMENTS 1000
    > double Tx[MAX_ELEMENTS + 1];
    > double Rx[MAX_ELEMENTS + 1];
    >
    > int compare(const void *e1, const void *e2)
    > {
    > return (int)(* (double *)e1 - * (double *)e2);
    > }
    >
    > void SortFreqs()
    > {
    > printf("Transmitters= %i ... ", Ttotal);
    > qsort (Tx, Ttotal, sizeof(double), compare);
    > printf("Receivers= %i ... ", Rtotal);
    > qsort (Rx, Rtotal, sizeof(double), compare);
    > }
    >
    > The data is typically entered by hand to 4 decimal places and the
    > analysis of the data (intermodulation study) is done to
    > user-modifiable precision of 3 decimal places. The user could enter
    > data to greater precision but I don't think DBL_EPSILON will ever be a
    > factor. The terminal array element is always 0.0 and the total number
    > of elements is always <= 1000 and the sort excludes the terminal zero.
    >
    > It seems qsort is perfectly adequate for this purpose. Comments?


    That's not elegant in C++. I would simply write:

    std::sort(std::begin(Tx), std::begin(Tx) + Ttotal);

    The same to order Rx.
    Luca Risolia, May 27, 2013
    #2
    1. Advertising

  3. Geoff

    Jorgen Grahn Guest

    On Mon, 2013-05-27, Geoff wrote:
    > I have an application that maintains two arrays of transmitter and
    > receiver frequencies. The arrays are optionally sorted by user command
    > which invokes the following functions.
    >
    > // globals
    > #define MAX_ELEMENTS 1000
    > double Tx[MAX_ELEMENTS + 1];
    > double Rx[MAX_ELEMENTS + 1];
    >
    > int compare(const void *e1, const void *e2)
    > {
    > return (int)(* (double *)e1 - * (double *)e2);
    > }
    >
    > void SortFreqs()
    > {
    > printf("Transmitters= %i ... ", Ttotal);
    > qsort (Tx, Ttotal, sizeof(double), compare);
    > printf("Receivers= %i ... ", Rtotal);
    > qsort (Rx, Rtotal, sizeof(double), compare);
    > }


    Ugh. Replace with:

    std::sort(Tx, Tx+Ttotal);
    std::sort(Rx, Rx+Rtotal);

    (And possibly a std::reverse somewhere there, if you want max..min
    rather than min..max order. I can't remember how qsort() expects
    things to work.)

    > The data is typically entered by hand to 4 decimal places and the
    > analysis of the data (intermodulation study) is done to
    > user-modifiable precision of 3 decimal places. The user could enter
    > data to greater precision but I don't think DBL_EPSILON will ever be a
    > factor. The terminal array element is always 0.0 and the total number
    > of elements is always <= 1000 and the sort excludes the terminal zero.


    I don't understand that, but I don't see how it is relevant. Do you
    want these doubles sorted by their actual value, or something else?

    > It seems qsort is perfectly adequate for this purpose. Comments?


    Adequate perhaps, but slow and error-prone. std::sort (or
    std::stable_sort ...) is what you should use.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, May 27, 2013
    #3
  4. Geoff

    Ike Naar Guest

    On 2013-05-27, Geoff <> wrote:
    > I have an application that maintains two arrays of transmitter and
    > receiver frequencies. The arrays are optionally sorted by user command
    > which invokes the following functions.
    >
    > // globals
    > #define MAX_ELEMENTS 1000
    > double Tx[MAX_ELEMENTS + 1];
    > double Rx[MAX_ELEMENTS + 1];
    >
    > int compare(const void *e1, const void *e2)
    > {
    > return (int)(* (double *)e1 - * (double *)e2);
    > }


    Do you really want, say, 1.6 and 2.4 to compare equal?

    This comparison function does not define a total
    ordering on the array, which is required by 7.20.5 p4:

    When the same objects (consisting of size bytes, irrespective of
    their current positions in the array) are passed more than once to
    the comparison function, the results shall be consistent with one
    another. That is, for qsort they shall define a total ordering on
    the array, and for bsearch the same object shall always compare
    the same way with the key.
    Ike Naar, May 27, 2013
    #4
  5. Geoff

    Jorgen Grahn Guest

    On Mon, 2013-05-27, Jorgen Grahn wrote:
    > On Mon, 2013-05-27, Geoff wrote:
    >> I have an application that maintains two arrays of transmitter and
    >> receiver frequencies. The arrays are optionally sorted by user command
    >> which invokes the following functions.
    >>
    >> // globals
    >> #define MAX_ELEMENTS 1000
    >> double Tx[MAX_ELEMENTS + 1];
    >> double Rx[MAX_ELEMENTS + 1];
    >>
    >> int compare(const void *e1, const void *e2)
    >> {
    >> return (int)(* (double *)e1 - * (double *)e2);
    >> }
    >>
    >> void SortFreqs()
    >> {
    >> printf("Transmitters= %i ... ", Ttotal);
    >> qsort (Tx, Ttotal, sizeof(double), compare);
    >> printf("Receivers= %i ... ", Rtotal);
    >> qsort (Rx, Rtotal, sizeof(double), compare);
    >> }

    >
    > Ugh. Replace with:
    >
    > std::sort(Tx, Tx+Ttotal);
    > std::sort(Rx, Rx+Rtotal);
    >
    > (And possibly a std::reverse somewhere there, if you want max..min
    > rather than min..max order. I can't remember how qsort() expects
    > things to work.)
    >
    >> The data is typically entered by hand to 4 decimal places and the
    >> analysis of the data (intermodulation study) is done to
    >> user-modifiable precision of 3 decimal places. The user could enter
    >> data to greater precision but I don't think DBL_EPSILON will ever be a
    >> factor. The terminal array element is always 0.0 and the total number
    >> of elements is always <= 1000 and the sort excludes the terminal zero.

    >
    > I don't understand that, but I don't see how it is relevant. Do you
    > want these doubles sorted by their actual value, or something else?


    Of course, unlike Ike Naar I completely missed the odd compare(), so
    never mind that last paragraph.

    I'm used to looking at an implementation of a < b for sorting and
    related tasks, so when I replied above I hadn't really bothered to
    read the compare() implementation.

    Perhaps that also says something about the relative merits of qsort()
    and std::sort ...

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, May 28, 2013
    #5
  6. Geoff

    SG Guest

    On May 27, 6:17 pm, Geoff wrote:
    > I have an application that maintains two arrays of transmitter
    > and receiver frequencies. The arrays are optionally sorted by
    > user command which invokes the following functions.
    >
    > // globals
    > #define MAX_ELEMENTS 1000
    > double Tx[MAX_ELEMENTS + 1];
    > double Rx[MAX_ELEMENTS + 1];
    >
    > int compare(const void *e1, const void *e2)
    > {
    >         return (int)(* (double *)e1 - * (double *)e2);
    > }


    Consider *(double*)e1 to be 0.375
    Consider *(double*)e2 to be 0.25

    (int)(0.375-0.25)
    = (int)(0.125)
    = 0

    But 0 tells qsort that 0.375 and 0.25 are equal.

    > void SortFreqs()
    > {
    >         printf("Transmitters= %i ... ", Ttotal);
    >         qsort (Tx, Ttotal, sizeof(double), compare);
    >         printf("Receivers= %i ... ", Rtotal);
    >         qsort (Rx, Rtotal, sizeof(double), compare);
    > }


    Avoid globals variables.
    Avoid C-isms we have better replacements for in C++.

    You might want to look into
    - std::vector<> you get via #include <vector>
    - std::sort you get via #include <algorithm>


    Cheers!
    SG
    SG, May 28, 2013
    #6
  7. Geoff

    SG Guest

    On May 28, 12:03 pm, Juha Nieminen wrote:
    >
    >   bool compare(double e1, double e2)
    >   {
    >       return int(e1 - e2);
    >   }
    >
    >   void SortFreqs()
    >   {
    >       printf("Transmitters= %i ... ", Ttotal);
    >       std::sort(Tx, Tx + Ttotal, compare);
    >       printf("Receivers= %i ... ", Rtotal);
    >       std::sort(Rx, Rx + Rtotal, compare);
    >   }


    This is not the code anybody is looking for.
    See Jorgen Grahn's and Ike Naar's response.
    SG, May 28, 2013
    #7
  8. Geoff

    Geoff Guest

    On Mon, 27 May 2013 20:17:42 +0200, Luca Risolia
    <> wrote:

    >std::sort(std::begin(Tx), std::begin(Tx) + Ttotal);


    Everyone had good suggestions about the std::sort solution and this
    was exactly the kind of expression I was looking for.

    Thanks.
    Geoff, May 28, 2013
    #8
  9. Geoff

    Geoff Guest

    On 27 May 2013 18:25:05 GMT, Jorgen Grahn <>
    wrote:

    >On Mon, 2013-05-27, Geoff wrote:
    >> I have an application that maintains two arrays of transmitter and
    >> receiver frequencies. The arrays are optionally sorted by user command
    >> which invokes the following functions.
    >>
    >> // globals
    >> #define MAX_ELEMENTS 1000
    >> double Tx[MAX_ELEMENTS + 1];
    >> double Rx[MAX_ELEMENTS + 1];
    >>
    >> int compare(const void *e1, const void *e2)
    >> {
    >> return (int)(* (double *)e1 - * (double *)e2);
    >> }
    >>
    >> void SortFreqs()
    >> {
    >> printf("Transmitters= %i ... ", Ttotal);
    >> qsort (Tx, Ttotal, sizeof(double), compare);
    >> printf("Receivers= %i ... ", Rtotal);
    >> qsort (Rx, Rtotal, sizeof(double), compare);
    >> }

    >
    >Ugh. Replace with:
    >
    > std::sort(Tx, Tx+Ttotal);
    > std::sort(Rx, Rx+Rtotal);
    >
    >(And possibly a std::reverse somewhere there, if you want max..min
    >rather than min..max order. I can't remember how qsort() expects
    >things to work.)
    >
    >> The data is typically entered by hand to 4 decimal places and the
    >> analysis of the data (intermodulation study) is done to
    >> user-modifiable precision of 3 decimal places. The user could enter
    >> data to greater precision but I don't think DBL_EPSILON will ever be a
    >> factor. The terminal array element is always 0.0 and the total number
    >> of elements is always <= 1000 and the sort excludes the terminal zero.

    >
    >I don't understand that, but I don't see how it is relevant. Do you
    >want these doubles sorted by their actual value, or something else?
    >
    >> It seems qsort is perfectly adequate for this purpose. Comments?

    >
    >Adequate perhaps, but slow and error-prone. std::sort (or
    >std::stable_sort ...) is what you should use.
    >
    >/Jorgen


    Agreed. Your suggestion is cleaner and clearer than Luca's.
    Geoff, May 29, 2013
    #9
  10. Geoff

    Jorgen Grahn Guest

    On Wed, 2013-05-29, Geoff wrote:
    > On 27 May 2013 18:25:05 GMT, Jorgen Grahn <>
    > wrote:
    >
    >>On Mon, 2013-05-27, Geoff wrote:
    >>> I have an application that maintains two arrays of transmitter and
    >>> receiver frequencies. The arrays are optionally sorted by user command
    >>> which invokes the following functions.
    >>>
    >>> // globals
    >>> #define MAX_ELEMENTS 1000
    >>> double Tx[MAX_ELEMENTS + 1];
    >>> double Rx[MAX_ELEMENTS + 1];
    >>>
    >>> int compare(const void *e1, const void *e2)
    >>> {
    >>> return (int)(* (double *)e1 - * (double *)e2);
    >>> }
    >>>
    >>> void SortFreqs()
    >>> {
    >>> printf("Transmitters= %i ... ", Ttotal);
    >>> qsort (Tx, Ttotal, sizeof(double), compare);
    >>> printf("Receivers= %i ... ", Rtotal);
    >>> qsort (Rx, Rtotal, sizeof(double), compare);
    >>> }

    >>
    >>Ugh. Replace with:
    >>
    >> std::sort(Tx, Tx+Ttotal);
    >> std::sort(Rx, Rx+Rtotal);

    ....
    >> [...] std::sort (or
    >>std::stable_sort ...) is what you should use.
    >>
    >>/Jorgen

    >
    > Agreed. Your suggestion is cleaner and clearer than Luca's.


    Luca suggested

    std::sort(std::begin(Tx), std::begin(Tx) + Ttotal);

    Well, I don't know what std::begin does -- is it a C++11 thing, or
    something in C++98 I simply missed? Perhaps it's better.

    In any case, std::sort is perfectly capable of sorting ordinary
    arrays. Like most standard algorithms it's happy to work with
    raw pointers.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, May 29, 2013
    #10
  11. Geoff

    Luca Risolia Guest

    Jorgen Grahn wrote:

    > Luca suggested
    >
    > std::sort(std::begin(Tx), std::begin(Tx) + Ttotal);
    >
    > Well, I don't know what std::begin does -- is it a C++11 thing, or
    > something in C++98 I simply missed? Perhaps it's better.


    The above statement is more general as it can sort any standard container
    providing Random Access Iterators. In facts, std::begin() is a new function
    template introduced in C++11 which returns an iterator to the beginning of the
    container or array passed as argument. It has no overhead on performance as
    the call can be optimized out by any compiler.
    Luca Risolia, May 29, 2013
    #11
  12. Geoff

    Ian Collins Guest

    Luca Risolia wrote:
    > Jorgen Grahn wrote:
    >
    >> Luca suggested
    >>
    >> std::sort(std::begin(Tx), std::begin(Tx) + Ttotal);
    >>
    >> Well, I don't know what std::begin does -- is it a C++11 thing, or
    >> something in C++98 I simply missed? Perhaps it's better.

    >
    > The above statement is more general as it can sort any standard container
    > providing Random Access Iterators. In facts, std::begin() is a new function
    > template introduced in C++11 which returns an iterator to the beginning of the
    > container or array passed as argument. It has no overhead on performance as
    > the call can be optimized out by any compiler.


    Thanks for pointing it out, I'd missed that one!

    --
    Ian Collins
    Ian Collins, May 29, 2013
    #12
    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. Venkat
    Replies:
    4
    Views:
    969
    Venkat
    Dec 5, 2003
  2. Sydex
    Replies:
    12
    Views:
    6,472
    Victor Bazarov
    Feb 17, 2005
  3. Replies:
    5
    Views:
    427
    James Kanze
    Jun 27, 2008
  4. jimgardener
    Replies:
    3
    Views:
    285
    Joshua Cranmer
    Jul 11, 2008
  5. KevinSimonson
    Replies:
    8
    Views:
    693
    Daniel Pitts
    Oct 12, 2010
Loading...

Share This Page