Reputation: 11

Attempt at ordering an array of structs based on an array of double results in array with unpredictable order

I am trying to order some triangles based on their surface. To do so, the triangles are stored in an array of structs named triangle. To sort this, my idea was to create a sort of parallel array with the surfaces of the triangle and swapping elements of both arrays "in parallel". The sorting is done in a void function that receives the array and the number of elements in it.

The sorting seems to work, I checked by printing the array of surfaces, but when I print the array of triangles (both from inside and outside the function), it is not in the correct order. It is neither the sorted one nor the initial one.

I used bubble sort for sorting, I know it's inefficient but it's also very simple to implement. I know I could have used qsort function, but for learning's sake I'd like to do this from scratch first. Here is the code, hopefully it is readable enough:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct triangle {
    int a;
    int b;
    int c;
};

typedef struct triangle triangle;
void sort_by_area(triangle *tr, int n) {
    double s[n];
    double p, s_2;
    int u;
    triangle v;
    for (int i = 0; i < n; i++) {
        p = (tr[i].a + tr[i].b + tr[i].b);
        p = p / 2.0;
        s_2 = p * (p - tr[i].a) + (p - tr[i].b) + (p - tr[i].c);
        s[i] = sqrt(s_2);
    }

    //bubble sort
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < (n - i - 1); j++) {
            if (s[j] > s[j + 1]) {
                u = s[j];
                s[j] = s[j + 1];
                s[j + 1] = u;
                
                v = tr[j];
                tr[j]= tr[j + 1];
                tr[j + 1] = v;
                //printf("swapped");
            }
        }
    } 
    
    for (int i = 0; i < n; i++) {
        printf("%f\n", s[i]);
        if (i == (n - 1)) {
            printf("\n\n");
        }
    }    
}

int main() {
    int n;
    scanf("%d", &n);
    triangle *tr = malloc(n * sizeof(triangle));
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c);
    }
    sort_by_area(tr, n);
    for (int i = 0; i < n; i++) {
        printf("%d %d %d\n", tr[i].a, tr[i].b, tr[i].c);
    }
    return 0;
}

Here an input example that I tried for testing:

My result is

Upvotes: 1

Answers (2)

arfneto

Reputation: 1765

"I am trying to order some triangles based on their surface. To do so, the triangles are stored in an array of structs named triangle. To sort this my idea was to create a sort of parallel array with the surfaces of the triangle and swapping "in parallel" the two arrays. The sorting is done in a void function that receives the array and the number of elements in it"

You can get id done the way you are trying to, but understand that is far more easier when you have an abstraction closer to the data you have.

This is all you have in your code:

    struct triangle
    {
        int a;
        int b;
        int c;
    };

    // ...

    double   s[n]; // array with surfaces for all triangles  
    
    // ...

    void sort_by_area(triangle* tr, int n);

why the code fails

You are trying to use Heron's formula, but wrote it all wrong:

        p = (tr[i].a+tr[i].b+tr[i].b);
        p = p/2.0;
        s_2 = p*(p-tr[i].a)+(p-tr[i].b)+(p-tr[i].c);
        s[i] = sqrt(s_2);

you wrote tr[i].b twice...
s_2 is not a product of a sum. it is a product

This works:

       p   = tr[i].a + tr[i].b + tr[i].c;
       p   = p / 2.0;
       s_2 = p * (p - tr[i].a) * (p - tr[i].b) *
             (p - tr[i].c);
       s[i] = sqrt(s_2);

As suggested by @Oka use functions.

Try simple things at first: the obvious triangle to test is 3,4,5 with area 6.

Look also into:

    double s[n];
    double p, s_2;
    int      u;

s[n] is not in fact a C thing. VLA are seen mostly in use by students. Never in production code. Just allocate the array and free it at exit, since n is a parameter.
declare one variable per line. Initialize all of them.
Use meaningful names. Here u is a temporary place for swapping values in the sort function. Name it as save or temp or tmpas everybody
if you are saving a double value, and s is double[n], you can not save it in an int value.

                u        = s[j];
                s[j]     = s[j + 1];
                s[j + 1] = u;

an Example using a probably better abstraction

your data is not a triangle: is a set of triangles, but this is not in your model. This way your code gets harder to write, change and read: a simple array implies in saving and passing counters everywhere.
sort is just sort: you should not mix sort and data. you just need a compare function, so use one.
if you have a collection to sort you must show it before and after. It is the simplest thing to do.
with 3 sides per triangle it is really boring to imagine one entering these at the terminal. Use a file. Never write interactive code. It will just slow you down. A lot.

a collection of triangles

Since we want to display the triangles with the computed areas before and after sort, it may be better to save the area value inside Triangle:.

  
typedef struct
{
    int    a;
    int    b;
    int    c;
    double area;
} Triangle;

double Heron(Triangle*);
int    show_triangle(Triangle*, const char* msg);

Heron gets a Triangle and returns its area
show_triangle gets a Triangle and an optional message and displays them

the collection itself

typedef struct
{
    size_t    capacity;
    size_t    size;
    Triangle* T;
} Triangles;

Triangles* create_triangles(size_t size); //constructor
Triangles* destroy_triangles(Triangles*); // destructor
Triangles* get_triangles(const char* input);
int        show_triangles(Triangles*, const char* msg);

create_triangles returns an empty container --- C++ name for this
destroy_triangles does the expected.
get_triangles accepts a file name and returns a collection --- java name for this
show_triangles uses show_triangle and does the expected
int bubble_sort(Triangle* T, size_t size) sorts the thing on area value

`main` for the example

With this model main can be more direct:

int main(void)
{
    const char* in_file = "input.txt";
    Triangles*  coll    = get_triangles(in_file);
    show_triangles(coll, "***** before sort *****\n\n");
    bubble_sort(coll->T, coll->size);
    show_triangles(coll, "***** after sort *****\n\n");
    destroy_triangles(coll);
    return 0;
}

output



***** before sort *****

11 triangles in this set:

  1   [       3,       4,       5       A =       6.00]
  2   [      67,      67,      19       A =     630.07]
  3   [       3,      57,      55       A =      62.59]
  4   [      33,      33,      33       A =     471.55]
  5   [      61,      58,      59       A =    1522.35]
  6   [      23,      43,      35       A =     401.80]
  7   [      48,      42,      45       A =     869.02]
  8   [      23,      12,      27       A =     137.29]
  9   [      41,      34,      22       A =     373.86]
  10  [      26,      49,      35       A =     437.49]
  11  [      63,      46,      45       A =    1034.11]


***** after sort *****

11 triangles in this set:

  1   [       3,       4,       5       A =       6.00]
  2   [       3,      57,      55       A =      62.59]
  3   [      23,      12,      27       A =     137.29]
  4   [      41,      34,      22       A =     373.86]
  5   [      23,      43,      35       A =     401.80]
  6   [      26,      49,      35       A =     437.49]
  7   [      33,      33,      33       A =     471.55]
  8   [      67,      67,      19       A =     630.07]
  9   [      48,      42,      45       A =     869.02]
  10  [      63,      46,      45       A =    1034.11]
  11  [      61,      58,      59       A =    1522.35]

This is just a toy. Consider passing file name in the command line.

complete code for the example

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define itoa _itoa

typedef struct
{
    int    a;
    int    b;
    int    c;
    double area;
} Triangle;

double Heron(Triangle*);
int    show_triangle(Triangle*, const char* msg);

typedef struct
{
    size_t    capacity;
    size_t    size;
    Triangle* T;
} Triangles;

Triangles* create_triangles(size_t size); //constructor
Triangles* destroy_triangles(Triangles*); // destructor
Triangles* get_triangles(const char* input);
int        show_triangles(Triangles*, const char* msg);

void bubble_sort(Triangle* T, size_t size);

int main(void)
{
    const char* in_file = "input.txt";
    Triangles*  coll    = get_triangles(in_file);
    show_triangles(coll, "\n\n***** before sort *****\n\n");
    bubble_sort(coll->T, coll->size);
    show_triangles(coll, "\n\n***** after sort *****\n\n");
    destroy_triangles(coll);
    return 0;
}

void bubble_sort(Triangle* T, size_t size)
{  // bubble sort
    Triangle temp;
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < (size - i - 1); j++)
        {
            if (T[j].area > T[j + 1].area)
            {
                temp     = T[j];
                T[j]     = T[j + 1];
                T[j + 1] = temp;
            }
        }
    }
}

double Heron(Triangle* T)
{
    double hp =
        (T->a + T->b + T->c) / 2.;  // half perimeter
    return sqrt(
        hp * (hp - T->a) * (hp - T->b) * (hp - T->c));
}

int show_triangle(Triangle* T, const char* msg)
{
    if (T == NULL) return -1;
    if (msg != NULL) printf("%s", msg);
    printf(
        "[%8d,%8d,%8d\tA = %10.2f] \n", T->a, T->b, T->c,
        T->area);
    return 0;
}

Triangles* create_triangles(size_t size)
{
    // fprintf(stderr, "%llu triangles\n", size);
    Triangles* set = malloc(sizeof(Triangles));
    if (set == NULL) return NULL;
    set->capacity = size;
    set->size     = 0;  // now empty
    // allocate array of triangles
    set->T = malloc(size * sizeof(Triangle));
    if (set->T == NULL)
    {
        free(set);
        return NULL;
    }
    return set;
}

Triangles* destroy_triangles(Triangles* S)
{
    if (S == NULL) return NULL;
    free(S->T);
    free(S);
    return NULL;
}

Triangles* get_triangles(const char* input)
{
    FILE* in = fopen(input, "r");
    if (in == NULL) return NULL;
    char  line[256];
    char* p = fgets(line, sizeof(line), in);
    if (p == NULL)
    {
        fclose(in);
        return NULL;
    }
    size_t size = atol(line);
    if (size == 0)
    {
        fclose(in);
        return NULL;
    }
    //fprintf(stderr, "%llu triangles\n", size);
    if (size > 1000) size = 1000; // some limit
    Triangles* set = create_triangles(size);
    if (set == NULL)
    {
        fclose(in);
        return NULL;
    }
    for (int i = 0, res = 0; i < size; i += 1)
    {
        res = fscanf(
            in, "%d%d%d", &set->T[i].a, &set->T[i].b,
            &set->T[i].c);
        if (res != 3)
        {
            destroy_triangles(set);
            fclose(in);
            return NULL;
        }
        set->T[i].area = Heron(&set->T[i]);
        set->size      = size;
    };  // for
    fclose(in);
    return set;
}

int show_triangles(Triangles* S, const char* msg)
{
    if (S == NULL) return -1;
    if (msg != NULL) printf("%s", msg);
    printf("%llu triangles in this set:\n\n", S->size);
    for (size_t i = 0; i < S->size; i += 1)
    {
        // get the index rigth justified
        char num[20];
        itoa((int)(1+i), num, 10);
        char str[20];
        sprintf(str, "  %-4s", num);
        show_triangle(&(S->T[i]), str);
    }

    return 0;
}

HIH

Upvotes: 1

Oka

Reputation: 26375

Your calculation for Heron's formula is incorrect, because in

p*(p-tr[i].a)+(p-tr[i].b)+(p-tr[i].c)

you are first multiplying the semiperimeter, p, by p - tr[i].a, and then adding it to the result of (p - tr[i].b) + (p - tr[i].c).

See: Operator precedence.

Instead, you are looking for the product of the semiperimeter and each side subtracted from the semiperimeter:

p * (p - a) * (p - b) * (p - c)

^{Variables for each side simplified.}

The first thing to do is simplify your code by writing functions that do one thing, and do it well

static double herons(const struct triangle *t)    
{                            
    double p = (t->a + t->b + t->c) / 2.0;
    return sqrt(p * (p - t->a) * (p - t->b) * (p - t->c));
}

and test those functions in isolation

#include <stdio.h>
#include <math.h>

struct triangle {
    int a;
    int b;
    int c;
};

static double herons(const struct triangle *t)
{
    double p = (t->a + t->b + t->c) / 2.0;
    return sqrt(p * (p - t->a) * (p - t->b) * (p - t->c));
}

int main(void)
{
    struct triangle tr[] = {
        { 67, 67, 19 },
        { 3 , 57, 55 },
        { 33, 33, 33 },
        { 61, 58, 59 },
        { 23, 43, 35 },
        { 48, 42, 45 },
        { 23, 12, 27 },
        { 41, 34, 22 },
        { 26, 49, 35 },
        { 63, 46, 45 }
    };

    for (size_t i = 0; i < (sizeof tr / sizeof *tr); i++)
        printf("%2d %2d %2d herons(%.5f)\n", tr[i].a, tr[i].b, tr[i].c, herons(tr + i));
}

to see if the results are what you expect

67 67 19 herons(630.06919)
 3 57 55 herons(62.58744)
33 33 33 herons(471.55083)
61 58 59 herons(1522.35344)
23 43 35 herons(401.79869)
48 42 45 herons(869.02154)
23 12 27 herons(137.28802)
41 34 22 herons(373.85952)
26 49 35 herons(437.49286)
63 46 45 herons(1034.10638)

and then move on from there.

For sorting, it may be easier to start with the vetted library function qsort, and a naive approach of recalculating areas at each step

static int compare_by_area(const void *a, const void *b)
{
    double l = herons(a);
    double r = herons(b);

    return (l > r) - (l < r);
}

qsort(tr, sizeof tr / sizeof *tr, sizeof *tr, compare_by_area);

^{Example usage, with the array defined above.}

which when plugged into the previously tested example, gives a good looking result:

 3 57 55 herons(62.58744)
23 12 27 herons(137.28802)
41 34 22 herons(373.85952)
23 43 35 herons(401.79869)
26 49 35 herons(437.49286)
33 33 33 herons(471.55083)
67 67 19 herons(630.06919)
48 42 45 herons(869.02154)
63 46 45 herons(1034.10638)
61 58 59 herons(1522.35344)

After you have a working baseline, start to modify just one part of the program. Here is a modified version of your sort function, using the naive approach of recalculating the areas at each step.

static void sort_by_area(struct triangle *tr, int n)
{
    for (int i = 0; i < (n - 1); i++) {
        for (int j = 0; j < (n - i - 1); j++) {
            if (herons(tr + j) > herons(tr + j + 1)) {
                struct triangle v = tr[j];
                tr[j]= tr[j + 1];
                tr[j + 1] = v;
            }
        }
    }
}

If we test this, it gives the expected results. So we move on to caching the results

static void sort_by_area(struct triangle *tr, int n)
{
    double s[n];

    for (int i = 0; i < n; i++)
        s[i] = herons(tr + i);

    for (int i = 0; i < (n - 1); i++) {
        for (int j = 0; j < (n - i - 1); j++) {
            if (s[j] >  s[j + 1]) {
                double u = s[j];
                s[j] = s[j+1];
                s[j+1] = u;

                struct triangle v = tr[j];
                tr[j]= tr[j + 1];
                tr[j + 1] = v;
            }
        }
    }
}

which, unsurprisingly, still works because it is built on previously tested code.

^{Next: benchmark this sort against the naive qsort approach.}

Note: Generally, prefer size_t to int when dealing with object sizes (including array lengths).

Note: The VLA double s[n]; will fail for non-positive values of n, or if n causes the object to exhaust available (stack) memory.

Note: int u; as the temporary variable for the double swap in your code truncates the left-hand side of the comparison on every swap. This was not a problem when using your data, but would have been if given a data set containing two (or more) floating-point values that convert to the same integer value. A more aggressive warning level from your compiler should highlight this (gcc/clang: -Wconversion [-Wfloat-conversion]).

Upvotes: 3