【アルゴリズム】ヒープソート|基本情報技術者 科目B対策

 

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

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

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

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

 

 

目次

 

 

ソート(整列)とは??

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

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

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

 

<ソートアルゴリズム例>

・単純交換ソート(バブルソート

・単純選択ソート

クイックソート

ヒープソート  等

 

 

ヒープソートとは??

ヒープソートとは、「選択ソートの応用的なアルゴリズムであり、整列していないデータを木構造を用いて整列させる」整列手順・ソートアルゴリズムのことを指します。

そもそもヒープ(累積)とは、親の値が子の値以上である条件を持っている完全2分木のことを言います。

 

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

1.整列していないデータ列から要素を取り出し、順にヒープに追加する。

2.ルート(最大値または最小値)を取り出し、整列済みリストに追加する。

 すべての要素を取り出すまで繰り返し。

 

 

どんなときに使う?

ヒープソートはソートが高速であり、かつ、マージソート等に比べてメモリの使用量が少ないです。

そのため、データ数が多い場合に強みを発揮します。

ただ、単純選択ソートや単純挿入ソートに比べるとアルゴリズムが少し複雑で難しいというデメリットもあります。

なお、クイックソートと同様に安定していないソートになります。

 

 

ヒープソートの実装例(プログラム)

実装例は下記です。

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

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

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

 

<実装例>

import java.util.*;

class Main {
    //a[idex1]とa[idex2]の値を交換(コメント)
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    //ヒープ化(コメント)
    static void heap(int[] a, int left, int right){
        int tmp = a[left];
        int child;
        int parent;
        
        for(parent=left; parent<(right+1)/2; parent=child){
            int pl = parent *2 + 1;
            int pr = pl + 1;
            child = (pr<=right&&a[pr]>a[pl]) ? pr : pl;
            if(tmp >= a[child]){break;}
            a[parent] = a[child];    
        }
        a[parent] = tmp;    
    }    
        
    //ヒープソートのプログラム(コメント)
    static void heapsort(int[] a, int n){
        for(int i=(n-1)/2; i>=0; i--){
            heap(a, i, n-1);
        }    
        for(int i=(n-1); i>0; i--){
            swap(a, 0, i);
            heap(a, 0, n-1);
        }    
    }

    public static void main(String[] args) throws Exception {
        int[] data = {1, 4, 3, 7, 5, 2, 6};
        heapsort(data, data.length);

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

 

 

 

まとめ

ソートの問題に限らず、基礎知識があると問題となっているプログラムに既視感も出て、解きやすくなると考えています!

 

Web上で実際にプログラムを動かすことができるサイトがあります。色々プログラムをいじってみましょう!

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

 

こちらのサイトはjava以外にも対応しています。他の言語で試しても動かすことができます。

アルゴリズムと言われると難しく感じる方もいるかもしれません。ただ、順を追っていけばそこまで難しい話ではないです。まずは触ってみて動きを見てみてはいかがでしょうか。