#/***********************************************************
#    shelsort.rb -- Shellソート
#***********************************************************/

def shellsort(n, a)  # a..n-1] を昇順に 
    h = 13
    while (h < n); h = 3 * h + 1; end
    h /= 9
    while (h > 0) 
        for i in h...n
            x = a[i]
            j = i - h; while(j >= 0 && a[j] > x)
                a[j + h] = a[j]
                j -= h
            end
            a[j + h] = x
        end
        h /= 3
    end
end

N = 20
a = []

printf("Before:")
for i in 0...N
    a[i] = (rand * 100 + 1).to_i
    printf(" %2d", a[i])
end
printf("\n")

shellsort(N, a)

printf("After: ")
for i in 0...N; printf(" %2d", a[i]); end
printf("\n")

exit 0