Zenn
🙌

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

2024/11/21に公開
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)

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/3YtOnpz

Discussion