カウントソート手順アニメーション

data 左から順に出現回数を数える

counts 値ごとの出現頻度

累積counts 左から順に加算した累積和

tmp

phase 初期化 i - 現在値 - counts対象 - 出現回数 0 累積値 0 配置先 - 配置済み 0 残りステップ 0

通常

現在注目

対象counts

tmpに配置済み

赤: 更新された値

配列：対象は 1以上4以下の整数を6個

速度 1.00x

カウントソートのコード1回目 に counts へ出現回数を集計し、2回目 に累積和へ変換し、3回目 に data を後ろから見て tmp を作ります。
1def count_sort(data):
2  counts = [0 for _ in range(5)]
3  for x in data:
4    counts[x] += 1
5  cumulative = counts[:]
6  for value in range(1, 5):
7    cumulative[value] += cumulative[value - 1]
8  tmp = [None] * len(data)
9  for x in reversed(data):
10    cumulative[x] -= 1
11    tmp[cumulative[x]] = x
12  return tmp

              初期状態
            

              counts の状態
[0, 0, 0, 0, 0]
              累積counts の状態
[0, 0, 0, 0, 0]
              tmp の状態
[_, _, _, _, _, _]
            