アルゴリズムと計算量は，基本情報技術者試験をはじめとする情報処理技術者試験で頻出となる重要分野です。しかし，「計算量の O(n) や O(n²) の違いがよく分からない」，「ソートアルゴリズムの特徴を覚えられない」，「クイックソートやマージソートの処理の流れが理解できない」という方も多いのではないでしょうか。
このページでは，基本情報技術者試験で重要となるアルゴリズムと計算量について，流れ図・擬似言語・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)となる
※ 入力データn2件，実行回数n2回の場合の計算量はO(n2)となる
入力データがn件で，
実行回数がn回の場合の計算量＝O(n)
実行回数が3n＋2回の場合の計算量＝O(n)
実行回数が12n2＋3n＋5回の場合の計算量＝O(n2)
実行回数がlog2n2の場合の計算量＝O(log2n)
※ 計算量は，最高次の項以外は無視し，さらに，最高次の係数も無視して表す
※ ax＝b ⇔ x＝logab（aを底，bを真数，xをaを底とする対数という）
計算量の大小関係とは
計算量の大小関係は，次のようになります。
O(1) ＜ O(log2n) ＜ O(n) ＜ O(nlog2n) ＜ O(n2) ＜ O(2n) ＜ O(n!)
問1 次の計算量に関する説明文①～③の（ ）内に当てはまる語句を記入しなさい。
① 計算量 O(1) は、データ件数に関係なく（ ）時間で処理できる。
② 計算量 O(n) は、データ件数に（ ）して処理時間が増加する。
③ 計算量 O(log2n) は探索範囲を毎回（ ）にしながら処理する。
① 一定
※ データ件数が1件でも，10件でも，100万件でも，処理時間はほぼ変わらない
② 比例
※ データ件数が2倍になると，処理時間も約2倍になる（線形探索など）
③ 半分（2分の1）
※ 二分探索では探索範囲を，毎回，半分にする ⇒ 高速
問2 次の計算量を，効率の良い順に並べなさい。
O(n)，O(1)，O(log2n)，O(n2)
O(1)，O(log2n)，O(n)，O(n2)
練習問題
問1 次の計算量に関する説明文①～③の（ ）内に当てはまる語句を記入しなさい。
① 計算量 O(1) は、データ件数に関係なく（ ）時間で処理できる。
② 計算量 O(n) は、データ件数に（ ）して処理時間が増加する。
③ 計算量 O(log2n) は探索範囲を毎回（ ）にしながら処理する。
① 一定
※ データ件数が1件でも，10件でも，100万件でも，処理時間はほぼ変わらない
② 比例
※ データ件数が2倍になると，処理時間も約2倍になる（線形探索など）
③ 半分（2分の1）
※ 二分探索では探索範囲を，毎回，半分にする ⇒ 高速
問2 次の計算量を，効率の良い順に並べなさい。
O(n)，O(1)，O(log2n)，O(n2)
O(1)，O(log2n)，O(n)，O(n2)
整列（ソート）とは
基本交換法（隣接交換法，バブルソート）とは
基本交換法は，隣り合うデータの比較・交換を，範囲を狭めながら繰り返し行い，昇順（または降順）に並べ替えるアルゴリズムです。
※ 未整列データの中で最も小さい（または最も大きい）データが，泡のように（泡が浮き上がるように）移動するので，バブルソートとも呼ばれる
※ 計算量：O(n2)
基本交換法（隣接交換法，バブルソート）の例
例）配列aを昇順に整列する
流れ図
※ 計算量（処理の効率性を大雑把に評価するもの）は，ループ1，ループ2の2重ループの部分で評価すればよい ⇒ 入力データn件の場合のループ2の実行回数：約n2回 ⇒ 全体の実行回数：約n2回となり，O(n2)となる
擬似言語
// 主プログラム
〇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
endforPython
import numpy as np
# クラスSort
class Sort:
def __init__(self):
pass
def bubble_sort(self, arr):
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()
a = np.array([30, 50, 40, 20, 10])
sort.bubble_sort(a)
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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(n2)
基本選択法（選択ソート）の例
例）配列aを昇順に整列する
流れ図
※ 計算量（処理の効率性を大雑把に評価するもの）は，ループ1，ループ2の2重ループの部分で評価すればよい ⇒ 入力データn件の場合のループ2の実行回数：約n2回 ⇒ 全体の実行回数：約n2回となり，O(n2)となる
擬似言語
// 主プログラム
〇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
endforPython
import numpy as np
# クラスSort
class Sort:
def __init__(self):
pass
def basic_selection_sort(self, arr):
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()
a = np.array([30, 50, 40, 20, 10])
sort.basic_selection_sort(a)
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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(n2)
基本挿入法（挿入ソート）の例
例）配列aを昇順に整列する
流れ図
※ 計算量（処理の効率性を大雑把に評価するもの）は，ループ1，ループ2の2重ループの部分で評価すればよい ⇒ 入力データn件の場合のループ2の実行回数：約n2回 ⇒ 全体の実行回数：約n2回となり，O(n2)となる
擬似言語
// 主プログラム
〇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
endforPython
import numpy as np
# クラスSort
class Sort:
def __init__(self):
pass
def basic_insertion_sort(self, arr):
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()
a = np.array([30, 40, 10, 50, 20])
sort.basic_insertion_sort(a)
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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(n1.5)程度，最悪の場合：O(n2)
シェルソート（改良挿入法）の例
例）配列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
endwhilePython
import numpy as np
# クラスSort
class Sort:
def __init__(self):
pass
def shell_sort (self, arr):
w = int(len(arr) / 2)
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()
a = np.array([30, 50, 40, 20, 10, 70, 15])
sort.shell_sort(a)
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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 log2n)，最悪の場合：O(n2)
クイックソートの例
例）配列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 )
endifPython
import numpy as np
# クラスSort
class Sort:
def __init__(self):
pass
def quick_sort(self, arr, first, last):
i = first
j = last
p = arr[int((i + j) / 2)]
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()
a = np.array([30, 50, 40, 20, 10, 70, 15])
sort.quick_sort(a, 0, len(a) - 1)
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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 log2n)
マージソートの例
例）配列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
else
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
else
arr[i ＋ j] ← arr2[j]
j ← j ＋ 1
endif
endwhilePython
import numpy as np
# クラスSort
class Sort:
def __init__(self):
pass
def merge_sort(self, arr, num):
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, num1, arr2, num2, arr):
i = 0; j = 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()
a = np.array([30, 50, 40, 20, 10, 70, 15])
sort.merge_sort(a, len(a))
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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 log2n)
ヒープソートの例
例）配列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, heap, num):
self.make_heap(arr, heap, num)
for i in range(num - 1, 0, -1):
self.swap(heap, 0, i)
self.down_heap(heap, i - 1)
def make_heap(self, arr, heap, num):
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 down_heap(self, heap, last):
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, i, j):
temp = heap[i]
heap[i] = heap[j]
heap[j] = temp
def lchild(self, i):
return int(2 * i + 1)
def rchild(self, i):
return int(2 * i + 2)
def parent(self, i):
return int((i - 1) / 2)
# 主プログラム
def main():
sort = Sort()
a = np.array([30, 50, 40, 20, 10])
h = np.array([0, 0, 0, 0, 0])
sort.heap_sort(a, h, len(a))
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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#プログラムの作成と実行」を参照
実行結果
練習問題
問1 次の擬似言語を実行した結果について，①～⑤に答えなさい。
整数型の配列: arr ← {30, 10, 40, 20}
整数型: i, j, temp
for(iを1から3まで1ずつ増やす)
for(jを1から4 － iまで1ずつ増やす)
if(arr[j] ＞ arr[j ＋ 1])
temp ← arr[j]
arr[j] ← arr[j ＋ 1]
arr[j ＋ 1] ← temp
endif
endfor
endfor※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
※ 基本交換法の実装方法は複数あり，この問題では，未整列部分の末尾まで順番に比較・交換を行う実装を使用している（アルゴリズムの動作自体は同じ）
① 1回目の外側ループ終了後の配列arrは？
② 2回目の外側ループ終了後の配列arrは？
③ 整列完了後の配列arrは？
④ 1回目の外側ループ終了後に確定した最大値は？
⑤ 計算量は？
① 10, 30, 20, 40
② 10, 20, 30, 40
③ 10, 20, 30, 40
④ 40
⑤ O(n2)
問2 次の擬似言語を実行した結果について，①～⑤に答えなさい。
整数型の配列: arr ← {30, 10, 40, 20}
整数型: i, j
整数型: min
整数型: temp
for(iを1から3まで1ずつ増やす)
min ← i
for(jをi ＋ 1から4まで1ずつ増やす)
if(arr[j] ＜ arr[min])
min ← j
endif
endfor
temp ← arr[i]
arr[i] ← arr[min]
arr[min] ← temp
endfor※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
※ 基本選択法の実装方法は複数あり，この問題では，未整列部分から最小値を探し，その位置を記録して最後に交換する実装を使用している（アルゴリズムの動作自体は同じ）
① 1回目の外側ループ終了後の配列arrは？
② 2回目の外側ループ終了後の配列arrは？
③ 整列完了後の配列arrは？
④ 1回目の外側ループ終了後に確定した最小値は？
⑤ 計算量は？
① 10, 30, 40, 20
② 10, 20, 40, 30
③ 10, 20, 30, 40
④ 10
⑤ O(n2)
問3 次の擬似言語を実行した結果について，①～④に答えなさい。
整数型の配列: arr ← {20, 40, 10, 30}
整数型: i, j, temp
for(iを2からarrの長さまで1ずつ増やす)
temp ← arr[i]
j ← i - 1
while(j ≧ 1 and arr[j] ＞ temp)
arr[j ＋ 1] ← arr[j]
j ← j － 1
endwhile
arr[j ＋ 1] ← temp
endfor※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
※ 基本挿入法の実装方法は複数あり，この問題では，挿入する値を一時変数に保存し、整列済み部分を後方へ移動しながら挿入位置を探す実装を使用している（アルゴリズムの動作自体は同じ）
① 10を挿入完了後の配列arrは？
② 30を挿入完了後の配列arrは？
③ 最初に挿入対象となる値は？
④ 計算量は？
① 10, 20, 40, 30
② 10, 20, 30, 40
③ 40
④ O(n2)
問4 次の擬似言語を実行した結果について，①～④に答えなさい。
整数型の配列: arr ← {40, 20, 30, 10}
整数型: w, i, j, temp
w ← arrの長さ ÷ 2
while(w ＞ 0)
for(iをw ＋ 1からarrの長さまで1ずつ増やす)
temp ← arr[i]
j ← i
while(j ＞ w and arr[j － w] ＞ temp)
arr[j] ← arr[j － w]
j ← j － w
endwhile
arr[j] ← temp
endfor
w ← w ÷ 2
endwhile※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
※ シェルソートの実装方法は複数あり，この問題では，間隔（gap）を配列長の半分から開始し，毎回半分にしながら挿入ソートを行う実装を使用している（アルゴリズムの動作自体は同じ）
① 最初の間隔wは？
② 間隔w＝2のときに構成されるグループは？
③ 間隔w＝2の整列後の配列arrは？
④ 整列完了後の配列arrは？
① 2
② (40, 30) と (20, 10)
③ 30, 10, 40, 20
④ 10, 20, 30, 40
問5 次の擬似言語を実行した結果について，①～⑤に答えなさい。
整数型の配列: arr ← {25, 10, 40, 20}
〇main()
quick_sort(arr, 1, arrの長さ)
〇quick_sort(整数型の配列：arr, 整数型：first, 整数型：last)
整数型：i ← first
整数型：j ← last
整数型：pivot ← arr[(first ＋ last) ÷ 2]
整数型：temp
while(true)
while(arr[i] ＜ pivot)
i ← i ＋ 1
endwhile
while(arr[j] ＞ pivot)
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 ＜ j)
quick_sort(arr, first, j)
endif
if(i ＜ last)
quick_sort(arr, i, last)
endif※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
※ クイックソートの実装方法は複数あり，この問題では，中央要素をピボットとし，左右から走査して条件を満たす要素を交換しながら分割し，その後に再帰的に部分配列を整列する実装を使用している（アルゴリズムの動作自体は同じ）
① 最初のピボットは？
② 最初の再帰呼び出し直前の配列arrは？
③ 左側の部分配列は？
④ 右側の部分配列は？
⑤ 整列完了後の配列arrは？
① 10
② 10, 25, 40, 20
③ なし
④ 25, 40, 20
⑤ 10, 20, 25, 40
問6 次の擬似言語を実行した結果について，①～⑤に答えなさい。
整数型の配列: arr ← {40, 20, 30, 10}
〇main()
merge_sort(arr, arrの長さ)
〇merge_sort(整数型の配列：arr, 整数型：num)
整数型の配列：arr1, arr2
整数型：num1, num2, i
if(num ＞ 1)
num1 ← num ÷ 2
num2 ← num － num1
for(iを1からnum1まで1ずつ増やす)
arr1[i] ← arr[i]
endfor
for(iを1からnum2まで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 ← 1
整数型：j ← 1
while((i ≦ num1) and (j ≦ num2))
if(arr1[i] ＜ arr2[j])
arr[i ＋ j － 1] ← arr1[i]
i ← i ＋ 1
else
arr[i ＋ j － 1] ← arr2[j]
j ← j ＋ 1
endif
endwhile
while((i ≦ num1) or (j ≦ num2))
if(i ≦ num1)
arr[i ＋ j － 1] ← arr1[i]
i ← i ＋ 1
else
arr[i ＋ j － 1] ← arr2[j]
j ← j ＋ 1
endif
endwhile※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
※ マージソートの実装方法は複数あるが，この問題は，例と同じ流れである
① 最初の分割結果は？
② さらに分割した結果は？
③ ②で得られた2要素ずつの部分配列をそれぞれマージした結果は？
④ 整列完了後の配列arrは？
⑤ 計算量は？
① (40, 20) , (30, 10)
② (40), (20), (30), (10)
③ (20, 40) , (10, 30)
④ 10, 20, 30, 40
⑤ O(n log2n)
問7 次の擬似言語を実行した結果について，①～④に答えなさい。
整数型の配列: arr ← {30, 50, 20, 10}
〇main()
heap_sort(arr, arrの長さ)
〇heap_sort(整数型の配列：arr, 整数型：n)
build_heap(arr, n) // 最大ヒープを構築
整数型：i
for(iをnから2まで1ずつ減らす)
temp ← arr[1]
arr[1] ← arr[i]
arr[i] ← temp
down_heap(arr, 1, i － 1) // ヒープサイズを縮小して再構成
endfor
〇build_heap(整数型の配列：arr, 整数型：n)
整数型：i
for(iをn÷2から1まで1ずつ減らす)
down_heap(arr, i, n)
endfor
〇down_heap(整数型の配列：arr, 整数型：k, 整数型：n)
整数型：parent ← k
整数型：child
整数型：temp
while(parent × 2 ≦ n)
child ← parent × 2
if(child ＜ n and arr[child] ＜ arr[child ＋ 1])
child ← child ＋ 1
endif
if(arr[parent] ≧ arr[child])
break
endif
temp ← arr[parent]
arr[parent] ← arr[child]
arr[child] ← temp
parent ← child
endwhile※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
※ ヒープソートの実装方法は複数あり，この問題では，最大ヒープの構築を下位ノードからのdown_heapにより行い，その後，根と末尾を交換しながらヒープサイズを縮小し，再度down_heapで再構成する方式を使用している（アルゴリズムの動作自体は同じ）
① build_heap()関数の実行が終了した時点での配列arrは？
② heap_sort()関数内の最初の交換（swap）直後の配列arrは？
③ ②の直後に実行されるdown_heap()関数完了後の配列arrは？
④ 最終的に整列された配列は？
① 50, 30, 20, 10
② 10, 30, 20, 50
③ 30, 10, 20, 50
④ 10, 20, 30, 50
探索とは
線形探索とは
線形探索は，探索データと探索対象の配列のデータとの比較を先頭から順に行い探索するアルゴリズムです。
※ 計算量：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※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様）が，ここでは，Python・C#に合わせて0から始めるものとする
Python
import numpy as np
# クラスSort
class Search:
def __init__(self):
pass
def sequential_search(self, k, arr):
i = 0
while i < len(arr) and arr[i] != k:
i += 1
if i < len(arr):
return i
else:
return -1
# 主プログラム
def main():
sort = Search()
a = np.array([30, 50, 40, 20, 10])
r = sort.sequential_search(20, a)
if r != -1:
print('探索結果：添字:', r, '，値:', a[r])
else:
print('探索結果：探索データはありませんでした。')
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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を返す
流れ図
※ 計算量（処理の効率性を大雑把に評価するもの）は，ループ1の部分で評価すればよいので，入力データn件の場合のループ1の実行回数：約n回 ⇒ 全体の実行回数：n回となり，O(n)となる
擬似言語
// 主プログラム
〇 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※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様）が，ここでは，Python・C#に合わせて0から始めるものとする
Python
import numpy as np
# クラスSort
class Search:
def __init__(self):
pass
def sequential_search1(self, k, arr):
arr = np.append(arr, k)
i = 0
while arr[i] != k:
i += 1
if i < len(arr) - 1:
return i
else:
return -1
# 主プログラム
def main():
sort = Search()
a = np.array([30, 50, 40, 20, 10])
r = sort.sequential_search1(20, a)
if r != -1:
print('探索結果：添字:', r, '，値:', a[r])
else:
print('探索結果：探索データはありませんでした。')
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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(log2n)
2分探索の例
例）配列aの中に70があるかを探索し，見つかった場合はデータの位置を示す添字を，見つからなかった場合は-1を返す
流れ図
※ 計算量（処理の効率性を大雑把に評価するもの）は，入力データn件の場合のループ1の部分で評価すればよいので，ループ1の実行回数：約log2n回 ⇒ 全体の実行回数：log2n回となり，O(log2n)となる
※ x＝log2n ⇔ n=2x。データ件数が16件の場合，4＝log216＝log224（⇔ 16＝24）となり，探索（分割）回数は最大で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※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様）が，ここでは，Python・C#に合わせて0から始めるものとする
Python
import numpy as np
# クラスSort
class Search:
def __init__(self):
pass
def binary_search(self, k, arr):
l = 0
h = len(arr) - 1
m = 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()
a = np.array([10, 15, 20, 30, 40, 50, 70, 85])
r = sort.binary_search(70, a)
if r != -1:
print('探索結果：添字:', r, '，値:', a[r])
else:
print('探索結果：探索データはありませんでした。')
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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 次の擬似言語を実行した結果について，①～④に答えなさい。
整数型の配列: arr ← {10, 20, 30, 40, 50}
整数型: i ← 1
while(arr[i] ≠ 40)
i ← i ＋ 1
endwhile
i を出力※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
① 出力される変数iの値は？
② 50を探索する場合の比較回数は？
③ 60を探索する場合の比較回数は？
④ 計算量は？
① 4
② 5回（50は5番目にあるので5回比較する）
③ 5回（60は存在しないので最後まで探索する）
④ O(n)（線形探索の計算量はO(n)）
問2 線形探索を番兵法で行う場合，探索値そのものを配列の末尾に追加するが，その目的を答えなさい。
配列の範囲外のチェック（終了条件の判定）を不要にし、比較回数を減らすため
問3 次の擬似言語を実行した結果について，①～⑤に答えなさい。
整数型の配列: arr ← {5, 10, 15, 20, 25, 35, 40}
整数型: key ← 35
整数型: l ← 1
整数型: h ← arrの長さ
整数型: m
while(l ≦ h)
m ← (l + h) ÷ 2
if(arr[m] = key)
break
elseif(arr[m] < key)
l ← m + 1
else
h ← m - 1
endif
endwhile※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
※ 2分探索の実装方法は複数あり，この問題では，探索成功時にbreakを用いる実装を使用している（アルゴリズムの動作自体は同じ）
① 最初に比較する値は？
② 2回目に比較する値は？
③ 探索値35が見つかったときの添字は？
④ 計算量は？
⑤ 2分探索を行うための条件は？
① 20
② 35
③ 6
④ O(log2n)（2分探索の計算量はO(log2n)）
⑤ データが整列されている必要がある（2分探索は，整列済みデータの中から探索データを探索する場合に有効なアルゴリズムである）
問4 次の擬似言語を実行した結果について，①～⑥に答えなさい。ただし，ハッシュ表のサイズは7とし，ハッシュ関数は「ハッシュ値＝キー mod 7（キーを7で割った余り）」とする。
整数型の配列: key ← {701, 709, 715}
整数型: i
整数型: hash
for(iを1から3まで1ずつ増やす)
hash ← key[i] mod 7
hash を出力
endfor※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
① 1回目のループで出力される値は？
② 2回目のループで出力される値は？
③ 3回目のループで出力される値は？
④ 計算量は？
⑤ 同じ格納位置に複数のデータが対応する現象を何というか？
⑥ この擬似言語を実行した結果，⑥の現象が発生するキーを答えなさい。
① 1
② 2
③ 1
④ O(1)（ハッシュ法の計算量はO(1)）
⑤ 衝突（コリジョン）
⑥ 715
文字列に対する処理とは
文字列の探索とは
文字列の探索に関しては，まず，探索する文字列の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
endifPython
import numpy as np
# クラスSearch
class Search:
def __init__(self):
pass
def search_str(self, arr1, arr2):
i = 0; j = 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) + 1
else:
return -1
# 主プログラム
def main():
a = 'かひとひかあぜひかりす'
b = 'ひかり'
r = 0
hash = Search()
r = hash.search_str(a, b)
print(r)
if __name__ == "__main__":
main()※ Pythonプログラムの作成と実行については，「Pythonプログラムの作成と実行」を参照
C#
// クラス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#プログラムの作成と実行」を参照
実行結果
練習問題
問1 次の擬似言語を実行した結果について，①～③に答えなさい。
文字列型: text ← "まゆげまゆみ"
文字列型: pattern ← "まゆみ"
整数型: i
整数型: j
for(iを1から4まで1ずつ増やす)
j ← 1
while(j ≦ 3 and text[i + j - 1] ＝ pattern[j])
j ← j + 1
endwhile
if(j ＝ 4)
iを出力
break
endif
endfor※ 擬似言語では，配列の要素番号は1から始まる（IPAの擬似言語仕様に準拠）
※ 文字列探索の実装方法は複数あり，この問題では，探索成功時にbreakを用いる実装を使用している。また，探索文字列「まゆみ」は3文字，対象文字列「まゆげまゆみ」は6文字であるため，探索開始位置は1～4の範囲で調べればよい
① 探索文字列「まゆみ」が見つかった開始位置は？
② 探索開始位置が1のとき，何文字連続で一致するか？
③ 文字列探索で途中不一致になった場合、探索開始位置はどうなるか？
① 4
② 2文字
③ 次の位置から再検索する
まとめ
今回は，アルゴリズムと計算量について，基本情報技術者試験で重要となる内容を中心にシンプルにまとめました。
特に重要なのは，各アルゴリズムの特徴や計算量を理解することです。ソートアルゴリズムには，バブルソート，選択ソート，挿入ソート，クイックソート，マージソート，ヒープソートなどがあり，処理手順や計算量の違いを理解しておくことが大切です。また、探索アルゴリズムには，線形探索，二分探索，ハッシュ法などがあり，それぞれ探索方法や処理効率が異なります。
基本情報技術者試験では，アルゴリズムの動作を追跡する問題や計算量を求める問題が頻繁に出題されます。暗記だけではなく，「なぜその結果になるのか」を考えながら学習することが大切です。擬似言語だけでなく，PythonやC#でも実際にコードを書きながら学習してみましょう。
実践的な内容を学びたい方は，開発環境を構築するところからはじめてみてください。
理解が進んだら，基本情報技術者試験の過去問題にもチャレンジしてみてください。
- 流れ図と擬似言語によるプログラミングの過去問・解説
※ このページでは読みやすさを考慮し「コンピューター」，「サーバー」など長音付きで表記していますが，試験では「コンピュータ」，「サーバ」と表記されます
基本情報技術者試験の学習におすすめの参考書
基本情報技術者試験の合格を目指す方におすすめの参考書です。
学習のお役に立ちましたら
この記事が少しでも学習のお役に立ちましたら，今後も分かりやすい解説や学習コンテンツを継続してお届けする励みになります。
よろしければ、このサイトを応援いただけますと嬉しいです。
※OFUSEは，クリエイターやコンテンツ制作を直接支援できるサービスです。
