情報処理技法（Javaプログラミング）II 第15回

ソート（5）

テキストpp.234--239を参照。

課題15

度数ソートの応用に、基数ソート（radix sort）があります。

度数ソートは高速なアルゴリズムですが、例えば入力が0以上999以下ならば、最悪の場合、要素数1,000の配列を用意しなくてはいけません。 基数ソートは、以下のように3回ソートしますが、要素数10の配列を用意するだけで済みます。

1. 1の位をキーとして（1の位だけを見て）度数ソートする。
2. 10の位をキーとして（10の位だけを見て）度数ソートする。
3. 100の位をキーとして（100の位だけを見て）度数ソートする。

例えば、配列（説明のためゼロ詰めします）

の1の位をキーとしてソートすると、

となり、次に10の位をキーとしてソートすると、

となり、最後に100の位をキーとしてソートすると、

となります。

p.238のList 6-18を参考にして、入力が0以上999以下と仮定して、基数ソートを行うプログラムを作成してください。

• メソッド countingSort の定義の引数 max を削除し、代わりに位を意味する exp に置き換えます。
• メソッド定義の中の変数 max は9に置き換えます（2か所）。
• メソッド定義の中の式 f [ a [ i ]]は f [ a [ i ] / exp % 10]に置き換えます（2か所）。
• メソッド countingSort の呼出しは、 countingSort ( x , nx , max )を削除し、代わりに countingSort ( x , nx , 1)と countingSort ( x , nx , 10)と countingSort ( x , nx , 100)に置き換えます。

import java.util.Scanner;

class CountingSort2 {
    static void countingSort(int[] a, int n, int exp) {
        
        
    }
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        
    }
}

PS ...\Desktop\java2>  & ... 'CountingSort2'
基数ソート
要素数：7
x[0]：22
x[1]：5
x[2]：11
x[3]：32
x[4]：120
x[5]：68
x[6]：70
昇順にソートしました。
x[0]＝5
x[1]＝11
x[2]＝22
x[3]＝32
x[4]＝68
x[5]＝70
x[6]＝120
PS ...\Desktop\java2>

余力がある人は、入力が0以上だが999以下とは限らないと仮定して、基数ソートを行うプログラムを作成してください。 例えば、for文を (int exp = 1; exp <= max; exp *= 10) として、メソッド countingSort を繰り返し呼び出してください。

import java.util.Scanner;

class CountingSort3 {
    static void countingSort(int[] a, int n, int exp) {
        
        
    }
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        
    }
}

PS ...\Desktop\java2>  & ... 'CountingSort3'
基数ソート
要素数：7
x[0]：2200
x[1]：500
x[2]：1100
x[3]：3200
x[4]：12000
x[5]：6800
x[6]：7000
昇順にソートしました。
x[0]＝500
x[1]＝1100
x[2]＝2200
x[3]＝3200
x[4]＝6800
x[5]＝7000
x[6]＝12000
PS ...\Desktop\java2>

完成したら、答案（Javaプログラム）をメールで提出してください。 差出人は大学発行のメール・アドレス（学生番号@cis.twcu.ac.jp）とし、宛先はkonishi@cis.twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（1月16日）を明記してください。

提出期限

すべてのレポートの提出期限を2026年1月29日（木）とします。

参考文献

• 柴田望洋『新・明解Javaで学ぶアルゴリズムとデータ構造 第2版』SBクリエイティブ、2020