Sorting an Array of double

[Geoff]

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?

 

[Luca Risolia]

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

 

[Jorgen Grahn]

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

 

[Ike Naar]

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.

 

[Jorgen Grahn]

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

 

[SG]

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]

  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.

 

[Geoff]

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]

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.

 

[Jorgen Grahn]

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

 

[Luca Risolia]

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.

 

[Ian Collins]

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!