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

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

ソートアルゴリズムとは？

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

1. バブルソート（Bubble Sort）

概要

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

特徴

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

C#での実装例

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

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));
    }
}

実行結果

ソート前: 5, 3, 8, 4, 2
ソート後: 2, 3, 4, 5, 8

2. クイックソート（Quick Sort）

概要

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

特徴

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

C#での実装例

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

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));
    }
}

実行結果

ソート前: 5, 3, 8, 4, 2
ソート後: 2, 3, 4, 5, 8

試験対策のポイント

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

おわりに

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