ALDS1_6_A: Counting Sort

いわゆるバケツソート
原理は知ってた

解説はA,Bが1オリジンになってますが
なんかA[0]とかB[0]が使われてないのが気持ち悪いので
0番目から詰めました

def counting_sort(A, k):
    B = [0] * len(A)
    C = [0] * k

    for a in A:
        C[a] += 1

    for i in range(1, k):
        C[i] += C[i - 1]

    for a in reversed(A):
        B[C[a] - 1] = a
        C[a] -= 1

    return B

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(*counting_sort(A, 10001))

main()

最後、Bを作るところはなんで後ろから見てるんだと思いましたが
（実際reversedしなくてもソートは成功するし）
そうしないとStableにならないんですね
なるほどCを

いったん累積にしてからやるのはこれで効率いいのかな
なんか頭いいことしてるような気はするんだけど
普通にやってもいいような気も

ところでpep8でフォーマットするようにしたので実際のソースは
関数と関数の間が２行空くようになりました
どうも間延びしてるように見えて好きになれませんね
慣れの問題かもしれませんが