基数ソートを理解する

基数ソートは桁ごとに安定な整列を繰り返す方法です。対象値の表現、負数、基数、各段階の安定性を定めます。

基数ソートは桁ごとに安定な整列を繰り返す方法です。対象値の表現、負数、基数、各段階の安定性を定めます。仕組みだけでなく、検証方法と運用上の注意も具体例で確認します。

基本の考え方

基数ソートは桁ごとに安定な整列を繰り返す方法です。対象値の表現、負数、基数、各段階の安定性を定めます。

計算量だけでなく入力条件、重複値、空データ、最悪ケースを確かめます。組み込み用途ではメモリ上限と実行時間を実測し、標準ライブラリの利用も検討してください。

手元のPython環境に貼り付ける前に、使用しているPythonの版と対象ライブラリの対応を確認してください。

def digit_at(value, place):
    return (value // place) % 10

values = [170, 45, 75, 90]
print([digit_at(value, 10) for value in values])

非負整数を桁ごとに安定整列する処理を完成させ、各パスの配列を表示してください。