КОД ДОЛБАЕБА СВЕТЛОГО(

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#include <time.h>

/*
 * Условия задачи
 * Тип элемента: int.
 * Тип сортировки: по неубыванию.
 * Методы сортировки: сортировка простым выбором + сортировка Шелла.
 */

int cmps = 0, prms = 0;
static bool cmp(int lhs, int rhs) {
    cmps++;
    if (lhs > rhs) return 0;
    return 1;
}

static void swap(int *lhs, int *rhs) {
    int temp = *lhs;
    *lhs = *rhs;
    *rhs = temp;
    prms++;
}

static void gen(int n, int *a, int type) {
    if (type == 1) {
        for (int i = 0; i < n; ++i) {
            a[i] = i + 1;
        }
    } else if (type == 2) {
        for (int i = 0; i < n; ++i) {
            a[i] = n - i;
        }
    } else if (type == 3 || type == 4) {
        for (int i = 0; i < n; ++i) {
            a[i] = rand();
        }
    }
}

static void selection_sort(int n, int *a) {
    int min_index;
    for (int i = 0; i < n - 1; ++i) {
        min_index = i;
        for (int j = i + 1; j < n; ++j) {
            if (cmp(a[j], a[min_index])) {
                min_index = j;
            }
        }
        swap(a + min_index, a + i);
    }
}

static void shell_sort(int n, int *a) {
    for (int d = n / 2; d > 0; d /= 2) {
        for (int i = d; i < n; ++i) {
            for (int j = i - d; j >= 0 && !cmp(a[j], a[j + d]); j -= d) {
                swap(a + j, a + j + d);
            }
        }
    }
}

static void test(int *a, int *sorted, int n) {
    int *checked = (int *) calloc(n, sizeof(int));
    // found показывает, найден ли текущий элемент отсортированного массива в исходном
    int found = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // Если в исходном массиве есть такая позиция,
            // что ее значение равно значению текущего элемента отсортированного массива
            // и она еще не была использована для проверки,
            // то помечаем ее как использованную и задаем found = 1
            if (sorted[i] == a[j]) {
                if (checked[j] == 0) {
                    checked[j] = 1;
                    found = 1;
                    break;
                }
            }
        }
        // Если элемент отсортированного массива не найден в исходном,
        // печатам сообщение об ошибке
        if (found == 0) {
            printf("Элементы отсортированного массива не совпадают с элементами изначального массива\n");
            free(checked);
            return;
        } else
            found = 0;
    }
    // Проверяем, правильно ли отсортированы элементы
    for (int i = 1; i < n; ++i) {
        if (sorted[i] < sorted[i - 1]) {
            printf("Элементы отсортированы в неправильном порядке\n");
            break;
        }
    }
    free(checked);
}

static void print(int *arr, int n) {
    for (int i = 0; i < n; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void) {
    int n = 0;
    if (scanf("%d", &n) != 1) {
        printf("Input error");
        return 400;
    };
    srand(time(0));
    for (int i = 1; i <= 4; ++i) {
        if (i == 1) {
            printf("-----------ЭЛЕМЕНТЫ УЖЕ УПОРЯДОЧЕНЫ-----------\n");
        } else if (i == 2) {
            printf("-----------ЭЛЕМЕНТЫ УПОРЯДОЧЕНЫ В ОБРАТНОМ ПОРЯДКЕ-----------\n");
        } else if (i == 3 || i == 4) {
            printf("-----------РАССТАНОВКА ЭЛЕМЕНТОВ СЛУЧАЙНА-----------\n");
        }

        int *a = (int *) malloc(sizeof(int) * n);
        gen(n, a, i);
        printf("Исходный массив:\n");
        print(a, n);

        int *copy1 = (int *) malloc(sizeof(int) * n);
        int *copy2 = (int *) malloc(sizeof(int) * n);
        memcpy(copy1, a, n * sizeof(int));
        memcpy(copy2, a, n * sizeof(int));

        selection_sort(n, copy1);
        printf("Массив после сортировки выбором:\n");
        print(copy1, n);
        printf("Перестановок и сравнений в сортировке методом простого выбора соответственно: %d, %d\n", prms, cmps);
        cmps = 0;
        prms = 0;
        test(a, copy1, n);

        shell_sort(n, copy2);
        printf("Массив после сортировки Шелла:\n");
        print(copy2, n);
        printf("Перестановок и сравнений в сортировке методом Шелла: %d, %d\n", prms, cmps);
        cmps = 0;
        prms = 0;
        test(a, copy2, n);

        free(a);
        free(copy1);
        free(copy2);
        printf("\n");
    }
    return 0;
}