アルゴリズム #1 ソートと探索

• Lingheng Tao
• 2024年1月13日
• 読了時間 5 分

Algorithms & Data Structure Content List C++ Programming Content List C++ Programming #8 Polymorphism

#ComputerScience#GameProgramming

このノートは主にソートアルゴリズムについてです。このシリーズのノートはすべて擬似コードの形式を採用します。データ構造がアルゴリズムの実装に非常に重要な場合を除き、ほとんどの場合アルゴリズムの実装ではなく、アルゴリズムそのものを主に考察します。

以下は一般的なソートアルゴリズムのチートシートです。

O(n²) のソート

ソートを理解するには、直感的な言語とコードの両方で記述できる必要があります。

ソート問題は次のようにまとめられます：

• Input：N 個の無秩序な要素（< 上で全順序を持つ）
• Output：N 個の昇順の要素

まず O(n²) のソートから始めます。

選択ソート Selection Sort

言語で説明すると：

• 0 回目、インデックス [0, n-1] で最小のものを探し、0 番目の数と交換する。
• 1 回目、インデックス [1, n-1] で最小のものを探し、1 番目の数と交換する。
• ...
• n-1 回目、インデックス n-1 の最小値（この時点で1つしかないので交換不要）を探す。

合計 n 回の交換を行い、各交換で最大 n 回の配列全体の走査が必要です。したがって複雑度は O(n²)。

擬似コードで記述すると：

Plain Textfor(int i = 0; i < n; i++):
    // 各ループでの最小値を維持
    min_index = i
    for(int j = i + 1; j < n; j++):
    // a[i] と a[i, length(A)] の最小要素を交換
        if A[j] < A[min_index]
            min_index = j
    swap A[i] and A[min_index]

このアルゴリズムは i 番目に小さい要素を a[i] に配置します。配列の i 番目の左側は i 個の最小要素で、これらは再びアクセスされません。

時間複雑度：最悪 O(n²)。

バブルソート Bubble Sort

• 0 番目から始め、隣り合う2つの数字を比較する。前が後より大きければ交換する。前が小さければそのまま。
• 1回の完全な比較後、最大の数字が最後の位置に来る。泡が水中から水面に浮かび上がるように。
• この過程を繰り返すが、毎回比較範囲を1つ狭める（最後の数字は既にソート済みのため）。
• 交換が必要なくなるまで続け、ソート完了。

Plain Textfor (int i = 0; i < n; i++):  // ソートのラウンド数を制御
    for (int j = 0; j < n - i - 1; j++):  // 未ソート部分を走査
        if A[j] > A[j + 1]:  // 前の要素が後ろより大きい場合
            swap A[j] and A[j + 1]  // 2つの要素を交換

合計 n 回のバブルが行われます。各回で最大値を右に押し出し、最悪の場合 O(n) 回押し出すため、複雑度は O(n²)。

挿入ソート Insertion Sort

• [0,0] をソート済みにする（既に完了）。
• [0,1] をソート済みにする。
• [0,2] をソート済みにする。
• ……
• [0, n-1] をソート済みにする。

トランプを取るのと同じ。

Plain Textfor (int i = 1; i < n; i++):
    // 現在取ったカードは i 枚目
    card = A[i]
    j = i - 1
    while j > 0 and A[j] > card:
        // 前 i 枚のカードをソート
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = card

特徴：初期状態に依存する。初期がほぼソート済みなら、ソートはかなり速くなる。

時間複雑度：平均・最悪 O(n²)、最良 O(n)

O(nlogn) のソート

マージソート Merge Sort

マージソートは再帰的なソートです。言語で説明すると：

• まず左側をソート（再帰ステップ）
• 次に右側をソート（再帰ステップ）
• 最後に配列全体を統合（マージ）

コードで記述すると：

Plain Textmergesort(int[] arr, int L, int R):
	if (L==R) return;
	// 中点を取得
	mid = L + ((R-L)>>1);
	// 左側をソート
	mergesort(arr, L, mid);
	// 右側をソート
	mergesort(arr, mid+1, R);
	// マージステップ
	merge(arr, L, mid, R);

マージソートは再帰の考え方を適用し、Divide and Conquer のアプローチを採用します。毎回半分のソートを処理し、最後に統合します。マージソートは毎回中央で分割し、中央より前の部分をソートし、中央より後の部分をソートし、最後にソート済みの2つの部分と中央の値をマージします。

ここで、merge が最も重要で最も間違いやすい部分です。

Plain Textmerge(int[] arr, int L, int mid, int R):
	// マージ用の補助空間を準備（サイズは R-L + 1）
	int[] help = new int[R-L+1];
	// 左側先頭と右側先頭のインデックスを準備
	int i = 0; p1 = L; p2 = M+1;
	while(p1 <= M && p2 <=R): // 左右とも範囲内
		// 常に小さい方を先にコピー；左右が等しい場合は左を先にコピーして安定性を保つ
		help[i++] =  arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; 
	while(p1 <= M): // p2 が先に範囲外になった場合、p1 の残りをコピー
		help[i++] = arr[p1++];
	while(p2 <= R): // p1 が先に範囲外になった場合、p2 の残りをコピー
		help[i++] = arr[p2++];
	for(int i = 0; i < help.length; i++): 
		arr[L+i] = help[i];

しかし難しくはありません。核心の目的は2つのソート済み配列をマージすることです。マージに必要な補助空間の長さは両者の合計、つまり R - L + 1 です。双ポインタで両方のリストを見て、小さい方を先にコピーします。

時間複雑度：平均・最悪・最良とも O(n log n)

クイックソート Quick Sort

Plain TextquickSort(A, low, high)
if low < high
    pi = partition(A, low, high)
    quickSort(A, low, pi-1)
    quickSort(A, pi+1, high)
else return

簡潔に言うと、クイックソートは毎回ピボット値を選び、ピボットより小さいものを左に、大きいものを右に置き、左右それぞれに再帰的にクイックソートを行います。

平均：O(n log n)

最良：O(n log n)

最悪：O(n²) - 配列が既にソート済み、または全要素が等しい場合

交換操作

ここで XOR 演算（^）に基づく交換を特に紹介します。以下のコードでデータの交換ができます。

Plain Textint a, b; // a と b が既に初期化され値があると仮定
a = a ^ b;
b = a ^ b;
a = a ^ b; // この時点で a と b のデータ交換が完了

XOR 演算はビット演算です。性質として、2ビットが等しければ結果は0、異なれば1。つまり

• 1 ^ 1 = 0, 0 ^ 0 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1;

したがって、以下の性質を満たします：

• 0 ^ n = n.
• n ^ n = 0. => a ^ b ^ a = a ^ a ^ b = 0 ^ b = b.
• a ^ b = b ^ a.
• a ^ (b ^ c) = (a ^ b) ^ c.

読者は上記3行のコードの動作を自分で確認できます。

参考文献：

1. Introduction to Algorithm, 3rd Edition