#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define SWAP_INT(a,b) {a = a ^ b; b = a ^ b; a = a ^ b;}

void init_int_array(int data[], int n)
{
    for (int i = 0; i < n; ++i)
        data[i] = rand()%10;
}

void print_int_array(int data[], int size)
{
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", data[i]);
    }
    printf("\n");
}

int check(int data[], int data_backup[], int size)
{
    int sum = 0, sum2 = 0;
    int i;
    for (i = 0; i < size-1; ++i)
    {
        sum += data[i];
        sum2 += data_backup[i];
        if (data[i+1] < data[i])
            return 0;
    }
    sum += data[i];
    sum2 += data_backup[i];
    if (sum != sum2)
        return 0;
    return 1;
}

void diminishing_increment(int data[], int length)
{
    int i, k;
    int increment;
    int temp;

    for (increment = length / 2; increment >= 1; increment/=2)
    {
        for (i = increment; i < length ; ++i)
        {
            temp = data[i];
            for (k = i-increment; k >= 0 && data[k] > temp; k-=increment)
            {
                data[k+increment] = data[k];
            }
            data[k+increment] = temp;
        }
    }
}

int main(void)
{
    // 目测一次排序结果
    int arr[16];
    srand(time(NULL));
    init_int_array(arr, sizeof(arr)/sizeof(arr[0]));

    print_int_array(arr, sizeof(arr)/sizeof(arr[0]));
    diminishing_increment(arr, sizeof(arr)/sizeof(arr[0])); //
    print_int_array(arr, sizeof(arr)/sizeof(arr[0]));


    // 多次验证排序结果是否正确
    for(int i = 0; i < 300; ++i)
    {
        int data[15], data_backup[15];
        init_int_array(data, sizeof(data)/sizeof(data[0]));
        memcpy(data_backup, data, sizeof(data_backup));
        diminishing_increment(data, sizeof(data)/sizeof(data[0]));
        if (!check(data, data_backup, sizeof(data)/sizeof(data[0])))
        {
            printf("error:\nOriginal data:\n");
            print_int_array(data_backup, sizeof(data)/sizeof(data[0]));
            printf("Sorted data:\n");
            print_int_array(data, sizeof(data)/sizeof(data[0]));
            return EXIT_FAILURE;
        }
    }
    printf("check\n");

    return EXIT_SUCCESS;
}