ソートアルゴリズムの基礎とその平均計算量
本記事では、代表的なソートアルゴリズムであるバブルソート、選択ソート、クイックソート、マージソート、ヒープソートについて、それぞれのアルゴリズムの概要と平均計算量をオーダー記法（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実装例を示します。
バブルソート
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 + " ");
}
}
}
選択ソート
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 + " ");
}
}
}
クイックソート
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 + " ");
}
}
}
マージソート
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）
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 + " ");
}
}
}