31-1

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

void sort(int *ms, int k)
{
    int i, j, n;
    int gap; // шаг сортировки
    int flg; // флаг окончания этапа сортировки
    for(gap = k/2; gap > 0; gap /= 2)
        do
        {
            flg = 0;
            for(i = 0, j = gap; j < k; i++, j++)
                if(*(ms+i) > *(ms+j)) // сравниваем отстоящие на gap элементы
                {
                    n = *(ms+j);
                    *(ms+j) = *(ms+i);
                    *(ms+i) = n;
                    flg = 1; // есть ещё нерассортированные данные
                }
        }
        while (flg);   // окончание этапа сортировки
}

int main()
{
    printf("Start\n");

    long *a;
    int n;

    printf("Enter n: ");
    scanf("%d", &n);

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

    for (int i = 0; i < n; i++){
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }

    sort(a, n);

    for(int i = 0; i < n; i++){
        printf("%d, ", a[i]);
    }

    return 0;
}