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

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

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

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

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

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

ソート（整列）とは？？

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

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

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

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

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

・単純選択ソート

・クイックソート

・ヒープソート　　等

クイックソートとは？？

クイックソートとは、「もっとも高速なソートのアルゴリズムの一つとしている」整列手順・ソートアルゴリズムのことを指します。

名の通り、処理が高速なソート方法です。

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

１．整列されていないデータ列の中から適当な基準値を決定する

２．手順1で設定した基準値でグループ分けを行う

　「基準値より小さい値」と「基準値より大きい値」の2つのグループに分ける

３．手順2で分けた各グループ内で適当な基準値を決定する。

４．手順3で設定した基準値でグループ分けを行う

　「基準値より小さい値」と「基準値より大きい値」の2つのグループに分ける

５．手順1〜4を繰り返して整列を行う

どんなときに使う？

クイックソートは、データ列を大小などで順序通りに並び替えるアルゴリズムです。

いろいろなソート方法がありますが、まずはクイックソートを検討すれば間違いないでしょう！

ただ、安定ソートではないという点がデメリットになり、他のソート方法を考えるきっかけになります。

クイックソートの実装例（プログラム）

実装例は下記です。

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 quick(int[] a, int pl, int pr){
        int left = pl;
        int right = pr;
        int x = a[(left+right)/2];
    
        do{
            while(a[left] < x) left++;
            while(a[right] > x) right--;
            if(left <= right){
                swap(a,left++,right--);
            }    
        }while(left <= right);
        
        if(pl < right){quick(a,pl,right);}
        if(left < pr){quick(a,left,pr);}
    }
    
    public static void main(String[] args) throws Exception {
        int[] data = {1, 4, 3, 7, 5, 2, 6};
        quick(data, 0, data.length-1);
        
        //配列を表示させるプログラム（コメント）
        for(int i = 0; i < data.length; i++) {
            System.out.println(data[i]);
        }
    }
}