Implementation (Part 1)

Coddyの「Radix Sort - DSAシリーズ」コースのレッスン 5/9。

基数ソートを、その核心となる操作から順に構築していきます。

チャレンジ

中級

基数ソート（Radix Sort）の各パスは、単一の桁に対する安定な計数ソート（stable counting sort）です。まずはそれを作成しましょう。

非負整数の配列 arr と位取りの値 exp（1の位なら 1、10の位なら 10、100の位なら 100...）を受け取り、桁の数値 (x / exp) % 10 に基づいてソートされた新しい配列を返す、countingSortByDigit という名前の関数を記述してください。このソートは安定的である必要があります。つまり、同じ桁の数値を持つ要素は、元の順序を維持しなければなりません。

例えば、countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) は [170, 90, 2, 802, 24, 45, 75, 66] を返します（1の位でソートされています）。

自分で試してみよう

#include <stdlib.h>

int* countingSortByDigit(int* arr, int arr_size, int exp, int* returnSize) {
    // ここにコードを記述してください
    *returnSize = arr_size;
    return arr;
}

腕試し

このレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。

Radix Sort - DSAシリーズのすべてのレッスン

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2