ALDS1_2_D: Shell Sort

ソート自体は擬似コードが書いてあるので移すだけ
挿入ソートだと遠く離れた要素を入れ替えたくてもひとつずつずらしていくので
入れ替えの数が増えてしまいますがシェルソートでは間隔を空けて入れ替えるので
入れ替えが少なくてすむという寸法
自分で考えるのは入れ替える間隔の配列

#! /usr/local/bin/python3
# coding: utf-8

def insertion_sort(A, g):
    global cnt
    for i in range(g, len(A)):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = v

def shell_sort(A):
    global cnt, G
    for g in G:
        insertion_sort(A, g)

n = int(input())

G = [1, 2]
for i in range(2, 100):
    g = G[i - 1] + G[i - 2]
    G.append(g)
G = list(filter(lambda x: x<=n, G))
G.reverse()

cnt = 0
A = []
for i in range(n):
    A = A + [int(input())]

shell_sort(A)

print(len(G))
print(" ".join([str(i) for i in G]))
print(cnt)
[print(i) for i in A]

データ数100万でTLE
ていうか長すぎて通信切れたかサーバ応答なくなったかと思ったよ
42.00sかかったって
ていうか

Time Limit : 6 sec

って出てるからこの基準だとデータ数10万でもうだめなはずなんだけど
22.33sかかってるのにAC
どういうこと
まあいいけど

数列Gがよくないのかな
なんとなくフィボナッチ数列かなーと思って使ったけど
g_n+1 = 3g_n + 1 がいいらしい
もっと離れてていいんだな

G = [1]
for i in range(1, 100):
    g = 3 * G[i - 1] + 1
    if g > n:
        break
    G.append(g)
G.reverse()

でもやっぱりデータ数100万だと42.00sでTLE
42秒がリミットで切られてるのかな
データ量10倍で時間2倍ってことはないだろうし
でも10万でも21.93sかかっててほとんど違いがない
あんまり影響ないのか？

データ数10万で比べてみる

フィボナッチ版実行結果

$ time (ALDS1_2_D.py < in.txt > out.txt)
real    0m36.617s
user    0m34.522s
sys     0m1.926s
$ head out.txt
24
75025 46368 28657 17711 10946 6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1
2746144
0
1

3g_n + 1版

$ time (ALDS1_2_D.py < in.txt > out.txt)
real    0m36.650s
user    0m34.620s
sys     0m1.863s
[PCAD][master *%]$ head out.txt
11
88573 29524 9841 3280 1093 364 121 40 13 4 1
2951754
0
1

思った以上に差がなかった
いや、よくみたらフィボナッチ版の方が入れ替え回数すくないやん
どういうこと

まあ10万まで合ってるんだしいいか・・・
Web Board見てみたらRubyやPythonだとTLEになるって言ってる人がいる
自分だけじゃないのか