主要なソートアルゴリズム(java)


# ソートアルゴリズムの基礎とその平均計算量

本記事では、代表的なソートアルゴリズムであるバブルソート、選択ソート、クイックソート、マージソート、ヒープソートについて、それぞれのアルゴリズムの概要と平均計算量をオーダー記法（Big O記法）で解説します。

## バブルソート（Bubble Sort）

### 概要

バブルソートは、隣接する要素を比較し、必要に応じて交換することでデータを整列させる単純なソートアルゴリズムです。複数回のパスを通じて、最も大きい（または小さい）要素が「泡のように」末尾に移動することからその名が付けられています。

### 平均計算量
- **時間計算量**: O(n²)
  バブルソートは、入力データのサイズをnとした場合、n回のパスを行い、各パスで最大でn-1回の比較・交換操作を行います。そのため、平均的なケースでも時間計算量は二乗オーダーとなります。

## 選択ソート（Selection Sort）

### 概要

選択ソートは、未ソート部分から最小（または最大）の要素を選び出し、ソート済み部分の末尾に配置することでデータを整列させるアルゴリズムです。各パスで一つの要素を確定させるため、バブルソートよりも交換回数が少なくなる特徴があります。

### 平均計算量
- **時間計算量**: O(n²)
  選択ソートも入力データのサイズnに対して、n回のパスを行い、各パスで未ソート部分全体を探索する必要があるため、平均的なケースでは二乗オーダーの時間計算量となります。

## クイックソート（Quick Sort）

### 概要

クイックソートは、分割統治法を用いた効率的なソートアルゴリズムです。基準となるピボット（基準値）を選び、ピボットより小さい要素と大きい要素に分割し、それぞれを再帰的にソートします。一般的に高速で、実用的なソートアルゴリズムとして広く使用されています。

### 平均計算量
- **時間計算量**: O(n log n)
  クイックソートは、データをピボットで均等に分割できる場合、再帰的な分割回数がlog nとなり、各レベルでn回の比較が必要です。そのため、平均的なケースではn log nの時間計算量となります。ただし、最悪の場合（既に整列されているデータなど）ではO(n²)となりますが、適切なピボット選択により最悪ケースを回避することが可能です。

## マージソート（Merge Sort）

### 概要

マージソートも分割統治法を用いたソートアルゴリズムです。データを再帰的に半分に分割し、それぞれをソートした後にマージ（統合）することで全体を整列させます。安定なソートであり、データの並び替えにおいて安定性が求められる場合に適しています。

### 平均計算量
- **時間計算量**: O(n log n)
  マージソートはデータをlog n回にわたって分割し、各レベルでn回のマージ操作を行うため、平均的なケースでもn log nの時間計算量となります。分割とマージのプロセスが確実に行われるため、常に安定したパフォーマンスを発揮します。

## ヒープソート（Heap Sort）

### 概要

ヒープソートは、ヒープデータ構造（特に最大ヒープまたは最小ヒープ）を利用してソートを行うアルゴリズムです。まずデータをヒープに構築し、ヒープの特性を活かして要素を一つずつ取り出し、整列させます。ヒープソートはインプレースで実行可能であり、安定性は保証されませんが、安定した時間計算量を持ちます。

### 平均計算量
- **時間計算量**: O(n log n)
  ヒープソートでは、ヒープの構築にO(n)の時間がかかり、その後n回の削除操作を行います。各削除操作ではヒープの再構築にlog nの時間が必要なため、全体としてn log nの時間計算量となります。最悪の場合でも時間計算量は同じくn log nです。

## まとめ

以下に、今回紹介したソートアルゴリズムとその平均計算量をまとめます。

| ソートアルゴリズム | 平均時間計算量  |
|-------------------|----------------|
| バブルソート       | O(n²)         |
| 選択ソート         | O(n²)         |
| クイックソート     | O(n log n)    |
| マージソート       | O(n log n)    |
| ヒープソート       | O(n log n)    |

- バブルソートと選択ソートは実装が簡単ですが、平均時間計算量がO(n²)と効率が悪いため、大規模なデータには不向きです。
- クイックソート、マージソート、ヒープソートは平均時間計算量がO(n log n)であり、実用的な用途に適しています。特にクイックソートは実装が比較的容易で、高速な動作を実現します。
- マージソートは安定なソートが必要な場合に有用であり、ヒープソートはインプレースでのソートが求められる場合に適しています。

それぞれのソートアルゴリズムには特性や適用シーンが異なるため、用途に応じて最適なアルゴリズムを選択することが重要です。

## ソースコード

以下に、各ソートアルゴリズムのJava実装例を示します。

### バブルソート

```java
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for(int i=0; i<n-1; i++) {
            swapped = false;
            for(int j=0; j<n-i-1; j++) {
                if(arr[j] > arr[j+1]) {
                    // 交換
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    swapped = true;
                }
            }
            // 交換がなければ終了
            if(!swapped) break;
        }
    }
    public static void main(String[] args) {
        int[] data = {5, 1, 4, 2, 8};
        bubbleSort(data);
        for(int num : data) {
            System.out.print(num + " ");
        }
    }
}
```

### 選択ソート

```java
public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for(int i=0; i<n-1; i++) {
            // 最小値のインデックスを探す
            int minIdx = i;
            for(int j=i+1; j<n; j++) {
                if(arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            // 交換
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
    public static void main(String[] args) {
        int[] data = {64, 25, 12, 22, 11};
        selectionSort(data);
        for(int num : data) {
            System.out.print(num + " ");
        }
    }
}
```

### クイックソート

```java
public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if(low < high) {
            // パーティション分割
            int pi = partition(arr, low, high);
            // 再帰的にソート
            quickSort(arr, low, pi-1);
            quickSort(arr, pi+1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // ピボットを末尾とする
        int i = (low - 1); // 小さい要素のインデックス

        for(int j=low; j<high; j++) {
            // 現在の要素がピボット以下なら交換
            if(arr[j] <= pivot) {
                i++;
                // 交換
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // ピボットを正しい位置に交換
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        return i+1;
    }

    public static void main(String[] args) {
        int[] data = {10, 7, 8, 9, 1, 5};
        int n = data.length;
        quickSort(data, 0, n-1);
        for(int num : data) {
            System.out.print(num + " ");
        }
    }
}
```

### マージソート

```java
public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if(left < right) {
            // 中央を計算
            int mid = left + (right - left) / 2;
            // 左半分をソート
            mergeSort(arr, left, mid);
            // 右半分をソート
            mergeSort(arr, mid+1, right);
            // マージ
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        // 左と右の部分配列のサイズ
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 一時配列を作成
        int[] L = new int[n1];
        int[] R = new int[n2];

        // データを一時配列にコピー
        for(int i=0; i<n1; i++) {
            L[i] = arr[left + i];
        }
        for(int j=0; j<n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        // マージ用のインデックス
        int i=0, j=0;
        int k = left;

        // マージ
        while(i < n1 && j < n2) {
            if(L[i] <= R[j]) {
                arr[k++] = L[i++];
            } else {
                arr[k++] = R[j++];
            }
        }

        // 残りの要素をコピー
        while(i < n1) {
            arr[k++] = L[i++];
        }
        while(j < n2) {
            arr[k++] = R[j++];
        }
    }

    public static void main(String[] args) {
        int[] data = {12, 11, 13, 5, 6, 7};
        int n = data.length;
        mergeSort(data, 0, n-1);
        for(int num : data) {
            System.out.print(num + " ");
        }
    }
}
```

### ヒープソート（Heap Sort）

```java
public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // ヒープを構築（最大ヒープ）
        for(int i = n/2 -1; i >=0; i--) {
            heapify(arr, n, i);
        }

        // ヒープから要素を1つずつ取り出してソート
        for(int i = n-1; i>=0; i--) {
            // ルート（最大値）を末尾と交換
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 残りのヒープをヒープ化
            heapify(arr, i, 0);
        }
    }

    // ヒープ化のヘルパーメソッド
    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // 親
        int left = 2*i +1; // 左の子
        int right = 2*i +2; // 右の子

        // 左の子が親より大きい場合
        if(left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 右の子が現在の最大値より大きい場合
        if(right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 最大値が親でなければ交換し、再帰的にヒープ化
        if(largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] data = {4, 10, 3, 5, 1};
        heapSort(data);
        for(int num : data) {
            System.out.print(num + " ");
        }
    }
}
```

## 参考資料
- [Wikipedia: Sorting algorithm](https://en.wikipedia.org/wiki/Sorting_algorithm)
- [Introduction to Algorithms by Cormen et al.](https://mitpress.mit.edu/books/introduction-algorithms)

---