アルゴリズムと計算量　－情報処理シンプルまとめ

　基本情報技術者試験など情報処理技術者試験を受験する方にとっては必須の，アルゴリズムと計算量についてシンプルにまとめています。はじめに計算量について説明し，その後，整列（ソート）（基本交換法（隣接交換法，バブルソート），基本選択法（選択ソート），基本挿入法（挿入ソート），シェルソート（改良挿入法），クイックソート，マージソート，ヒープソート），探索（線形探索（番兵を使用した方法），2分探索，ハッシュ法（データの追加，データの探索）），文字列に対する処理（文字列の探索）ついて説明します。擬似言語，Python，C#の例を載せていますので，（時間があれば）実際にコーディングをしながら進めてみてください。

アルゴリズム

　アルゴリズムとは，ある問題を解く手順や計算方法のことをいいます。同じ処理結果が得られる場合でも，コンピューターに負荷をかけず，高速で，無駄なリソースを使わないアルゴリズムを採用することが重要です。

　実際に，コーディングをしながら進めたい場合は，先に，開発環境を整えてください。

計算量

　アルゴリズムの計算量とは，処理内容の効率性を大雑把に評価するもので，O（オーダー）という単位を使用します。

※ ここでは，時間計算量（実行時間を対象とする計算量）について説明する

例）入力データn件，実行回数n回の場合の計算量：O(n)

文字列型の配列: x ← { "おはよう", "こんにちは", "こんばんは" }
整数型: n ← 配列xの要素数
for ( iを1からnまで１ずつ増やす )
　x[i]を出力
endfor

※ 1行目の実行回数：1回，2行目の実行回数：1回，3行目の実行回数：n回，4行目の実行回数：n回 ⇒ 全体の実行回数：2n＋2回 ⇒ 計算量は，処理の効率性を大雑把に評価するものなので，O(n)となる

※ O(n)とは，処理件数nに計算量が比例していることを意味している

例）入力データm×n件，実行回数m×n回の場合の計算量：O(mn)

整数型の配列: k ← { {11, 12, 13, 14}, {21, 22, 23, 24}, {31, 32, 33, 34} }
整数型: m ← 配列kの行数
整数型: n ← 配列kの列数
for ( iを1からmまで１ずつ増やす )
　for ( jを1からnまで１ずつ増やす )
　　k[i][j] の値をコンマ区切りで出力する
　endfor
　改行を出力する
endfor

※ 1行目の実行回数：1回，2行目の実行回数：1回，3行目の実行回数：1回，4行目の実行回数：m回，5行目の実行回数：m×n回，6行目の実行回数：m×n回，8行目の実行回数：m回 ⇒ 全体の実行回数：2mn＋2m＋3回 ⇒ 計算量は，処理の効率性を大雑把に評価するものなので，O(mn)となる

※ 入力データn²件，実行回数n²回の場合の計算量はO(n²)となる

入力データがn件で，

実行回数がn回の場合の計算量＝O(n)

実行回数が3n＋2回の場合の計算量＝O(n)

実行回数が12n²＋3n＋5回の場合の計算量＝O(n²)

実行回数がlog₂n2の場合の計算量＝O(log₂n)

※ 計算量は，最高次の項以外は無視し，さらに，最高次の係数も無視して表す

※ a^x＝b ⇔ x＝log_ab（aを底，bを真数，xをaを底とする対数という）

計算量の大小関係

　計算量の大小関係は，次のようになります。

O(1) ＜ O(log₂n) ＜ O(n) ＜ O(nlog₂n) ＜ O(n²) ＜ O(2ⁿ) ＜ O(n!)

整列（ソート）

基本交換法（隣接交換法，バブルソート）

　基本交換法は，隣り合うデータの比較・交換を，範囲を狭めながら繰り返し行い，昇順（または降順）に並べ替えるアルゴリズムです。

※ 未整列データの中で最も小さい（または最も大きい）データが，泡のように（泡が浮き上がるように）移動するので，バブルソートとも呼ばれる

※ 計算量：O(n²)

例）配列aを昇順に整列する

流れ図

※ 計算量（処理の効率性を大雑把に評価するもの）は，ループ1，ループ2の2重ループの部分で評価すればよい ⇒ 入力データn件の場合のループ2の実行回数：約n²回 ⇒ 全体の実行回数：約n²回となり，O(n²)となる

擬似言語

// 主プログラム
〇main()
　整数型の配列：a ← {30, 20, 40, 10}
　bubble_sort (a)

// 副プログラム
○ bubble_sort ( 整数型の配列：arr )
　整数型：temp
　for ( iをarrの長さ－1から1まで１ずつ減らす )
　　for ( jを0からi－1まで１ずつ増やす )
　　　if ( arr[j] ＞ arr[j ＋ 1] )
　　　　temp ← arr[j]
　　　　arr[j] ← arr[j ＋ 1]
　　　　arr[j ＋ 1] ← temp
　　　endif
　　endfor
　 endfor

Python

import numpy as np

# クラスSort
class Sort:
    def __init__(self):
       pass 
    
    def bubble_sort(self, arr: np.array):
        temp: int
        for i in range(len(arr) - 1, 0, -1):
            for j in range(0, i, 1):
                if arr[j] > arr[j + 1]:
                    temp = arr[j]
                    arr[j] = arr[j + 1]
                    arr[j + 1] = temp

# 主プログラム
def main():
    sort: Sort = Sort()
    a: np.array = np.array([30, 20, 40, 10])
    sort.bubble_sort (a)

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
class Sort {
    public Sort() {}

    public void bubble_sort(int[] arr) {
        int temp;
        for(int i = arr.Length - 1; i > 0; i--) {
            for(int j = 0; j < i; j++) {
                if(arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

class a_001 {
    // 主プログラム
    static void Main(string[] args) {
        Sort sort = new Sort();
        int[] a = new int[]{30, 20, 40, 10};
        sort.bubble_sort (a);
    }
 }

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

基本選択法（選択ソート）

　基本選択法は，未整列データの中で最も小さい（または最も大きい）データを，範囲を狭めながら繰り返し求め，昇順（または降順）に並べ替えるアルゴリズムです。

※ 計算量：O(n²)

例）配列aを昇順に整列する

流れ図

擬似言語

// 主プログラム
〇main()
　整数型の配列：a ← {30, 20, 40, 10}
　 basic_selection_sort (a)

// 副プログラム
○ basic_selection_sort ( 整数型の配列：arr )
　整数型：min, temp
　for ( iを0からarrの長さ－2まで１ずつ増やす )
　　min ← i
　　for ( jをi+1からarrの長さ－1まで１ずつ増やす )
　　　if ( arr[min] > arr[j] )
　　　　min = j
　　　endif
　　endfor
　　temp ← arr[i]
　　arr[i] ← arr[min]
　　arr[min] ← temp
　 endfor

Python

import numpy as np

# クラスSort
class Sort:
    def __init__(self):
       pass 

    def basic_selection_sort(self, arr: np.array):
        min: int; temp: int
        for i in range(0, len(arr) - 1, 1):
            min = i
            for j in range(i + 1, len(arr), 1):
                if arr[min] > arr[j]:
                    min = j
            temp = arr[i]
            arr[i] = arr[min]
            arr[min] = temp

# 主プログラム
def main():
    sort: Sort = Sort()
    a: np.array = np.array([30, 20, 40, 10])
    sort.basic_selection_sort(a)

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
class Sort {
    public Sort() {}

    public void basic_selection_sort(int[] arr) {
        int min, temp;
        for(int i = 0; i < arr.Length - 1; i++) {
            min = i;
            for(int j = i + 1; j < arr.Length; j++){
                if(arr[min] > arr[j]) {
                    min = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

class a_002 {
    // 主プログラム
    static void Main(string[] args) {
        Sort sort = new Sort();
        int[] a = new int[]{30, 20, 40, 10};
        sort.basic_selection_sort (a);
    }
 }

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

基本挿入法（挿入ソート）

　基本挿入法は，未整列データから順にデータを取り出して，整列済みデータの正しい位置にデータを追加するという操作を繰り返し行い，昇順（または降順）に並べ替えるアルゴリズムです。

※ 計算量：O(n²)

例）配列aを昇順に整列する

流れ図

擬似言語

// 主プログラム
〇main()
　整数型の配列：a ← {30, 10, 40, 20}
　 basic_insertion_sort (a)

// 副プログラム
○ basic_insertion_sort ( 整数型の配列：arr )
　整数型：j, temp
　for ( iを1からarrの長さ－1まで１ずつ増やす )
　　j ← i
　　while ( (j > 0) and (arr[j] < arr[j - 1]) )
　　　temp ← arr[j]
　　　arr[j] ← arr[j － 1]
　　　arr[j － 1] ← temp
　　　j ← j － 1
　　endwhile
　 endfor

Python

import numpy as np

# クラスSort
class Sort:
    def __init__(self):
       pass 

    def basic_insertion_sort(self, arr: np.array):
        temp: int; j: int
        for i in range(1, len(arr), 1):
            j = i
            while (j > 0) & (arr[j] < arr[j - 1]):
                temp = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = temp
                j = j - 1

# 主プログラム
def main():
    sort: Sort = Sort()
    a: np.array = np.array([30, 10, 40, 20])
    sort.basic_insertion_sort(a)

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
class Sort {
    public Sort() {}

    public void basic_insertion_sort(int[] arr) {
        int temp, j;
        for(int i = 1; i < arr.Length; i++) {
            j = i;
            while((j > 0) && (arr[j] < arr[j - 1])) {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j = j - 1;
            }
        }
    }
}

class a_003 {
    // 主プログラム
    static void Main(string[] args) {
        Sort sort = new Sort();
        int[] a = new int[]{30, 10, 40, 20};
        sort.basic_insertion_sort (a);
    }
 }

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

シェルソート（改良挿入法）

　シェルソートは，一定の間隔ごとに取り出したデータをそれぞれ並べ替え，間隔を狭めながら，間隔が1になるまで繰り返し，昇順（または降順）に並べ替えるアルゴリズムです。

※ 基本挿入法を改良したアルゴリズム

※ 計算量（平均）：O(n^1.5)程度，最悪の場合：O(n²)

例）配列aを昇順に整列する

流れ図

擬似言語

// 主プログラム
〇main()
　整数型の配列：a ← {20, 40, 10, 30, 15}
　 shell_sort (a)

// 副プログラム
○ shell_sort ( 整数型の配列：arr )
　整数型：w ← arrの長さ ÷ 2
　整数型：i, j, r_cnt, temp
　while ( w ≧ 1 )
　　i ← 0
　　while ( i ＜ w )
　　　j ← 1
　　　while ( i ＋ j × w ＜ arrの長さ )
　　　　r_cnt ← 0
　　　　while ( ( j ＞ 0 ) and ( arr[i ＋ j × w] ＜ arr[i ＋ (j － 1) × w)] ) )
　　　　　temp ← arr[i ＋ j × w]
　　　　　arr[i ＋ j × w] ← arr[i ＋ (j － 1) × w]
　　　　　arr[i ＋ (j － 1) × w] ← temp
　　　　　j ← j － 1
　　　　　r_cnt ← r_cnt ＋ 1
　　　　endwhile
　　　　if ( r_cnt ≠ 0 )
　　　　　j ← j + r_cnt ＋ 1
　　　　else
　　　　　j ← j ＋ 1
　　　　endif
　　　endwhile
　　　i ← i ＋ 1
　　endwhile
　　w ← w ÷ 2
　endwhile

Python

import numpy as np

# クラスSort
class Sort:
    def __init__(self):
       pass 

    def shell_sort (self, arr: np.array):
        w: int = int(len(arr) / 2)
        i: int; j: int; r_cnt: int; temp: int
        while(w >= 1):
            i = 0
            while(i < w):
                j = 1
                while(i + j * w < len(arr)):
                    r_cnt = 0
                    while (j > 0) and (arr[i + (j - 1) * w] >= arr[i + j * w]):
                        temp = arr[i + j * w]
                        arr[i + j * w] = arr[i + (j - 1) * w]
                        arr[i + (j - 1) * w] = temp
                        j = j - 1
                        r_cnt +=1
                    if r_cnt != 0:
                        j = j + r_cnt + 1
                    else:
                        j = j + 1
                i = i + 1
            w = int(w / 2)
    
# 主プログラム
def main():
    sort: Sort = Sort()
    a: np.array = np.array([20, 40, 10, 30, 15])
    sort.shell_sort(a)

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
class Sort {
    public Sort() {}

 public void shell_sort (int[] arr) {
        int w = arr.Length / 2;
        int i, j, r_cnt, temp;
        while(w >= 1) {
            i = 0;
            while(i < w) {
                j = 1;
                while(i + j * w < arr.Length) {
                    r_cnt = 0;
                    while((j > 0) && (arr[i + j * w] < arr[i + (j - 1) * w])) {
                        temp = arr[i + j * w];
                        arr[i + j * w] = arr[i + (j - 1) * w];
                        arr[i + (j - 1) * w] = temp;
                        j = j - 1;
                        r_cnt++;
                    }
                    if(r_cnt != 0){
                        j = j + r_cnt + 1;
                    } else {
                        j = j + 1;
                    }
                }
                i = i + 1;
            }
            w = w / 2;
        }
    }
}

class a_004 {
    // 主プログラム
    static void Main(string[] args) {
        Sort sort = new Sort();
        int[] a = new int[]{20, 40, 10, 30, 15}; 
        sort.shell_sort(a);
    }
 }

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

クイックソート

　クイックソートは，データの中で基準値（ピボット）を選択し，その基準値よりも値の小さいグループと大きいグルーに分け，さらに，それぞれのグループの中で基準値を選択し、その基準値よりも値の小さいグループと大きいグループに分け…，という操作を繰り返し行い，昇順（または降順）に並べ替えるアルゴリズムです。

※ 計算量（平均）：O(n log₂n)，最悪の場合：O(n²)

例）配列aを昇順に整列する

流れ図

擬似言語

// 主プログラム
〇main()
　整数型の配列：a ← {30, 50, 40, 20, 10, 70, 15}
　 quick_sort (a, 0, aの長さ－1)

// 副プログラム
○ quick_sort ( 整数型の配列：arr, 整数型：first, 整数型：last)
　整数型：i ← first
　整数型：j ← last
　整数型：p ← arr[(i ＋ j) / 2]
　整数型：temp
　while ( true )
　　while ( arr[i] ＜ p )
　　　i ← i ＋ 1
　　endwhile
　　while ( arr[j] ＞ p )
　　　j ← j － 1
　　endwhile
　　if ( i ≧ j )
　　　break
　　endif
　　temp ← arr[i]
　　arr[i] ← arr[j]
　　arr[j] ← temp
　　i ← i ＋ 1
　　j ← j － 1
　endwhile
　if ( first ＜ i － 1 )
　　quick_sort (arr, first, i － 1 )
　endif
　if ( last ＞ j ＋ 1 )
　　quick_sort (arr, j ＋ 1, last )
　endif

Python

import numpy as np

# クラスSort
class Sort:
    def __init__(self):
       pass 

    def quick_sort(self, arr: np.array, first:int, last: int):
        i: int = first
        j: int = last
        p: int = arr[int((i + j) / 2)]
        temp: int
        while True:
            while arr[i] < p:
                i += 1
            while arr[j] > p:
                j -= 1
            if i >= j:
                break
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
            i += 1
            j -= 1
        if first < i - 1:
            self.quick_sort(arr, first, i - 1)
        if last > j + 1:
            self.quick_sort(arr, j + 1, last)
    
# 主プログラム
def main():
    sort: Sort = Sort()
    a: np.array = np.array([30, 50, 40, 20, 10, 70, 15])
    sort.quick_sort(a, 0, len(a) - 1)

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
class Sort {
    public Sort() {}

 public void quick_sort(int[] arr, int first, int last) {
        int i = first;
        int j = last;
        int p = arr[(i + j) / 2];
        int temp;
        while(true) {
            while(arr[i] < p) {
                i++;
            }
            while(arr[j] > p) {
                j--;
            }
            if(i >= j) {
                break;
            }
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
        if(first < i - 1) {
            quick_sort(arr, first, i - 1);
        }
        if(last > j + 1) {
            quick_sort(arr, j + 1, last);
        }
    }
}

class a_005 {
    // 主プログラム
    static void Main(string[] args) {
        Sort sort = new Sort();
        int[] a = new int[]{30, 50, 40, 20, 10, 70, 15}; 
        sort.quick_sort(a, 0, a.Length - 1);
    }
 }

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

マージソート

　マージソートは，データ列を繰り返し分割して，それぞれを並べ替えては併合するという操作を繰り返し行い，昇順（または降順）に並べ替えるアルゴリズムです。

※ 計算量：O(n log₂n)

例）配列aを昇順に整列する

流れ図

擬似言語

// 主プログラム
〇main()
　整数型の配列：a ← {30, 50, 20, 10, 40, 70, 15}
　 merge_sort ( a, aの長さ )

// 副プログラム
○ merge_sort ( 整数型の配列：arr, 整数型：num )
　整数型の配列：arr1, arr2
　整数型：num1, num2
　if ( num ＞ 1 )
　　num1 ← num ÷ 2
　　num2 ← num － num1
　　for ( iを0からnum1－1まで1ずつ増やす )
　　　arr1[i] ← arr[i]
　　endfor
　　for ( iを0からnum2－1まで1ずつ増やす )
　　　arr2[i] ← arr[num1 ＋ i]
　　endfor
　　merge_sort ( arr1, num1 )
　　merge_sort ( arr2, num2 )
　　merge ( arr1, num1, arr2, num2, arr )
　endif

○ merge ( 整数型の配列：arr1, 整数型：num1, 整数型の配列：arr2, 整数型：num2, 整数型の配列：arr )
　整数型：i, j
　i ← 0
　j ← 0
　while (( i ＜ num1) and ( j ＜ num2 ))
　　if ( arr1[i] ＜ arr2[j] )
　　　arr[i ＋ j] ← arr1[i]
　　　i ← i ＋ 1
　　eise
　　　arr[i ＋ j] ← arr2[j]
　　　j ← j ＋ 1
　　endif
　endwhile
　while (( i ＜ num1) or ( j ＜ num2 ))
　　if ( i ＜ num1 )
　　　arr[i ＋ j] ← arr1[i]
　　　i ← i ＋ 1
　　eiseif ()
　　　arr[i ＋ j] ← arr2[j]
　　　j ← j ＋ 1
　　endif
　endwhile

Python

import numpy as np

# クラスSort
class Sort:
    def __init__(self):
       pass 

    def merge_sort(self, arr: np.array, num:int):
        arr1: np.array; arr2: np.array
        num1: int; num2: int
        if num > 1:
            num1 = int(num / 2)
            num2 = num - num1
            arr1 = np.zeros(num1, dtype=np.int32)
            arr2 = np.zeros(num2, dtype=np.int32)
            for i in range(0, num1, 1):
                arr1[i] = arr[i]
            for i in range(0, num2, 1):
                arr2[i] = arr[num1 + i]
            self.merge_sort(arr1, num1)
            self.merge_sort(arr2, num2)
            self.merge(arr1, num1, arr2, num2, arr)

    def merge(self, arr1: np.array, num1:int, arr2: np.array, num2: int, arr: np.array):
        i: int = 0; j: int = 0
        while (i < num1) and (j < num2):
            if arr1[i] < arr2[j]:
                arr[i + j] = arr1[i]
                i += 1
            else:
                arr[i + j] = arr2[j]
                j += 1
        while (i < num1) or (j < num2):
            if i < num1:
                arr[i + j] = arr1[i]
                i += 1
            else:
                arr[i + j] = arr2[j]
                j += 1

# 主プログラム
def main():
    sort: Sort = Sort()
    a: np.array = np.array([30, 50, 20, 10, 40, 70, 15])
    sort.merge_sort(a, len(a))
    print('ソート後：', a)

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
class Sort {
    public Sort() {}

    public void merge_sort(int[] arr, int num) {
        int[] arr1, arr2;
        int num1, num2;
        if(num > 1) {
            num1 = num / 2;
            num2 = num - num1;
            arr1 = new int[num1];
            arr2 = new int[num2];
            for(int i = 0; i < num1; i++) {
                arr1[i] = arr[i];
            }
            for(int i = 0; i < num2; i++) {
                arr2[i] = arr[num1 + i];
            }
            merge_sort(arr1, num1);
            merge_sort(arr2, num2);
            merge(arr1, num1, arr2, num2, arr);
            Console.WriteLine("ソート：{0}", String.Join(",", arr));
        }
    }

    void merge(int[] arr1, int num1, int[] arr2, int num2, int[] arr) {
        int i = 0, j = 0;
        while((i < num1) && (j < num2)) {
            if(arr1[i] < arr2[j]) {
                arr[i + j] = arr1[i];
                i += 1;
            } else {
                arr[i + j] = arr2[j];
                j += 1;
            }
        }
        while((i < num1) || (j < num2)) {
            if(i < num1) {
                arr[i + j] = arr1[i];
                i += 1;
            } else {
                arr[i + j] = arr2[j];
                j += 1;
            }
        }
    }
}

class a_006 {
    // 主プログラム
    static void Main(string[] args) {
        Sort sort = new Sort();
        int[] a = new int[]{30, 50, 20, 10, 40, 70, 15}; 
        sort. merge_sort(a, a.Length);
    }
}

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

ヒープソート

　ヒープソートは，未整列データからヒープを作成して，昇順（または降順）に並べ替えるアルゴリズムです。

※ ヒープ…親ノード≧子ノード（または，子ノード≧親ノード）という性質を持つ2分木

※ 計算量：O(n log₂n)

例）配列aを昇順に整列する

※ ① ヒープの作成，② 木の根と最後の節の値を交換，③ ヒープの再構成，④ ②，③を，③の結果が木の根になるまで繰り返す

流れ図

擬似言語

// 主プログラム
〇main()
　整数型の配列：a ← {20, 40, 30, 50, 10}
　整数型の配列：h
　 heap_sort ( a, h, aの長さ )

// 副プログラム
○ heap_sort ( 整数型の配列：arr, 整数型の配列：heap, 整数型：num )
　make_heap ( arr, heap, num )
　for ( iをnum－1から1まで1ずつ減らす)
　　swap ( heap, 0, i )
　　remake_heap ( heap, i - 1 )
　endfor

○ make_heap ( 整数型の配列：arr, 整数型の配列：heap, 整数型：num )
　整数型：k
　for ( iを0からnum－1まで1ずつ増やす )
　　heap[i] ← arr[i]
　　k ← i
　　while ( k ＞ 0 )
　　　if ( heap[k] ＞ heap[parent ( k )] )
　　　　swap ( heap, k, parent ( k ) )
　　　　k ← parent ( k )
　　　else
　　　　break
　　　endif
　　endwhile
　endfor

○ remake_heap ( 整数型の配列：heap, 整数型：last )
　整数型：n, temp
　n ← 0
　while ( lchild ( n ) ≦ last )
　　temp ← lchild ( n )
　　if ( rchild ( n ) ≦ last )
　　　if ( heap[temp] ≦ heap[rchild ( n )] )
　　　　temp ← rchild ( n )
　　　endif
　　endif
　　if ( heap[temp] ＞ heap[n] )
　　　swap ( heap, n, temp )
　　else
　　　return
　　endif
　　n ← temp
　endwhile

○ swap ( 整数型の配列：heap, 整数型：i, 整数型：j )
　整数型：temp
　temp ← heap[i]
　heap[i] ← heap[j]
　heap[j] ← temp

○ parent (整数型：i )
　( i － 1 ) ÷ 2 を返す

○ lchild ( 整数型：i )
　2 × i ＋ 1 を返す

○ rchild (整数型：i )
　2 × i ＋ 2 を返す

Python

import numpy as np

# クラスSort
class Sort:
    def __init__(self):
       pass 

    def heap_sort(self, arr: np.array, heap: np.array, num: int):
        self.make_heap(arr, heap, num)
        for i in range(num - 1, 0, -1):
            self.swap(heap, 0, i)
            self. remake_heap(heap, i - 1)

    def make_heap(self, arr: np.array, heap: np.array, num: int):
        k: int
        for i in range(0, num, 1):
            heap[i] = arr[i]
            k = i
            while k > 0:
                if heap[k] > heap[self.parent(k)]:
                    self.swap(heap, k, self.parent(k))
                    k = self.parent(k)
                else:
                    break

    def remake_heap(self, heap: np.array, last: int):
        n: int; temp: int
        n = 0
        while self.lchild(n) <= last:
            temp = self.lchild(n)
            if self.rchild(n) <= last:
                if heap[temp] <= heap[self.rchild(n)]:
                    temp = self.rchild(n)
            if heap[temp] > heap[n]:
                self.swap(heap, n, temp)
            else:
                return
            n = temp

    def swap(self, heap: np.array, i: int,j: int):
        temp: int
        temp = heap[i]
        heap[i] = heap[j]
        heap[j] = temp

    def parent(self, i: int):
        return int((i - 1) / 2)

    def lchild(self, i: int):
        return int(2 * i + 1)
    
    def rchild(self, i: int):
        return int(2 * i + 2)
        
# 主プログラム
def main():
    sort: Sort = Sort()
    a: np.array = np.array([20, 40, 30, 50, 10])
    h: np.array = np.array([0, 0, 0, 0, 0])
    sort.heap_sort(a, h, len(a))

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
using System.ComponentModel;

class Sort {
    public Sort() {}

    public void heap_sort(int[] arr, int[] heap, int num) {
        make_heap(arr, heap, num);
        for(int i = num - 1; i > 0; i--) {
            swap(heap, 0, i);
            remake_heap(heap, i - 1);
        }
    }

    void make_heap(int[] arr, int[] heap, int num) {
        int k;
        for(int i = 0; i < num; i++) {
            heap[i] = arr[i];
            k = i;
            while(k > 0) {
                if(heap[k] > heap[parent(k)]) {
                    swap(heap, k, parent(k));
                    k = parent(k);
                } else {
                    break;
                }
            }
        }
    }

    void remake_heap(int[] heap, int last) {
        int n, temp;
        n = 0;
        while(lchild(n) <= last) {
            temp = lchild(n);
            if(rchild(n) <= last) {
                if(heap[temp] <= heap[rchild(n)]) {
                    temp = rchild(n);
                }
            }
            if(heap[temp] > heap[n]) {
                swap(heap, n, temp);
            } else {
                return;
            }
            n = temp;
        }
    }

    void swap(int[] heap, int i, int j) {
        int temp;
        temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    int parent(int i) {
        return (i - 1) / 2;
    }

    int lchild(int i) {
        return 2 * i + 1;
    }

    int rchild(int i) {
        return 2 * i + 2;
    }
}

class a_007 {
    // 主プログラム
    static void Main(string[] args) {
        Sort sort = new Sort();
        int[] a = new int[]{20, 40, 30, 50, 10}; 
        int[] h = new int[a.Length];
        sort.heap_sort(a, h, a.Length);
    }
}

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

探索

線形探索

　線形探索は，探索データと探索対象の配列のデータとの比較を先頭から順に行い探索するアルゴリズムです。

※ 計算量：O(n)

例）配列aの中に20があるかを探索し，見つかった場合はデータの位置を示す添字を，見つからなかった場合は-1を返す

流れ図

※ 計算量（処理の効率性を大雑把に評価するもの）は，ループ1の部分で評価すればよいので，入力データn件の場合のループ1の実行回数：約n回 ⇒ 全体の実行回数：n回となり，O(n)となる

擬似言語

// 主プログラム
〇 main()
　整数型の配列：a ← {30, 50, 40, 20, 10}
　sequential_search( 20, a )

// 副プログラム
○ sequential_search( k, arr )
　整数型：i ← 0
　while ( i ＜ arrの長さ and arr[i] ≠ k )
　　i ← i ＋ 1
　endwhile
　if ( i ＜ arrの長さ )
　　return i
　else
　　return －1
　endif

Python

import numpy as np

# クラスSort
class Search:
    def __init__(self):
       pass 

    def sequential_search(self, k: int, arr: np.array) -> int:
        i: int = 0
        while i < len(arr) and arr[i] != k:
            i += 1
        if i < len(arr):            
            return i
        else:
            return -1

# 主プログラム
def main():
    sort: Search = Search()
    a: np.array = np.array([30, 50, 40, 20, 10])
    r: int = sort.sequential_search(20, a)
    if r != -1:
        print('探索結果：添字:', r, '，値:', a[r])
    else:
        print('探索結果：探索データはありませんでした。')

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
class Search {
    public Search() {}

    public int sequential_search(int k, int[] arr) {
        int i = 0;
        while(i < arr.Length && arr[i] != k) {
            i += 1;
        }
        if(i < arr.Length) {
            return i;
        } else {
            return -1;
        }
    }
}

class b_001 {
    // 主プログラム
    static void Main(string[] args) {
        Search search = new Search();
        int[] a = new int[]{30, 50, 40, 20, 10};
        int r = search.sequential_search(20, a);
        if(r != -1) {
            Console.WriteLine("探索結果：添字:{0}，値:{1}", r, a[r]);
        } else {
            Console.WriteLine("探索結果：探索データはありませんでした。");
        }
    }
 }

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

番兵を使用した方法

　線形探索の効率を上げるために，番兵を使用する方法があります。

※ 番兵を使用すると，ループのたびに「すべてのデータと比較したかを確認」する必要がないので，探索の効率を上げることができる

例）配列aの中に70があるかを探索し，見つかった場合はデータの位置を示す添字を，見つからなかった場合は-1を返す

流れ図

擬似言語

// 主プログラム
〇 main()
　整数型の配列：a ← {30, 50, 40, 20, 10}
　sequential_search1 ( 70, a )

// 副プログラム
○ sequential_search1 ( k, arr )
　arrの長さを1増やす
　arr[arrの長さ － 1] ← k
　整数型：i ← 0
　while ( arr[i] ≠ k )
　　i ← i ＋ 1
　endwhile
　if ( i ＜ arrの長さ － 1 )
　　return i
　else
　　return －1
　endif

Python

import numpy as np

# クラスSort
class Search:
    def __init__(self):
       pass 

    def sequential_search1(self, k: int, arr: np.array) -> int:
        arr = np.append(arr, k)
        i: int = 0
        while arr[i] != k:
            i += 1
        if i < len(arr) - 1:
            return i
        else:
            return -1

# 主プログラム
def main():
    sort: Search = Search()
    a: np.array = np.array([30, 50, 40, 20, 10])
    r: int = sort.sequential_search1(20, a)
    if r != -1:
        print('探索結果：添字:', r, '，値:', a[r])
    else:
        print('探索結果：探索データはありませんでした。')

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
class Search {
    public Search() {}

    public int sequential_search1(int k, int[] arr) {
        Array.Resize(ref arr, arr.Length + 1);
        arr[arr.Length - 1] = k;
        int i = 0;
        while(arr[i] != k) {
            i += 1;
        }
        if(i < arr.Length - 1) {
            return i;
        } else {
            return -1;
        }
    }
}

class b_001 {
    // 主プログラム
    static void Main(string[] args) {
        Search search = new Search();
        int[] a = new int[]{30, 50, 40, 20, 10};
        int r = search.sequential_search1(20, a);
        if(r != -1) {
            Console.WriteLine("探索結果：添字:{0}，値:{1}", r, a[r]);
        } else {
            Console.WriteLine("探索結果：探索データはありませんでした。");
        }
    }
 }

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

2分探索

　2分探索は，整列済みデータの中から探索データを探索する場合に有効なアルゴリズムです。探索データと整列済みデータの中心に位置するデータを比較し，整列済みデータの前半分か後半分を次の探索範囲として，これを繰り返すことによりデータを探索します。

※ 計算量：O(log₂n)

例）配列aの中に70があるかを探索し，見つかった場合はデータの位置を示す添字を，見つからなかった場合は-1を返す

流れ図

※ 計算量（処理の効率性を大雑把に評価するもの）は，入力データn件の場合のループ1の部分で評価すればよいので，ループ1の実行回数：約log₂n回 ⇒ 全体の実行回数：log₂n回となり，O(log₂n)となる

※ x＝log₂n ⇔ n=2^x。データ件数が16件の場合，4＝log₂16＝log₂2⁴（⇔ 16＝2⁴）となり，探索（分割）回数は最大で4回となる

擬似言語

// 主プログラム
〇 main()
　整数型の配列：a ← {10, 15, 20, 30, 40, 50, 70, 85}
　binary_search ( 70, a )

// 副プログラム
○ binary_search ( k, arr )
　整数型：l ← 0
　整数型：h ← arrの長さ－1
　整数型：m ← (l + h) / 2
　while ( l ≦ h and arr[m] ≠ k )
　　if ( arr[m] ＜ k )
　　　l ← m ＋ 1
　　else
　　　h ← m － 1
　　endif
　　m ← (l + h) / 2
　endwhile
　if ( l ≦ h )
　　return m
　else
　　return －1
　endif

Python

import numpy as np

# クラスSort
class Search:
    def __init__(self):
       pass 

    def binary_search(self, k: int, arr: np.array) -> int:
        l: int = 0
        h: int = len(arr) - 1
        m: int = int((l + h) / 2)
        while l <= h and arr[m] != k:
            if arr[m] < k:
                l = m + 1
            else:
                h = m - 1
            m = int((l + h) / 2)
        if l <= h:
            return m
        else:
            return -1

# 主プログラム
def main():
    sort: Search = Search()
    a: np.array = np.array([10, 15, 20, 30, 40, 50, 70, 85])
    r: int = sort.binary_search(70, a)
    if r != -1:
        print('探索結果：添字:', r, '，値:', a[r])
    else:
        print('探索結果：探索データはありませんでした。')

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSort
class Search {
    public Search() {}

    public int binary_search(int k, int[] arr) {
        int l = 0;
        int h = arr.Length - 1;
        int m = (l + h) / 2;
        while(l <= h && arr[m] != k) {
            if(arr[m] < k){
                l = m + 1;
            } else {
                h = m - 1;
            }
            m = (l + h) / 2;
        }
        if(l <= h) {
            return m;
        } else {
            return -1;
        }
    }
}

class b_002 {
    // 主プログラム
    static void Main(string[] args) {
        Search search = new Search();
        int[] a = new int[]{10, 15, 20, 30, 40, 50, 70, 85};
        int r = search.binary_search(70, a);
        if(r != -1) {
            Console.WriteLine("探索結果：添字:{0}，値:{1}", r, a[r]);
        } else {
            Console.WriteLine("探索結果：探索データはありませんでした。");
        }
    }
 }

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

ハッシュ法

　ハッシュ法は，直接探索が可能なアルゴリズムです。データのキー値をハッシュ関数に通して得られるハッシュ値によりデータの格納位置が決まりますので，探索時には同じ計算により格納位置を見つけることができます。ただし，異なるキー値から同じハッシュ値が得られる場合があります（衝突（シノニム））。

※ 計算量：O(1)

データの追加

データの探索

文字列に対する処理

文字列の探索

　文字列の探索に関しては，まず，探索する文字列の1文字目と同じ文字を探索して，一致した場合に2文字目以降も一致するかを順に調べたりします。

例）配列aの中に「ひかり」という文字列があるかを探索し，見つかった場合はデータの1文字目の位置を示す添字を，見つからなかった場合は-1を返す

流れ図

擬似言語

// 主プログラム
〇 main()
　文字列型：a ← {かひとひかあぜひかりす}
　文字列型：b ← {ひかり]
　search_str(a, b)

// 副プログラム
○ search_str (文字列型：arr1, 文字列型：arr2)
　整数型：i ← 0
　整数型：j ← 0
　while ( i ＜ arr1の長さ and j ＜ arr2の長さ )
　　if ( arr1[i] ≠ arr2[j] )
　　　j ← 0
　　else
　　　j ← j ＋ 1
　　endif
　　i ← i ＋ 1
　endwhile
　if ( j ＞ arr2の長さ － 1 )
　　return i - arr2.Length
　else
　　return －1
　endif

Python

import numpy as np

# クラスSearch
class Search:
    def __init__(self):
       pass 

    def search_str(self, arr1: str, arr2: str) ->int:
        i: int = 0; j: int = 0
        while i < len(arr1) and j < len(arr2):
            if arr1[i] != arr2[j]:
                j = 0
            else:
                j += 1
            i += 1
        if j > len(arr2) - 1:
            return i - len(arr2)
        else:
            return -1

# 主プログラム
def main():
    a: str = 'かひとひかあぜひかりす'
    b: str = 'ひかり'
    r: int = 0
    hash: Search = Search()
    r = hash.search_str(a, b)
    print(r)

if __name__ == "__main__":
    main()

※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行　－情報処理シンプルまとめ」を参照

// クラスSearch
class Search {
    public Search() {}

    public int search_str(string arr1, string arr2) {
        int i = 0, j = 0;
        while(i < arr1.Length && j < arr2.Length) {
            if(arr1[i] != arr2[j]) {
                j = 0;
            } else {
                j += 1;
            }
            i += 1;
        }
        if(j > arr2.Length - 1) {
            return i - arr2.Length;
        } else {
            return -1;
        }
    }
}

class c_001 {
    // 主プログラム
    static void Main(string[] args) {
        string a = "かひとひかあぜひかりす";
        string b = "ひかり";
        int r = 0;
        Search hash = new Search();
        r = hash.search_str(a, b);
        Console.WriteLine(r);
    }
 }

※ C#プログラムの作成と実行については，「C#プログラムの作成と実行　－情報処理シンプルまとめ」を参照

実行結果

まとめ

　今回は，アルゴリズムと計算量について，シンプルにまとめてみました。各アルゴリズムについては，丁寧にトレースすると理解が深まると思います。最初は難しいかもしれませんが，慣れだと思います。根気よく頑張りましょう。