12,950
回編集
「C++の基礎 - ソート」の版間の差分
ナビゲーションに移動
検索に移動
→単純挿入法 (挿入ソート)
(→バブルソート) |
|||
| 238行目: | 238行目: | ||
ステップ 6: 11 12 22 25 34 64 90 50 # 90は既にソート済み部分の要素より大きいため、位置は変わらない | ステップ 6: 11 12 22 25 34 64 90 50 # 90は既にソート済み部分の要素より大きいため、位置は変わらない | ||
ステップ 7: 11 12 22 25 34 50 64 90 # 50を64と90の間の適切な位置に挿入する | ステップ 7: 11 12 22 25 34 50 64 90 # 50を64と90の間の適切な位置に挿入する | ||
ソート後の配列: 11 12 22 25 34 50 64 90 | |||
<br><br> | |||
== マージソート == | |||
マージソートは、分割統治法に基づくソートアルゴリズムである。<br> | |||
配列を再帰的に半分に分割して、それぞれをソートした後にマージ (統合) することにより全体をソートする。<br> | |||
<br> | |||
# 配列を半分に分割する。 | |||
# 分割した各部分を再帰的にソートする。 | |||
# ソートされた2つの部分配列をマージして1つの配列にする。 | |||
<br> | |||
計算量は <math>O(n \log{n})</math> で、クイックソートと同様に効率的なアルゴリズムである。<br> | |||
安定なソートであり、データの偏りに影響されず常に一定の性能を発揮する。<br> | |||
ただし、追加のメモリ空間が必要という特徴がある。<br> | |||
<br> | |||
マージソートは大規模なデータセットの処理に適しているが、追加メモリが必要なためメモリ制約が厳しい環境では注意が必要となる。<br> | |||
<br> | |||
<syntaxhighlight lang="c++"> | |||
#include <iostream> | |||
using namespace std; | |||
// マージを行う関数 | |||
void merge(int arr[], int left, int mid, int right) | |||
{ | |||
int n1 = mid - left + 1; | |||
int n2 = right - mid; | |||
// 一時配列の作成 | |||
int L[n1], R[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, k = left; | |||
while (i < n1 && j < n2) { | |||
if(L[i] <= R[j]) { | |||
arr[k] = L[i]; | |||
i++; | |||
} | |||
else { | |||
arr[k] = R[j]; | |||
j++; | |||
} | |||
k++; | |||
} | |||
// 残りの要素をコピー | |||
while (i < n1) { | |||
arr[k] = L[i]; | |||
i++; | |||
k++; | |||
} | |||
while(j < n2) { | |||
arr[k] = R[j]; | |||
j++; | |||
k++; | |||
} | |||
} | |||
// マージソートを行う再帰関数 | |||
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); // マージ | |||
// 現在の配列の状態を表示 | |||
cout << "部分ソート (left=" << left << ", right=" << right << "): "; | |||
for (int i = 0; i < 8; i++) { | |||
cout << arr[i] << " "; | |||
} | |||
cout << endl; | |||
} | |||
} | |||
int main() | |||
{ | |||
int arr[8] = {64, 34, 25, 12, 22, 11, 90, 50}; | |||
int n = 8; | |||
cout << "ソート前の配列: "; | |||
for (int i = 0; i < n; i++) { | |||
cout << arr[i] << " "; | |||
} | |||
cout << endl; | |||
mergeSort(arr, 0, n - 1); | |||
cout << "ソート後の配列: "; | |||
for (int i = 0; i < n; i++) { | |||
cout << arr[i] << " "; | |||
} | |||
cout << endl; | |||
return 0; | |||
} | |||
</syntaxhighlight> | |||
<br> | |||
# 出力例: | |||
ソート前の配列: 64 34 25 12 22 11 90 50 | |||
部分ソート (left=0, right=1): 34 64 25 12 22 11 90 50 | |||
部分ソート (left=0, right=2): 25 34 64 12 22 11 90 50 | |||
部分ソート (left=3, right=4): 25 34 64 12 22 11 90 50 | |||
部分ソート (left=3, right=5): 25 34 64 11 12 22 90 50 | |||
部分ソート (left=6, right=7): 25 34 64 11 12 22 50 90 | |||
部分ソート (left=3, right=7): 25 34 64 11 12 22 50 90 | |||
部分ソート (left=0, right=7): 11 12 22 25 34 50 64 90 | |||
ソート後の配列: 11 12 22 25 34 50 64 90 | ソート後の配列: 11 12 22 25 34 50 64 90 | ||