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でフォーマットするようにしたので実際のソースは
関数と関数の間が2行空くようになりました
どうも間延びしてるように見えて好きになれませんね
慣れの問題かもしれませんが