#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

/*
v[0] ... v[ n-1 ]を昇順にソート
*/
void shellsort(int v[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            for (int j = i - gap; j >= 0 && v[j] > v[j + gap]; j -= gap) {
                int temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
        }
    }
}


/*
シェルソートの検証
*/
int main()
{
    srand((unsigned int)time(NULL));
    int arr[100];
    cout <<  "ソート前" << endl;
    for (auto& v : arr) {
        v = rand() % 100;
        cout << v << ",";
    }
    cout << endl;
    shellsort(arr,100);
    cout << "ソート後" << endl;
    for (auto v : arr) {
        cout << v << ",";
    }
    cout << endl;
    return 0;
}

ソート前
54,4,60,13,67,78,24,66,76,28,53,91,59,34,69,7,9,32,8,61,
73,15,58,82,31,81,54,29,36,53,96,82,1,67,16,47,70,52,96,
60,36,94,30,49,0,31,23,17,98,43,59,69,62,58,23,62,26,2,
94,71,56,85,59,58,17,75,31,85,82,35,34,76,50,26,92,1,93,
0,12,35,24,45,33,59,80,55,4,3,71,26,57,36,20,76,44,7,91,79,38,67,
ソート後
0,0,1,1,2,3,4,4,7,7,8,9,12,13,15,16,17,17,20,23,23,24,24,
26,26,26,28,29,30,31,31,31,32,33,34,34,35,35,36,36,36,38,
43,44,45,47,49,50,52,53,53,54,54,55,56,57,58,58,58,59,59,
59,59,60,60,61,62,62,66,67,67,67,69,69,70,71,71,73,75,76,
76,76,78,79,80,81,82,82,82,85,85,91,91,92,93,94,94,96,96,98,