【C#で学ぶ】応用情報技術者試験のためのアルゴリズム入門：ソート編

こんにちは！[前回](https://qiita.com/izutani/items/a701cdec50bc58fe9a74)に引き続き、応用情報技術者試験（AP）の受験者向けに「アルゴリズム」を解説します。今回は「ソートアルゴリズム」に焦点を当て、C#での実装例とともに代表的な「バブルソート」と「クイックソート」を取り上げます。

# ソートアルゴリズムとは？
ソートアルゴリズムは、データの並べ替えを行う手順のことです。たとえば、数値の配列を昇順や降順に整理する際に使います。応用情報技術者試験では、ソートの仕組みや効率性を問う問題が頻出します。ここでは、シンプルな「**バブルソート**」と効率的な「**クイックソート**」を学びましょう。

# 1. バブルソート（Bubble Sort）
### 概要
バブルソートは、隣り合う要素を比較して交換を繰り返し、徐々に大きな値（または小さな値）を端に寄せていくアルゴリズムです。イメージとしては、水面に泡（bubble）が浮かび上がるように値が移動します。

### 特徴
* **時間計算量**: `O(n²)`（nは要素数）
* **メリット**: 実装が簡単で理解しやすい
* **デメリット**: データ量が多いと非常に低速

### C#での実装例
以下は、配列を昇順に整列するバブルソートのコードです。

```csharp
using System;

class Program
{
    static void BubbleSort(int[] array)
    {
        int n = array.Length;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (array[j] > array[j + 1])
                {
                    // 隣接要素を交換
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    static void Main()
    {
        int[] numbers = { 5, 3, 8, 4, 2 };
        Console.WriteLine("ソート前: " + string.Join(", ", numbers));

        BubbleSort(numbers);
        Console.WriteLine("ソート後: " + string.Join(", ", numbers));
    }
}
```

### 実行結果
```text
ソート前: 5, 3, 8, 4, 2
ソート後: 2, 3, 4, 5, 8
```

# 2. クイックソート（Quick Sort）
### 概要
クイックソートは、ピボットと呼ばれる基準値を決め、それをもとに配列を「ピボットより小さい部分」と「ピボットより大きい部分」に分割するアルゴリズムです。この分割を再帰的に繰り返すことで高速にソートします。

### 特徴
* **時間計算量**: 平均 `O(n log n)`、最悪 `O(n²)`
* **メリット**: 平均的に非常に高速
* **デメリット**: 最悪ケース（ピボットが極端に偏る場合）が発生する可能性

### C#での実装例
以下は、配列を昇順に整列するクイックソートのコードです。ピボットは配列の末尾要素を使用します。

```csharp
using System;

class Program
{
    static void QuickSort(int[] array, int low, int high)
    {
        if (low < high)
        {
            int pivotIndex = Partition(array, low, high);
            QuickSort(array, low, pivotIndex - 1); // 左部分をソート
            QuickSort(array, pivotIndex + 1, high); // 右部分をソート
        }
    }

    static int Partition(int[] array, int low, int high)
    {
        int pivot = array[high]; // ピボットを末尾に設定
        int i = low - 1; // 小さい値の範囲のインデックス

        for (int j = low; j < high; j++)
        {
            if (array[j] <= pivot)
            {
                i++;
                // 要素を交換
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // ピボットを適切な位置に移動
        int tempPivot = array[i + 1];
        array[i + 1] = array[high];
        array[high] = tempPivot;

        return i + 1; // ピボットの位置を返す
    }

    static void Main()
    {
        int[] numbers = { 5, 3, 8, 4, 2 };
        Console.WriteLine("ソート前: " + string.Join(", ", numbers));

        QuickSort(numbers, 0, numbers.Length - 1);
        Console.WriteLine("ソート後: " + string.Join(", ", numbers));
    }
}
```

### 実行結果
```text
ソート前: 5, 3, 8, 4, 2
ソート後: 2, 3, 4, 5, 8
```

# 試験対策のポイント
* **アルゴリズムのステップを追う**
バブルソートは単純ですが、クイックソートはピボットの動きを理解するのが重要です。紙に書き出してステップを追ってみましょう。
* **時間計算量の違いを意識**
`O(n²)`と`O(n log n)`の差は、データ量が増えたときの効率に大きく影響します。試験では「どのアルゴリズムが適切か」を問われることも。
* **実装の工夫を考える**
たとえば、バブルソートに「交換が不要なら終了」という最適化を加えるとどうなるか、考えてみてください。

# おわりに
今回はバブルソートとクイックソートをC#で実装しながら学びました。ソートアルゴリズムは応用情報技術者試験で頻出かつ、実務でも基礎となる知識です。コードを自分で書き、動作を確認することで理解が深まります。過去問を解きながら、アルゴリズムの特徴をしっかり押さえて試験に臨んでください。応援しています！