Implementation (Part 2)
Coddyの「カウンティングソート - DSAシリーズ」コースのレッスン 6/9。
次に、すべての値をカウントし、順番に配列を再構築します。
チャレンジ
簡単それでは、これらすべてを組み合わせて完全なアルゴリズムを完成させましょう。
非負整数の配列を受け取り、それを昇順にソートして返す countingSort という名前の関数を作成してください。
最大値を見つけ、サイズが max + 1 のカウント配列を作成し、すべての要素を集計します。その後、各値 v を出力に count[v] 回ずつ、小さい順から大きい順へと書き込むことで、結果を再構築します。
前のレッスンで学んだカウントの考え方を再利用してください。
自分で試してみよう
#include <stdlib.h>
int* countingSort(int* arr, int arr_size, int* returnSize) {
// ここにコードを記述してください
*returnSize = arr_size;
return arr;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
カウンティングソート - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity