#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <Windows.h>
#include <iostream>


//сортировка методом Шелла
void ShellSort(int n, int arr[])
{
    int i, j, step;
    int tmp;
    for (step = n / 2; step > 0; step /= 2)
        for (i = step; i < n; i++)
        {
            tmp = arr[i];
            for (j = i; j >= step; j -= step)
            {
                if (tmp < arr[j - step])
                    arr[j] = arr[j - step];
                else
                    break;
            }
            arr[j] = tmp;
        }
}

int main()
{
    setlocale(LC_ALL, "Russian");
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    //ввод number
    int number;

    printf("Введіть потрібну кількість масиву N: ");

    if (number > 0) {
        scanf_s("%d", &number);
    }
    else {
        printf("Будь ласка введіть тільки числа від 1 до 100");
    }

    //выделение памяти под массив
    int* mass;
    mass = (int*)malloc(number * sizeof(int));

    //ввод элементов массива
    printf("Введіть елементи масиву:\n");
        for (int i = 0; i < number; i++)
            scanf_s("%d", &mass[i]);
    
   
    //сортировка методом Шелла
    ShellSort(number, mass);

    //вывод отсортированного массива на экран
    printf("Відсортований масив:\n");
    for (int i = 0; i < number; i++)
        printf("%d ", mass[i]);
    printf("\n");

    //освобождение памяти
    free(mass);
    _getch();

    return 0;
}

#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <Windows.h>
#include <iostream>

//сортировка методом Шелла
void ShellSort(int n, int arr[])
{
    int i, j, step;
    int tmp;
    for (step = n / 2; step > 0; step /= 2)
        for (i = step; i < n; i++)
        {
            tmp = arr[i];
            for (j = i; j >= step; j -= step)
            {
                if (tmp < arr[j - step])
                    arr[j] = arr[j - step];
                else
                    break;
            }
            arr[j] = tmp;
        }
}

int main()
{
    //ввод number
    int number;
    printf("Enter desired amount of array N: ");
    scanf_s("%d", &number);

    //выделение памяти под массив
    int* mass;
    mass = (int*)malloc(number * sizeof(int));

    //ввод элементов массива
    printf("Input the array elements:\n");
    for (int i = 0; i < number; i++)
        scanf_s("%d", &mass[i]);

    //сортировка методом Шелла
    ShellSort(number, mass);

    //вывод отсортированного массива на экран
    printf("Sorted array:\n");
    for (int i = 0; i < number; i++)
        printf("%d ", mass[i]);
    printf("\n");

    //освобождение памяти
    free(mass);
    _getch();

    return 0;
}