前回に引き続き今回はマージソートについてです
-
バブルソートを理解する - ナストンのまとめ
前回に引き続き今回はバブルソートについてです バブルソートって? ソートアルゴリズムの1つで、処理時間が遅いものとなりま ...
nasuton.net
マージソートって?
クイックソートと同じく処理が速いものとなりますが、ソート時に複数の配列を作成する必要があるため、メモリを消費するという難点があります。詳しくは以下のサイトがわかりやすいと思います
-
【図解】マージソート:アルゴリズム【C言語】
本記事では、マージソートのアルゴリズムの実際の動き・実装を解説しています。図を多く使用して解説しているため、初学者の方で ...
続きを読む
マージソートを実装する
ランダム配列は前回の記事で作成したものを使用します。それでは実際にマージソートをC++で実装してみます
template <typename T>
void mergeSort(std::vector<T>& arr, int left, int right) {
if (left < right) {
int middle = left + (right - left) / 2;
// 左半分をマージソート
mergeSort(arr, left, middle);
// 右半分をマージソート
mergeSort(arr, middle + 1, right);
// マージ
merge(arr, left, middle, right);
}
}
まずは再帰的に呼び出す関数を用意します。配列の入れ替えを実施する関数は別で用意します
template <typename T>
void merge(std::vector<T>& arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
// 一時的なベクターを作成
std::vector<T> leftArray(n1);
std::vector<T> rightArray(n2);
// 左半分を一時的なベクターにコピー
for (int i = 0; i < n1; i++) {
leftArray[i] = arr[left + i];
}
// 右半分を一時的なベクターにコピー
for (int j = 0; j < n2; j++) {
rightArray[j] = arr[middle + 1 + j];
}
// マージ
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
// 左半分に残った要素をコピー
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
// 右半分に残った要素をコピー
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
最期に配列の中身を入れ替える関数を実装します
実際に動かしてみる
検証用の配列を作成し、それをマージソートで並び替えて結果を見てみましょう
std::vector<int> arr = RandomCreate();
int size = arr.size();
std::cout << "Original Array: ";
for (int i : arr) {
std::cout << i << " ";
}
std::cout << std::endl;
mergeSort(arr, 0, size - 1);
std::cout << "Sorted Array: ";
for (int i : arr) {
std::cout << i << " ";
}
std::cout << std::endl;
マージソートを用いて配列が並び変えられていることが確認できました