🙌

【C#アルゴリズム】素朴なソートアルゴリズム

に公開
C#
アルゴリズム
ソート
tech

この記事でわかること

  • 素朴なソートアルゴリズム がどんな問題を解くための考え方か
  • 基本アイデアと処理の流れ
  • 実装するときに注意する点
  • 計算量の見方

参考資料

広告：この記事にはアフィリエイトリンクが含まれます。

『アルゴリズム図鑑 増補改訂版』

この記事で扱う処理の流れを、図を使って直感的に理解したい人向けの入門書です。

全体像

はじめに

paiza　、アルゴリズムの本で素朴なソートアルゴリズムについて学んだのでまとめました。
素朴なソートアルゴリズムは、比較的簡単で直感的に理解しやすいアルゴリズムの総称で、これらは計算回数やソートの基本原理を理解するのに適しています。ただし、効率が低いため、大量のデータには向きません。

代表的な素朴なソートアルゴリズムであるバブルソート、選択ソート、挿入ソートについてまとめました。

1. バブルソート (Bubble Sort)

  • 概要: 配列内の隣接する要素を比較し、小さいものを左側に移動させる操作を繰り返します。配列が完全にソートされるまでこのプロセスを繰り返します。
  • 特徴:
    • 計算量 : O(n^2)
  • 実装例 (csharp):
      private static void BubbleSort(int[] A, int n)
  {
    for (int i = 0; i < n - 1; i++)
    {
      for (int j = n - 1; j >= i + 1; j--)
      {
        if (A[j] < A[j - 1])
        {
          int temp = A[j];
          A[j] = A[j - 1];
          A[j - 1] = temp;
        }
      }
      Console.WriteLine(string.Join(" ", A));
    }
  }

2. 選択ソート (Selection Sort)

  • 概要: 配列内で最小（または最大）の要素を探し、それを現在の位置に移動します。この操作を配列全体で繰り返します。
  • 特徴:
    • 時間計算量 : O(n^2)
  • 実装例 (csharp):
      private static void SelectionSort(int[] A, int n)
  {
    for (int i = 0; i < n - 1; i++)
    {
      int minIndex = i;
      for (int j = i + 1; j < n; j++)
      {
        if (A[j] < A[minIndex])
        {
          minIndex = j;
        }
      }
      //Swap（タプルでも行える）
      int temp = A[minIndex];
      A[minIndex] = A[i];
      A[i] = temp;
      Console.WriteLine(string.Join(" ", A));
    }
  }

3. 挿入ソート (Insertion Sort)

  • 概要: 配列の要素を一つずつ取り出し、既にソートされた部分に挿入することで配列をソートします。
  • 特徴:
    • 計算量: 悪の場合 O(n^2)、最良の場合（すでにソートされている場合）は (O(n))
  • 実装例 (csharp):
      private static void InsertionSort(int[] A, int n)
  {
    for (int i = 1; i < n; i++)
    {
      int x = A[i];
      int j = i - 1;
  
      while (j >= 0 && A[j] > x)
      {
        A[j + 1] = A[j];
        j--;
      }
      A[j + 1] = x;
      Console.WriteLine(string.Join(" ", A));
    }
  }

特徴比較

アルゴリズム 時間計算量 (平均) 時間計算量 (最良)
バブルソート O(n^2) O(n^2)
選択ソート O(n^2) O(n^2)
挿入ソート O(n^2) O(n)

つまずきやすいポイント

  • 前提条件を確認します。ソート済みか、グラフが有向か無向か、indexが0始まりか1始まりかで実装が変わります。
  • サンプルを小さくして、手で1ステップずつ追うと理解しやすいです。
  • 計算量を確認し、制約に対して間に合うかを見ることが大切です。

Discussion