Не работает алгоритм сортировки вставками

Тест программы

Мне нужно отсортировать массив стуктур по возрастанию площади (функция Sort). Я использую алгоритм сортировки вставками, пока не до конца разобралась, как он работает (я новичок). Нашла уже готовый алгоритм, но работает он неправильно, не пойму, в чем дело. Подскажите, где ошибка

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10

typedef struct
{
    int number;
    double x1, y1;
    double x2, y2;
    double sq;
}coord;

int Enter(coord*, int);
void Print(coord*, int, const char*);
void Inside(coord*, int);
void Square(coord*, int);
void Sort(coord*, int);
void PrintSq(coord*, int, const char*);

void main(void)
{
    coord rectang[MAX]; // масив структур
    int size = Enter(rectang, MAX); 
    Print(rectang, size, "введених");
    Inside(rectang, size);
    Square(rectang, size);
    Sort(rectang, size);
    PrintSq(rectang, size, "відсортованих");
    getchar(); getchar();
}

int Enter(coord* ar, int s)
{
    system("chcp 1251");
    int m = 0;
    int end;
    printf(" 0 - завершити введення\n");
    for (m; m < s; m++) {
        ar[m].number = m + 1;
        printf(" Прямокутник №%d\n", ar[m].number);
        printf(" Введіть координати верхньої лівої вершини:\n x1: ");
        scanf_s("%lf", &ar[m].x1);
        printf(" y1: ");
        scanf_s("%lf", &ar[m].y1);
        printf(" Введіть координати нижньої правої вершини:\n x2: ");
        scanf_s("%lf", &ar[m].x2);
        printf(" y2: ");
        scanf_s("%lf", &ar[m].y2);
        rewind(stdin);
        if ((end = getchar()) == '0')
            break;
    }
    return m;
}

void Print(coord* ar, int s, const char* name)
{
    int m = 0;
    printf("\n\t\t\t Таблиця ");
    puts(name);
    printf("\t\t\t      даних ");
    printf("\n -------------------------------------------------------------------");
    printf("\n |    №    |   ");
    printf("   x1     |   ");
    printf("   y1     |   ");
    printf("   x2     |   ");
    printf("   y2     |");
    for (m; m <= s; m++) {
        printf("\n -------------------------------------------------------------------");
        printf("\n |    %d.   |   ", (ar + m)->number);
        printf(" %-9.2lf|   ", (ar + m)->x1);
        printf(" %-9.2lf|   ", (ar + m)->y1);
        printf(" %-9.2lf|   ", (ar + m)->x2);
        printf(" %-9.2lf|", (ar + m)->y2);
    }
    printf("\n -------------------------------------------------------------------");
}

void Inside(coord* ar, int s)
{
    int m, ins = 0;
    printf("\n\n № прямокутників, які знаходяться всередині першого:");
    for (m = 1; m < s; m++) {
        if (ar[m].x1 > ar[0].x1&& ar[m].x1 < ar[0].x2 && ar[m].y1 < ar[0].y1 && ar[m].y1 > ar[0].y2 &&
            ar[m].x2 > ar[0].x1&& ar[m].x2 < ar[0].x2 && ar[m].y2 < ar[0].y1 && ar[m].y2 > ar[0].y2) {
            printf("\t%d", m + 1);
            ins = 1;
        }   
    }
    if (ins == 0)
        printf("\tвідсутні");
}

void Square(coord* ar, int s)
{
    int m;
    double  a, b; //сторони прямокутника
    for (m = 0; m <= s; m++) {
        a = ar[m].x2 - ar[m].x1;
        b = ar[m].y1 - ar[m].y2;
        ar[m].sq = a * b;
    }
}

void Sort(coord* ar, int s)
{
    int i, j;
    for (i = 1; i < s; i++) { //сортування вставками
        for (j = i; j > 0 && ar[j - 1].sq > ar[j].sq; j--) {
            double t = ar[j].sq;
            ar[j].sq = ar[j - 1].sq;
            ar[j - 1].sq = t;
            int t1 = ar[j].number;
            ar[j].number = ar[j - 1].number;
            ar[j - 1].number = t1;
        }
    }
}

void PrintSq(coord* ar, int s, const char* name)
{
    int i;
    printf("\n\n\t\t      Таблиця ");
    puts(name);
    printf("\t\t\t      даних ");
    printf("\n -------------------------");
    printf("\n |    №    |   ");
    printf("   S      |");
    for (i = 0; i <= s; i++) { // виводимо таблицю
        printf("\n -------------------------");
        printf("\n |    %d.   |   ", ar[i].number);
        printf(" %-9.2lf|   ", ar[i].sq);
    }
    printf("\n -------------------------");
}

Ответы (2 шт):

Автор решения: e.n.shirokov

Нужно взять абсолютное значение площади, чтобы она не получилась отрицательной

void Square(coord* ar, int s)
{
    int m;
    double  a, b; //сторони прямокутника
    for (m = 0; m <= s; m++) {
        a = ar[m].x2 - ar[m].x1;
        b = ar[m].y1 - ar[m].y2;
        ar[m].sq = std::abs(a * b); // <--- АБСОЛЮТНОЕ ЗНАЧЕНИЕ ПЛОЩАДИ 
    }
}
→ Ссылка
Автор решения: 0andriy

Алгоритм сортировки вставкой для контейнера типа двусвязный список делается прямо в лоб:

static void inssort(struct list_head *bs)
{
    struct bus *b, *_b, *n, *_n;
    LIST_HEAD(result);

    list_for_each_entry_safe(b, _b, bs, node) {
        list_del(&b->node);

        list_for_each_entry_safe(n, _n, &result, node) {
            if (s(n) > s(b))
                break;
        }

        list_add(&b->node, &n->node);
    }

    list_splice(&result, bs, bs);
}

Пояснение: а) берём из неотсортированного списка первый элемент, б) удаляем его, в) проходимся по результирующему списку от головы к хвосту, пока не найдём больший (критерии выбираете сами, здесь функция s()), г) добавляем наш запомненный элемент в результирующий список. Повторяем предыдущие действия пока в исходном списке не останется элементов.

Полный текст программы.

Понятно, что можно использовать массив или другой тип контейнера, возни только будет больше.

→ Ссылка