Can't figure out what's wrong with my code for a HackerRank problem in C

Question

I'm sorry to ask help for a HackerRank problem here, I know it's not really the right place but nobody is answering me on HackerRank. Also, I'm new in C, so don't be to rude please.

Problem's description:

You are given n triangles, specifically, their sides a, b and c. Print them in the same style but sorted by their areas from the smallest one to the largest one. It is guaranteed that all the areas are different.

Link to the problem : https://www.hackerrank.com/challenges/small-triangles-large-triangles/problem

We can only edit the sort_by_area function.

First of all, I didn't calculate the triangles' area, I've just calculated the perimeter of each triangle, because the formula is simpler to read and to execute. Normally, that doesn't change anything for the result since a bigger perimeter means a bigger area. Tell me if I'm wrong.

The problem is that I have unexpected results: there's numbers on a line from my output that I really don't know from where they come. See:

Code:

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

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

void sort_by_area(triangle *tr, int n) {
    // Array for storing the perimeter.
    int *size = malloc(100 * sizeof(*size));
    
    // Adding perimeters in size array.
    for (int i = 0; i < n; i++) {
        size[i] = tr[i].a + tr[i].b + tr[i].c;
    }
    
    // Sort.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (size[j] > size[j + 1]) {
                // Sort in size array.
                int temp = size[j];
                size[j] = size[j + 1];
                size[j + 1] = temp;
                
                // Sort in tr array.
                temp = tr[j].a;
                tr[j].a = tr[j + 1].a;
                tr[j + 1].a = temp;
                
                temp = tr[j].b;
                tr[j].b = tr[j + 1].b;
                tr[j + 1].b = temp;
                
                temp = tr[j].c;
                tr[j].c = tr[j + 1].c;
                tr[j + 1].c = temp;
            }
        }
    }
}

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;
}

Input:

3
7 24 25
5 12 13
3 4 5

Output:

0 417 0 // Unexpected results on this line.
3 4 5
5 12 13

Expected output:

3 4 5
5 12 13
7 24 25

It seems that an error occurs from the 7 24 25 triangle, but for me, my code seems to be good.... Can you help to find out what's wrong ? I really want to understand before going to another problem.

Answer 1

The inner loop does not need to run till n, only till n-1

for (int j = 0; j < n - 1; j++)

Because when j == n, then you are comparing with random junk outside of your respective arrays by accessing size[j+1] and tr[j+1].

Also, when swapping, you don't need to copy the structure members one-by-one. You can simply do:

 // Sort in tr array.
 triangle tmp = tr[j];
 tr[j] = tr[j + 1];
 tr[j + 1] = tmp;

Edit: As @CiaPan pointed out:

You have a memory leak. You need to call free() after you are done with using the malloc'd memory.

You are not allocating the right amount of memory. If you are passed more than 100 triangles, your code might behave weirdly or randomly crash.

int *size = malloc(n* sizeof(*size));

Full code:

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

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

void sort_by_area(triangle *tr, int n) {
    // Array for storing the perimeter.
    int *size = malloc(n* sizeof(*size));
    
    // Adding perimeters in size array.
    for (int i = 0; i < n; i++) {
        size[i] = tr[i].a + tr[i].b + tr[i].c;
    }
    
    // Sort.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (size[j] > size[j + 1]) {
                // Sort in size array.
                int temp = size[j];
                size[j] = size[j + 1];
                size[j + 1] = temp;
                
                // Sort in tr array.
                triangle tmp = tr[j];
                tr[j] = tr[j + 1];
                tr[j + 1] = tmp;
            }
        }
    }
}

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;
}

Answer 2

The assumption that a greater parameter implies a greater area is incorrect. Why? Imagine an isosceles triangle with a base of 1000 units and a height of 1e-9 units. The area is minuscule, compared to an equilateral triangle with unit length whereas the former has a huge perimeter (~2000 units) compared to the latter (3 units). That's just an (extreme) example to convey the flaw in your assumption.

I'd suggest you roll up your own area function. It's even mentioned on the problem page to use Heron's formula. Since it's just to be used in the comparison, then we don't need the exact area but an indicative area. So something like

double area(triangle const* tr) {
    if(tr) {
        double semiPerimeter = (tr->a + tr->b + tr->c)/2.0;
        return semiPerimeter* (semiPerimeter - tr->a) * (semiPerimeter - tr->b) * (semiPerimeter - tr->c);
    } else {
        return 0;
    }
}

Where we don't really need to calculate the square root since we just need to compare the areas across triangles and comparing the square of areas across triangles should be fine.

After this, it's just a matter of plugging this into whatever you did, after correcting the inner j loop to run only till n-1 (as the other answer has also explained)

void sort_by_area(triangle* tr, int n) {
    /**
    * Sort an array a of the length n
    */
    double areaArr[n];
    for(size_t i = 0; i < n; ++i) {
        areaArr[i] = area(&tr[i]);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            if (areaArr[j] > areaArr[j + 1]) {
                // Sort in area array.
                int temp = areaArr[j];
                areaArr[j] = areaArr[j + 1];
                areaArr[j + 1] = temp;
                
                // Sort in tr array.
                triangle tmp = tr[j];
                tr[j] = tr[j + 1];
                tr[j + 1] = tmp;
            }
        }
    }
}

You could directly use qsort too here since the problem doesn't prohibit using standard functions, something like:

int qsortCompare(void const* a, void const* b) {
    triangle const* trA = a;
    triangle const* trB = b;
    if(trA && trB) {
        double areaA = area(trA);
        double areaB = area(trB);
        return (areaA < areaB) ? -1 :
        ((areaA > areaB)? 1: 0);
    }
    return 0;
}

void sort_by_area(triangle* tr, int n) {
    qsort(tr, n, sizeof(triangle), &qsortCompare);
}

Also, don't be restricted to add functions in the problem solution. The actual driver code only calls sort_by_area() but you can write other functions in the solution and call them from sort_by_area().