Pseudo Code
Coddyの「カウンティングソート - DSAシリーズ」コースのレッスン 4/9。
countingSort(array):
max = largest value in array
count = array of (max + 1) zeros
for each x in array: # カウントフェーズ
count[x] += 1
result = [] # 再構築フェーズ
for v from 0 to max:
repeat count[v] times:
append v to result
return result- count[v] は値
vをインデックスとして使用するため、値の範囲によってカウント配列のサイズが決まります。 - カウントフェーズ は1回のパスですべての値を集計します。
- 再構築フェーズ は各値を正しい回数だけ昇順に出力し、ソートされた配列を生成します。
自分で試してみよう
このレッスンにはコードチャレンジは含まれていません。
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
カウンティングソート - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity