目次から探す
マージソートの概要
マージソートは、効率的なソートアルゴリズムの一つです。
データを分割し、それぞれをソートしてから結合することで、全体をソートします。
マージソートは、再帰的なアプローチを取るため、分割統治法と呼ばれる手法に基づいています。
マージソートの特徴
マージソートの特徴は以下の通りです。
- 安定なソートアルゴリズムであるため、同じ値を持つ要素の順序が変わることはありません。
- データの分割と結合の過程で、追加のメモリを必要とするため、ソート対象のデータ量が大きい場合にはメモリ使用量に注意が必要です。
マージソートの利点
マージソートの利点は以下の通りです。
- データの分割と結合の過程で、比較回数が最小限に抑えられるため、効率的なソートが可能です。
- データの分割が再帰的に行われるため、ソート対象のデータがソート済みであっても、効率的に処理することができます。
マージソートの欠点
マージソートの欠点は以下の通りです。
- 追加のメモリを必要とするため、ソート対象のデータ量が大きい場合にはメモリ使用量に注意が必要です。
- 分割と結合の過程で、データのコピーが発生するため、処理速度が遅くなる可能性があります。
マージソートのアルゴリズム
マージソートの手順
マージソートの手順は以下の通りです。
- ソート対象のデータを分割します。
データの中央を基準に、左側と右側に分割します。
- 分割したデータそれぞれに対して、再帰的にマージソートを適用します。
- 分割されたデータを結合します。
結合する際には、比較しながら小さい順に結合していきます。
マージソートの実装例
以下に、C言語でのマージソートの実装例を示します。
#include <stdio.h>
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
int i = 0, j = 0, k = 0;
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < leftSize) {
arr[k++] = left[i++];
}
while (j < rightSize) {
arr[k++] = right[j++];
}
}
void mergeSort(int arr[], int size) {
if (size < 2) {
return;
}
int mid = size / 2;
int left[mid];
int right[size - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = arr[i];
}
mergeSort(left, mid);
mergeSort(right, size - mid);
merge(arr, left, mid, right, size - mid);
}
int main() {
int arr[] = {5, 2, 8, 3, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, size);
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}上記のコードでは、merge関数で2つの配列をマージし、mergeSort関数で再帰的にマージソートを行っています。
最後に、ソートされた配列を出力しています。
Sorted array: 1 2 3 5 8