【アルゴリズム】マージソート｜基本情報技術者科目B対策

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

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

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

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

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

ソート（整列）とは？？

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

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

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

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

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

・単純選択ソート

・クイックソート

・ヒープソート　　等

マージソートとは？？

マージソートとは、「データ列を前半部分と後半部分の2つに分けて、それぞれをソートしたものをマージ（併合）する作業を繰り返す」整列手順・ソートアルゴリズムのことを指します。

例えば、リストを昇順に整列させる手順の場合、下記のようになる。

１．データ列を一つの要素になるまで分割していく

２．手順1で分割したデータを2個づつ昇順になるように整列していく

３．手順2の処理を繰り返してもともとのデータ列と同じ大きさのデータ列

　になるまで処理を繰り返す

どんなときに使う？

マージソートは、名の通りマージを行います。

処理の関係上、より大きな作業用の配列を用意する必要があります。そのため、配列のソートには不向きです。

ただ、クイックソートとは違い安定したソートであり、メリットと言えるでしょう。

マージソートの実装例（プログラム）

実装例は下記です。

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

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

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

＜実装例＞

import java.util.*;

class Main {
    
    static int[] box;
    
    //マージソートのプログラム（コメント）
    static void _merge(int[] a, int left, int right){
        if(left < right){
            int i;
            int center = (left + right)/2;
            int p = 0;
            int j = 0;
            int k = left;
            
            _merge(a, left, center);
            _merge(a, center+1, right);
            
            for(i=left; i <= center; i++){
                box[p++]=a[i];}
            while(i<=right && j<p){
                a[k++] = (box[j]<=a[i]) ? box[j++] : a[i++];}
            while(j<p){
                a[k++] = box[j++];}
        }    
    }
    
    static void merge(int[] a, int n){
        box = new int[n];
        _merge(a, 0, n-1);
    }
    
    public static void main(String[] args) throws Exception {
        int[] data = {1, 4, 3, 7, 5, 2, 6, 8};
        merge(data, data.length);
        
        //配列を表示させるプログラム（コメント）
        for(int i = 0; i < data.length; i++) {
            System.out.println(data[i]);
        }
    }
}