Double sort (Sort elements on 2 different values)

Question

Let's say I have a struct node that looks like this:

typedef struct node{
    int t;
    double p;
}node;

And then I also have an array of struct node some of which have equal values p.

What I want to do is:

Primarily, sort the elements based on value p. And after I have a sorted array based on p, I want every sub-array with the same p to be sorted based on value t.

For example:

If I have original array that looks like this (1st element is p, 2nd element is t):

[0,10|1], [0.05|0], [0,10|0], [0,05|2], [0,10|2], [0,15|1], [0,05|1]

After it is double sorted, it should look like this:

[0,05|0], [0,05|1], [0,05|2], [0,10|0], [0,10|1], [0,10|2], [0,15|1].

I have come up with the bubble sort based on p, but I then have difficulties on how to sort sub-arrays on t. Here is bubble sort code on p.

node *sort_p(node *nodes, int num) {
    int i, j;
    node *temp = malloc(sizeof(node));

    for(i=1; i<num; i+=1){
        for(j=0; j<num-i; j+=1){
            if(nodes[j].p > nodes[j+1].p){
                *temp = nodes[j];
                nodes[j] = nodes[j+1];
                nodes[j+1] = *temp;
            }
        }
    }
    free(temp);

    return nodes;
}

How could I accomplish the desired double sort?

UPDATE

I wrote a compare method that works with qsort() as suggested below, but it does not yield the desired results from one point.

I am calling the method like this: qsort(nodes, num_of_nodes, sizeof(node), compare_pairs);

Where compare_pairs() looks like this:

static int compare_pairs(node *n1, node *n2){

const node *na1 = n1;
const node *na2 = n2;

if(na1->p< na2->p) return -1;
if(na1->p> na2->p) return 1;

if(na1->t < na2->t) return -1;
if(na1->t > na2->t) return 1;

return 0;

Problem

The unwanted behaviour starts at 3. STEP which looks like this:

List: [0.10 | 2] [0.10 | 999] [0.10 | 999] [0.15 | 999] [0.15 | 999] [0.15 | 1] [0.25 | 999]

And should look like this:

List: [0.10 | 2] [0.10 | 999] [0.10 | 999] [0.15 | 1] [0.15 | 999] [0.15 | 999] [0.25 | 999]

Initial list: [0.25 | 999] [0.15 | 999] [0.15 | 999] [0.10 | 999] [0.10 | 999] [0.05 | 999] [0.05| 999] [0.05 | 999] [0.05 | 999] [0.05 | 999]

STEP:

Erasing (min) node 0.050000...

Creating (new) node 0.100000...

List: [0.05 | 999] [0.05 | 999] [0.05 | 999] [0.10 | 1] [0.10 | 999] [0.10 | 999] [0.15 | 999] [0.15 | 999] [0.25 | 999]

STEP:

Erasing (min) node 0.050000...

Creating (new) node 0.100000...

List: [0.05 | 999] [0.10 | 1] [0.10 | 2] [0.10 | 999] [0.10 | 999] [0.15 | 999] [0.15 | 999] [0.25 | 999]

STEP:

Erasing (min) node 0.050000...

Erasing (min) node 0.100000...

Creating (new) node 0.150000...

List: [0.10 | 2] [0.10 | 999] [0.10 | 999] [0.15 | 999] [0.15 | 999] [0.15 | 1] [0.25 | 999]

STEP:

Erasing (min) node 0.100000...

Erasing (new) node 0.200000...

List: [0.10 | 999] [0.15 | 999] [0.15 | 999] [0.15 | 1] [0.20 | 1] [0.25 | 999]

STEP:

Erasing (min) node 0.100000...

Erasing (min) node 0.150000...

Creating (new) node 0.250000...

List: [0.15 | 999] [0.15 | 1] [0.20 | 1] [0.25 | 1] [0.25 | 999]

STEP:

Erasing (min) node 0.150000...

Erasing (new) node 0.300000...

List: [0.20 | 1] [0.25 | 1] [0.25 | 999] [0.30 | 1]

STEP:

Erasing (min) node 0.200000...

Erasing (min) node 0.250000...

Erasing (new) node 0.450000...

List: [0.25 | 999] [0.30 | 1] [0.45 | 1]

STEP:

Erasing (min) node 0.250000...

Erasing (min) node 0.300000...

Creating (new) node 0.550000...

List: [0.45 | 1] [0.55 | 1]

STEP:

Erasing (min) node 0.450000...

Erasing (min) node 0.550000...

Creating (new) node 1.000000...

List: [1.00 | 1]

General idea*

In every step two minimal nodes get deleted from list, and one new node gets inserted into the list. The node that gets inserted has the value of t for 1 bigger then the greatest in the list, except that it does not compare itself to the t value of 999. If the greatest in the list has t = 999, then the one inserted will have 1.

Find greatest t:

int max_t(node *nodes, int num, double p){
int max_t= 0;
int i;
for(i=0; i<num; i+=1){
    if(nodes[i].p== p && nodes[i].t != 999){
        if(nodes[i].t > max_t){
            max_t = nodes[i].t;
        }
    }
}
return max_t;

Main code:

node *nodes = malloc(num_of_nodes*sizeof(node));
int i;
for(i=0; i<num_of_nodes; i+=1){
    node n;
    n.t = 999;
    n.p = *(probabs+ i);
    *(nodes+i) = n;
}

qsort(nodes, num_of_nodes, sizeof(node), compare_pairs);

while(num_of_nodes> 1){

    printf("\n%d. STEP:\n", z);
    z += 1;

    // 2) Find two min nodes
    node *min_n1 = malloc(sizeof(node));
    node *min_n2 = malloc(sizeof(node));

    *min_n1 = nodes[0];
    printf("Erasing (min) node %lf...\n", min_n1->p);
    nodes= erase_node(nodes, min_n1, num_of_nodes);
    num_of_nodes -= 1;

    *min_n2 = nodes[0];
    printf("Erasing (min) node %lf...\n", min_n2->p);
    nodes= erase_node(nodes, min_n2, num_of_nodes);
    num_of_nodes-= 1;

    // 3) Create new node, add it to the list
    node *new:node = malloc(sizeof(node));
    new_node->p= min_n1->p + min_n2->p;
    double p = new->p;
    int max_t = max_t(nodes, num_of_nodes, p);
    new_node->t = max_t + 1;

    printf("Creating (new) node %lf...\n", new_node->p);
    node = add_node(nodes, new_node, num_of_nodes);
    num_of_nodes += 1;

    qsort(nodes, num_of_nodes, sizeof(node), compare_pairs);

    printf("List: ");
    int k;
    for(k=0; k<num_of_nodes; k+=1){
        printf("[%.2lf | %d]  ", nodes[k].p, nodes[k].t);
    }
    printf("\n");

score 6 · Answer 1 · edited May 23 '17 at 12:12

Your approach is needlessly complicated. There's no need to "sort twice", all you need to do is enhance the comparison operator.

Also, use qsort() to sort arrays in C, it's much easier than rolling your own sort, and might have better performance too.

Basically, you should try to fill in the blanks of a function like this:

static int compare_pairs(const void *a, const void *b)
{
  const node *na = a, *nb = b;

  /* more code here */
}

Essentially you have the solution when you say "I want every sub-array with the same p to be sorted based on value t".

That means the body of the comparison function becomes:

if(na->p < nb->p)
  return -1;
if(na->p > nb->p)
  return 1;
/* If we get this far, we know the p values are equal, so tie-break with t. */
if(na->t < nb->t)
  return -1;
if(na->t > nb->t)
  return 1;
return 0;

Finally, please don't cast the return value of malloc() in C.

Double sort (Sort elements on 2 different values)

1 Answers1