アルゴリズム基礎（ソート／検索の考え方） — パフォーマンス判断
プログラムでよく使う処理が ソート（並べ替え） と 検索（探す）。
初心者がまず理解すべきは「どういう方法があるか」「どのくらい速いか（計算量）」です。ここでは Java のコード例とともに、かみ砕いて解説します。
ソート（Sorting）
代表的なアルゴリズムと計算量
| アルゴリズム | 計算量（平均） | 特徴 |
|---|---|---|
| バブルソート | O(n²) | シンプルだが遅い。学習用。 |
| 選択ソート | O(n²) | 実装簡単。やはり遅い。 |
| 挿入ソート | O(n²) | 小規模データに有効。 |
| クイックソート | O(n log n) | 高速。標準ライブラリで採用。 |
| マージソート | O(n log n) | 安定ソート。大規模データに強い。 |
👉 実務では Arrays.sort や Collections.sort を使えば十分。内部で高速アルゴリズムが選ばれる。
Java のコード例
import java.util.*;
public class SortDemo {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(5, 2, 9, 1, 3);
// 昇順ソート
Collections.sort(list);
System.out.println(list); // [1, 2, 3, 5, 9]
// 降順ソート
list.sort(Comparator.reverseOrder());
System.out.println(list); // [9, 5, 3, 2, 1]
}
}
検索（Searching）
代表的な方法と計算量
| 方法 | 計算量 | 特徴 |
|---|---|---|
| 線形探索（リニアサーチ） | O(n) | 先頭から順に探す。小規模データ向け。 |
| 二分探索（バイナリサーチ） | O(log n) | ソート済み配列に有効。高速。 |
| ハッシュ探索 | O(1)（平均） | HashMap/HashSet を使う。超高速。 |
Java のコード例
線形探索
int[] arr = {5, 2, 9, 1, 3};
int target = 9;
boolean found = false;
for (int x : arr) {
if (x == target) {
found = true;
break;
}
}
System.out.println(found); // true
二分探索（Arrays.binarySearch）
int[] arr = {1, 2, 3, 5, 9};
int idx = Arrays.binarySearch(arr, 5);
System.out.println(idx); // 3（インデックス）
ハッシュ探索（HashSet）
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
System.out.println(set.contains("apple")); // true
System.out.println(set.contains("orange")); // false
パフォーマンス判断の考え方
- データ量が少ない: 単純な線形探索や挿入ソートでも十分。
- データ量が多い: O(n log n) のソート、O(log n) の検索を選ぶ。
- 頻繁に検索する: HashMap/HashSet を使うと効率的。
- 安定ソートが必要: 同じ値の順序を保ちたいならマージソート系（Java の
Collections.sortは安定）。
👉 計算量の目安:
- O(n²) → 数千件程度まで。
- O(n log n) → 数百万件でも現実的。
- O(1) → 即時応答。
例題で練習
例題1: 名前リストをソートして検索
List<String> names = Arrays.asList("Tanaka", "Sato", "Suzuki", "Kato");
Collections.sort(names); // 昇順ソート
System.out.println(names); // [Kato, Sato, Suzuki, Tanaka]
int idx = Collections.binarySearch(names, "Suzuki");
System.out.println("Suzukiの位置=" + idx);
例題2: 商品コード検索（HashMap）
Map<String, String> products = new HashMap<>();
products.put("A001", "Apple");
products.put("B002", "Banana");
System.out.println(products.get("A001")); // Apple
System.out.println(products.containsKey("C003")); // false
テンプレート集
ソート
Collections.sort(list); // 昇順
list.sort(Comparator.reverseOrder()); // 降順
線形探索
for (T item : list) {
if (item.equals(target)) { ... }
}
二分探索
int idx = Arrays.binarySearch(array, target);
ハッシュ探索
Set<T> set = new HashSet<>();
set.contains(target);
まとめ
- ソート: データを並べ替える。
Collections.sortが基本。 - 検索: 線形探索（O(n)）、二分探索（O(log n)）、ハッシュ探索（O(1)）。
- パフォーマンス判断: データ量と用途に応じてアルゴリズムを選ぶ。
👉 練習課題として「10万件のデータをソートして検索する」コードを書いてみると、線形探索と二分探索の速度差が体感できます。