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

По условию печать зависит от разных индексов, а не от разных значений; для пирамиды печать нужна при каждой перестановке/проталкивании, а подсчет — только для операций, где участвует элемент массива. (laboratornaia-rabota-13 (1).pdf)

Оставил сортировку по убыванию, как у тебя в коде.

Точечные исправления

1. В Xoar:

c
if (a[l] != a[r]) {

заменить на:

c
if (l != r) {

У тебя неверно: если значения равны, но индексы разные, перестановка все равно между разными элементами массива. Плюс a[l] != a[r] — это сравнение с элементами массива, а ты его не считал.

2. В treePush удалить строку:

c
if (a[i] != v) flag = true;

У тебя неверно: это лишнее сравнение с элементом массива, которое не считалось. Флаг уже ставится в true, когда реально было проталкивание.

3. В tree заменить весь блок:

c
if (a[0] != a[i]) {
    swap(&a[0], &a[i]);
    hs_assignments += 3;
    printf("\n");
    fprint(a, n);
} else {
    swap(&a[0], &a[i]);
    hs_assignments += 3;
}

на:

c
swap(&a[0], &a[i]);
hs_assignments += 3;
printf("\n");
fprint(a, n);

У тебя неверно: 0 и i всегда разные, потому что цикл идет i >= 1. Значит перестановку надо печатать всегда, даже если значения одинаковые. Еще a[0] != a[i] — лишнее сравнение с массивом, которое ты не считал.

Готовый код

c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int qs_comparisons = 0;
int qs_assignments = 0;
int hs_comparisons = 0;
int hs_assignments = 0;
void swap(int *x, int *y){
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
void fprint(int *a, int l){
    int j;
    for (j = 1; j <= l; j++) {
        printf("%3d", j);
    }
    printf("\n");
    for (j = 0; j < l; j++) {
        printf("%3d", a[j]);
    }
    printf("\n");
}
void Xoar(int *a, int n, int first, int last)
{
    int pivot, l, r;
    l = first;
    r = last;
    pivot = a[(l + r) / 2];
    qs_assignments++;
    while (l <= r) {
        qs_comparisons++;
        while (a[l] > pivot) {
            qs_comparisons++;
            l++;
        }
        qs_comparisons++;
        while (a[r] < pivot) {
            qs_comparisons++;
            r--;
        }
        if (l <= r) {
            if (l != r) {
                swap(&a[l], &a[r]);
                qs_assignments += 3;
                printf("\n");
                fprint(a, n);
            }
            l++;
            r--;
        }
    }
    if (first < r) {
        Xoar(a, n, first, r);
    }
    if (l < last) {
        Xoar(a, n, l, last);
    }
}
bool treePush(int *a, int r, int q) {
    int v, i, j, pp;
    i = r;
    v = a[i];
    hs_assignments++;
    j = 2 * i + 1;
    pp = 0;
    bool flag = false;
    while (j <= q && !pp) {
        if (j < q) {
            hs_comparisons++;
            if (a[j] > a[j + 1])
                j++;
        }
        hs_comparisons++;
        if (v <= a[j])
            pp = 1;
        else {
            flag = true;
            a[i] = a[j];
            hs_assignments++;
            i = j;
            j = 2 * i + 1;
        }
    }
    a[i] = v;
    hs_assignments++;
    return flag;
}
void tree(int *a, int n)
{
    int k, i;
    k = n / 2;
    for (i = k - 1; i >= 0; i--) {
        if (treePush(a, i, n - 1)) {
            printf("\n");
            fprint(a, n);
        }
    }
    for (i = n - 1; i >= 1; i--) {
        swap(&a[0], &a[i]);
        hs_assignments += 3;
        printf("\n");
        fprint(a, n);
        if (treePush(a, 0, i - 1)) {
            printf("\n");
            fprint(a, n);
        }
    }
}
int main()
{
    int n, i;
    int *m, *a;
    scanf("%d", &n);
    m = (int*)malloc(n * sizeof(int));
    a = (int*)malloc(n * sizeof(int));
    if (!m || !a) {
        free(m);
        free(a);
        return 0;
    }
    for (i = 0; i < n; i++) {
        scanf("%d", &m[i]);
        a[i] = m[i];
    }
    fprint(a, n);
    Xoar(a, n, 0, n - 1);
    printf("%d %d\n", qs_assignments, qs_comparisons);
    tree(m, n);
    printf("%d %d\n", hs_assignments, hs_comparisons);
    free(m);
    free(a);
    return 0;
}