【アルゴリズム】度数（分布数え上げ）ソート｜基本情報技術者科目B対策

2023年4月から基本情報技術者の試験制度が変更されたものの科目B（旧：午後問題）の重要さは変わりません。

出題方式は「多肢選択式」で以前と同じですが、データ構造及びアルゴリズムが8割、情報セキュリティが2割の割合で出題される点が大きく変わっています。

合格基準点は600点以上/1000点満点中、つまり6割以上取れれば合格になります。

そんな科目Bのデータ構造及びアルゴリズムについて、基本となるソートの問題について考えてみましょう。

ソート（整列）とは？？
度数ソートとは？？
どんなときに使う？
度数ソートの実装例（プログラム）
まとめ

ソート（整列）とは？？

ソートとは、複数のデータが並んだ列を、何らかの順序に基いて順番通りになるよう並べ替える(整列させる)こと。
数値を大きい順または小さい順に並べたり、文字をアルファベット順や五十音順に並べたり、日時を古い順または新しい順に並べ替えることが該当する。

また、コンピュータによるデータ処理でソート（整列）手順を定式化したアルゴリズムをソートアルゴリズムと言っています。

ソートアルゴリズムにも種類があり、場面に応じた使い分けが必要です。

＜ソートアルゴリズム例＞

・単純交換ソート（バブルソート）

・単純選択ソート

・クイックソート

・ヒープソート　　等

度数ソートとは？？

度数（分布数え上げ）ソートとは、「要素の大小を比較することなく高速にソートを行う」整列手順・ソートアルゴリズムのことを指します。

そもそも度数ソートは比較の必要がありません。

例えば、配列を整列させる手順は下記のようになる。

１．キー(配列aのデータ)を数え上げるための配列cと

　ソートのための作業用配列bを用意します。

２．配列cを用いて、度数分布表を作成する。

　配列aのデータの出現頻度を数えた値が配列ｃに入る。　

３．配列ｃを用いて、キーの累積度数分布表を作成し、求める。
４．累積度数分布表に基づいて配列aから配列bにデータをコピーする。

どんなときに使う？

度数ソートは制限はありますが、使い道次第で有用なソート手法です。

度数ソートはデータの大小比較は行いませんが、対象データの値の範囲を予め明確にしておく必要があります。

また、キーを数えるための配列（領域）や結果を入力するための配列（領域）が別途必要になります。そのため、マージソートと同様に大きな範囲のデータを取り扱うには不向きであり、場合によっては物理的に不可能になります。

ただ、安定的なソートであること、データを比較しないことによる処理の高速さはメリットと言えます。

度数ソートの実装例（プログラム）

実装例（昇順のプログラム）は下記です。

Web上で実際にプログラムを動かすことができるサイトがあります。

色々プログラムをいじってみましょう！

Online PHP/Java/C++... editor and compiler | paiza.IO

＜実装例＞

import java.util.*;

class Main {

    //度数ソートのプログラム（コメント）※負の値はないものとする。
    static void sort(int[] a, int k, int max) {
        int[] f = new int[max + 1]; // 累積度数
        int[] b = new int[k];       // 作業用配列
        for (int i = 0; i < k; i++) {f[a[i]]++;}
        for (int i = 1; i <= max; i++) {f[i]+=f[i-1];}
        for (int i = k-1; i >= 0; i--) {b[--f[a[i]]]=a[i];}
        for (int i = 0; i < k; i++) {a[i]=b[i];}
    }

    public static void main(String[] args) throws Exception {
        int[] data = {1, 4, 3, 7, 5, 2, 6}; 
        int m = 0;
        
        //最大値mを求める
        for(int i=0;i < data.length;i++) {
            m = data[i] > m ? data[i] : m;
        }
        
        sort(data, data.length, m);

        //配列を表示させるプログラム（コメント）
        for(int i = 0; i < data.length; i++) { 
            System.out.println(data[i]);
        }
    }
}