Implementation (Part 2)
Coddyの「Radix Sort - DSAシリーズ」コースのレッスン 6/9。
次に、各桁の位置に対して一度ずつ、桁ごとのカウンティングソートを実行します。
チャレンジ
中級それでは、すべてを組み合わせて完全なアルゴリズムを完成させましょう。
非負整数の配列を受け取り、各桁の位置に対して桁ごとのカウンティングソートを一度ずつ使用して、昇順にソートされた配列を返す radixSort という名前の関数を作成してください。
最大値を見つけ、次に exp = 1, 10, 100, ... とループさせます。その桁の値が存在する限り、countingSortByDigit を実行し、exp を10倍していきます。
前のレッスンで作成したカウンティングソートをヘルパー関数として再利用してください。
自分で試してみよう
#include <stdlib.h>
int* radixSort(int* arr, int arr_size, int* returnSize) {
// ここにコードを書いてください
*returnSize = arr_size;
return arr;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
Radix Sort - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity